最终得到的最小生成树为 算法的思路如下: ①并查集初始化:将所有顶点置为只有一个顶点的连通分量 ②检查所有的边 i)若边的两个端点i与j不在同一连通分量上(i与j在并查集中不同根),则连通之(合并); i)若边的两个端点i与j在同一连通分量上(i与j在并查集中同根),则 在并查集中寻找离i与j最近的共同祖先结点 分别从i与j向上检测具有最大权值的边 在并查集上删除具有最大权值的边,加入新的边 下面给出实现算法 t int MaxNum =10000: I Graph Dijkstra (i L,h,p, q, k; ∥并查集 for(i=0;i< Vertices Num;计++) disJoint=-1;∥并查集初始化 for (i=0; i<Vertices Num-I; i++) ∥检查所有的边 um; j++) ∥判结点i与j是否在同一连通分量上 while( disJoint[p]>=0)p=disJoint[p]: while( disJoint[ql >=0)p=disJoint(ql ∥i与j不在同一连通分量上,连通之 i else ∥i与j在同一连通分量上 ∥寻找离结点i与j最近的祖先结点 dis Joint[p] >=0)i 每变动一个p,就对q到根的路径检测一遍 while( disJoint(q >=0 & disJoint[]==disJoint[p]) jOint[ql if( disJoint[gl=disJointp))break aJoint[P]: 是i和j的最近的共同祖先 p=i;q= disJoint[p];max= MaxNum;m从i到k找权值最大的边(s1,s2) while(q<=k)i if( Edge[q][p]> max)( max= Edge[qlp]: sl=p; s2=q:) disJoint[p]:第 8 章 图 106 最终得到的最小生成树为 算法的思路如下： ① 并查集初始化：将所有顶点置为只有一个顶点的连通分量； ② 检查所有的边： ⅰ）若边的两个端点 i 与 j 不在同一连通分量上(i 与 j 在并查集中不同根)，则连通之(合并)； ⅱ) 若边的两个端点 i 与 j 在同一连通分量上(i 与 j 在并查集中同根)，则 — 在并查集中寻找离 i 与 j 最近的共同祖先结点 — 分别从 i 与 j 向上检测具有最大权值的边 — 在并查集上删除具有最大权值的边，加入新的边。 下面给出实现算法： const int MaxNum = 10000; void Graph :: Dijkstra ( ) { GraphEdge e; int VerticesNum = GetVerticesNum ( ); int i, j, p, q, k; int disJoint[VerticesNum]; //并查集 for ( i = 0; i < VerticesNum; i++ ) disJoint[i] = -1; //并查集初始化 for ( i = 0; i < VerticesNum-1; i++ ) //检查所有的边 for ( j = i + 1; j < VerticesNum; j++ ) if ( Edge[i][j] < MaxNum ) { //边存在 p = i; q = j; //判结点 i 与 j 是否在同一连通分量上 while ( disJoint[p] >= 0 ) p = disJoint[p]; while ( disJoint[q] >= 0 ) p = disJoint[q]; if ( p != q ) disJoint[j] = i; // i 与 j 不在同一连通分量上, 连通之 } else { // i 与 j 在同一连通分量上 p = i; //寻找离结点 i 与 j 最近的祖先结点 while ( disJoint[p] >= 0 ) { //每变动一个 p, 就对 q 到根的路径检测一遍 q = j; while ( disJoint[q] >= 0 && disJoint[q] == disJoint[p] ) q = disJoint[q]; if ( disJoint[q] == disJoint[p] ) break; else p = disJoint[p]; } k = disJoint[p]; //结点 k 是 i 和 j 的最近的共同祖先 p = i; q = disJoint[p]; max = -MaxNum; //从 i 到 k 找权值最大的边(s1, s2) while ( q <= k ) { if ( Edge[q][p] > max ) { max = Edge[q][p]; s1 = p; s2 = q; } p =q; q = disJoint[p]; ① ② ⑤ ④ 14 ⑥ ③ 16 5 6 11