Llf's blog

标签 生成树 下的文章

February 6, 2018

最小生成树

概念 最小生成树即为无向图中结点构成的树中各边权值之和最小的树,可以有多种情况。一般用Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。 Kruskal算法 方法 可以将Kruskal算法理解成对边的贪心算法。 1.将路径用邻接表存储,存储的值为起点、终点和权值; 2.将邻接表按照权值为关键字排序; 3.从最小权值的边开始循环,每连接起两个结点就把它们并到同一个集合(并查集实现)...