L16 图优化

Posted on Edited on In Views:

Outline:

  • BestFS
  • MCE

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇

BestFS( Prim, Dijk )

Free → Fringe → Finished

  • Fringe的update可能会更新权重

代价

  • 抽象： \(n \times (getMin, deleteMin, Insert) + m \times (decreaseKey)\)

  • Priority Queue:

    • 数组实现优先队列以实现Prim或Dijkstra： \(O(n^2 + m)\)​

    • getMin: \(O(n)\)

    • decreaseKey: \(O(1)\)

    • 贪心选择选择所有点（ n × n）， 对于边进行权重更新（ m × 1 ）

  • Heap：

    • Heap实现优先队列以实现Prim或Dijkstra：\(O（nlogn + mlogn）\)
    • getMIN: \(O(1)\)
    • deleteMin, Insert （都是fixHeap）: \(O(logn)\)
    • decreaseKey ( 不断上浮): \(O(logn)\)​
    • 每个点都要进队列( n × logn ) , 每个边都要权重更新( m × logn )
    • 因为Prim算法通常用于连通片,后者有\(m \geq n - 1\) , 则复杂度化为\(O(mlogn)\)

MCE( Prim, Kruskal )

Min-weight Cut-crossing Edge,

  • MCE一定在MST中

    • Proof:
    若(a,b)为MCE不在MST中, 则a,b两点在MST中必定通过另外两点连通,设为c,d. 在MST中加入*(a,b)*,得到一个环. 再删除*(c,d)*,得到一个更小的ST, 与""最小生成树"矛盾"

  • Prim: 从当前的Finished部分出发, 找MCE

  • Kruskal: 如果两点a,b已经连通( a,b在不同的cut中 ),则根据kruskal算法,(a,b)不是MCE,因为之前有更小的. 反之则(a,b)为MCE. 其实就是判断加了这条边后生成树是否会成环