最小生成树

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。 [1] 最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。摘自百度

Prim算法

个人认为这是一个贪心算法，从任意一个点开始，选择一个与这个点连接的最小权边组成一颗树，然后再从剩下的点中找一个与当前的树连接最小的权边，不停的这样取点直到取完

prim wiki

The algorithm may informally be described as performing the following steps:

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).

Kruskal算法

参考

kruskal wiki

Algorithm

• create a forest F (a set of trees), where each vertex in the graph is a separate tree : 把图中所有的点作为一个单独的树放到集合F中

• create a set S containing all the edges in the graph : 把图分解成树，每个树包含一条边

• while S is nonempty and F is not yet spanning : s不为空，表示还有边没加入到生成树中; F不连通，说明还有孤立的点, spanning是连通的意思

  • remove an edge with minimum weight from S : 先择权值最小的边

  • if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree ： 如果这个边连接了两个不同的树则把这个边加入到F中，这样就把两个不同的树连在了一起

这个算法以边为切入点，每次在在一个图中选择权值最小的边直到所有的点都在生成的树中