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