图最小生成树

生成树:

若从连通图的某个顶点出发,可以系统的访问到图中所有的顶点,则遍历时经历过得边和图的所有顶点构成的的子图,成为该图的生成树。

最小生成树(MST):

如果连通图是网,则网中所有生成树中权值总和最小的生产树为最小生成树。

Prim算法:

设G=(V,E)为N个顶点的连通图,T=(U,TE)是G的最小生成树,T的初始状态为U={U0},TE={},重复执行以下操作:

在所有u属于U,v=V-U中的边中找一条最小权值的边(u,v)加入到TE中,同时v并入到U,直至U=V。

算法演示:http://sjjg.js.zwu.edu.cn/SFXX/sf1/prim.html

Kruskal算法:

与Prim算法类似,首先初始化一个T=(v,null),此时最T是一个无边的森林,按权值递增的顺序选择E中(u,v)加入到T。除了最终结果外T是最小生成树,其他情况下都是森林。

算法演示:http://sjjg.js.zwu.edu.cn/SFXX/sf1/kruskal.html

原文地址:https://www.cnblogs.com/273809717/p/2817596.html