怎么网站代备案,谷歌推广关键词匹配,湖北网站建设制作,wordpress英文写作插件点睛Prim与Kruskal算法是用来求图的最小生成树的算法。最小生成树有n个顶点#xff0c;n-1条边#xff0c;不能有回路。Prim算法Prim算法的特点是从个体到整体#xff0c;随机选定一个顶点为起始点出发#xff0c;然后找它的权值最小的边对应的另一个顶点#xff0c;这两个…点睛Prim与Kruskal算法是用来求图的最小生成树的算法。最小生成树有n个顶点n-1条边不能有回路。Prim算法Prim算法的特点是从个体到整体随机选定一个顶点为起始点出发然后找它的权值最小的边对应的另一个顶点这两个顶点就构成了新的个体连通图然后在这两个顶点的所有边中找权值最小的边对应的另一个顶点前提是加进来不能导致已有的顶点所在的连通图构成回路就这样直到所有顶点都并入同一个连通图算法结束。例1利用Prim算法求下图的一棵最小生成树设顶点1为起始点写出求解过程。答案找到顶点1权值最小的边1,3则顶点1和3构成新的连通图找到顶点1和3中权值最小的边3,4则顶点1,3,4构成新的连通图找到顶点1,3,4中权值最小的边4,7则顶点1,3,4,7构成新的连通图找到顶点1,3,4,7中权值最小的边7,8则顶点1,3,4,7,8构成新的连通图找到顶点1,3,4,7,8中权值最小的边8,6则顶点1,3,4,7,8,6构成新的连通图找到顶点1,3,4,7,8中权值最小的边8,5则顶点1,3,4,7,8,6,5构成新的连通图找到顶点1,3,4,7,8,5中权值最小的边1,2则顶点1,3,4,7,8,6,5,2构成新的连通图至此Prim算法结束找到最小生成树如下图Kruskal算法Kruskal算法的特点是从整体到个体它把整个图默认是无向连通图看做n个独立的顶点然后把图的所有带权边根据权值大小升序排列存入一个序列中。最后依次从序列中取出这些边加入n个独立的顶点使它们成为同一个连通图的一部分只要取出的边的数量不到n-1就一直取。在取的过程中如果有一条边的加入会造成回路则跳过选下一个权值稍大的边。例2利用Kruskal算法求下图的一棵最小生成树写出求解过程。答案将图中所有的边按照权值大小升序排列存入集合中结果如下{(1,2), (1,3), (1,4), (2,5), (2,6), (3,4, (3,7), (4, 5), (4,7), (5,6), (5, 8), (6,8), (7,8)}从集合中取出边1,2顶点1和2构成一个新的连通图从集合中取出边1,3顶点123构成一个新的连通图从集合中取出边1,4顶点123,4构成一个新的连通图从集合中取出边2,5顶点123,4,5构成一个新的连通图从集合中取出边2,6顶点123,4,5,6构成一个新的连通图从集合中取出边3,4会在顶点1,3,4之间构成回路跳过从集合中取出边3,7顶点12,3,4,5,6,7构成一个新的连通图从集合中取出边4,5会在顶点124,5构成回路跳过从集合中取出边4,7顶点13,4,7构成回路跳过从集合中取出边5,6顶点2,5,6构成回路跳过从集合中取出边5,8顶点12,3,4,5,6,7,8构成一个新的连通图边的个数达到n-1结束最小生成树如下图
