Minimum Spanning Trees

  • A Minimum Spanning Trees is a spanning tree of minimum total weight.

    • Example: Directly connecting buildings by power lines.

  • 定义图的生成树是它的一棵含有其所有顶点的无环连通子图 。 一幅加杈图的最小生成树 （ MST ）是它的一棵权值 （ 树中所有边的权值之和 ） 最小的生成树

  • Determain graph has cycle

  • Application

    • For example, I want to wire up a bunch of towns, that they can all have power. In that case, you are trying to minimize the total cost of all.

  • 与 Shortest Paths 的关系

    • MST 有的时候恰好是某个 Vertex 的 SPT

  • 设计 MST 算法（行不通的

    • 选择最好的 Vertex
    • 运行 Dijkstra

  • Cut Property

  • Prim's Algorithm

  • Kruskal's Algorithm


https://en.wikipedia.org/wiki/Minimum_spanning_tree#Optimal_algorithm