L16 图优化

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\ge 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. 其实就是判断加了这条边后生成树是否会成环