第8章图 第7章图 7-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向 完全图中,边的条数为n(n-1)2。 【解答】 1个顶点的2个顶点的 无向完全图无向完全图 3个顶点的 4个顶点的 无向完全图 无向完全图 5个顶点的 无 向完全图 【证明】 在有n个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有n-1 条边与其他n-1个顶点相连,总计n个顶点有n(n-1)条边。但在无向图中,顶点i到顶点j与顶点j到顶 点i是同一条边,所以总共有n(n-1)2条边 7-2右边的有向图是强连通的吗?请列出所有的简单路径。 【解答】 判断一个有向图是否强连通,要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点,它不是强连通的有向图。各个顶点自成 强连通分量 所谓简单路径是指该路径上没有重复的顶点 从顶点A出发,到其他的各个顶点的简单路径有A→B,A→D→B,A→B→C,A→D→B→C,A D,A→B→E,A→D→E,A→D→B→E,A→B→C→F→E,A→D→B→C→F→E,A→B→C→F,A →D→B→C→F。 从顶点B出发,到其他各个顶点的简单路径有B→C,B→C→F,B→E,B→C→F→E 从顶点C出发,到其他各个顶点的简单路径有C→F,C→F→E 从顶点D出发,到其他各个顶点的简单路径有D→B,D→B→C,D→B→C→F,D→E,D→B→E D→B→C→F→E 从顶点E出发,到其他各个顶点的简单路径无 从顶点F出发,到其他各个顶点的简单路径有F→E。 7-3给出右图的邻接矩阵、邻接表和邻接多重表表示 【解答】 (1)邻接矩阵 010100 0010 0 000001 Ed 0100 000000 000010
第 8 章 图 96 = 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 1 0 0 Edge 第 7 章 图 7-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向 完全图中，边的条数为 n(n-1)/2。 【解答】 【证明】 在有 n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1 条边与其他 n-1 个顶点相连，总计 n 个顶点有 n(n-1)条边。但在无向图中，顶点 i 到顶点 j 与顶点 j 到顶 点 i 是同一条边，所以总共有 n(n-1)/2 条边。 7-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶 点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成 强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点 A 出发，到其他的各个顶点的简单路径有 A→B，A→D→B，A→B→C，A→D→B→C，A →D，A→B→E，A→D→E，A→D→B→E，A→B→C→F→E，A→D→B→C→F→E，A→B→C→F，A →D→B→C→F。 从顶点 B 出发，到其他各个顶点的简单路径有 B→C，B→C→F，B→E，B→C→F→E。 从顶点 C 出发，到其他各个顶点的简单路径有 C→F，C→F→E。 从顶点 D 出发，到其他各个顶点的简单路径有 D→B，D→B→C，D→B→C→F，D→E，D→B→E， D→B→C→F→E。 从顶点 E 出发，到其他各个顶点的简单路径无。 从顶点 F 出发，到其他各个顶点的简单路径有 F→E。 7-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 1 个顶点的 无向完全图 2 个顶点的 无向完全图 3 个顶点的 无向完全图 4 个顶点的 无向完全图 5 个顶点的 无向完全图 A B C D E F A B C D E F
第8章图 (2)邻接表 (出边表 5∧ 3D (入边表) ABCDEF -3B (3)邻接多重表(十字链表) data fin fout j ilink jlink 0A∧ 0 03∧∧ 4121(((((B.C) 2|5A 31 54A∧cE 7-4用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关? 【解答】 用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 7-5有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说 【解答】 个顶点的无向连通图至少有n1条边,n个顶点的有向强连通图至少有n条边。例如: 无向图 有向图
第 8 章 图 97 (2) 邻接表 (3) 邻接多重表（十字链表） 7-4 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 【解答】 用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数 与边的条数有关。 7-5 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说 明。 【解答】 n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。例如： 0 A 1 B 2 C 3 D 4 E 5 F 1 0 A 1 B 2 C 3 D 4 E 5 F 3 2 4 5 1 4 4 0 3 1 0 1 3 5 2 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ （出边表） （入边表） 0 A 1 B 2 C 3 D 4 E 5 F data fin fout i j ilink jlink 0 1 (A, B) 0 3 (A, D) 1 2 (B, C) 1 4 (B, E) 2 5 (C, F) 3 1 (D, B) 3 4 (D, E) 5 4 (F, E) ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧
第8章图 特例情况是当n=1时,此时至少有0条边 7-6对于有n个顶点的无向图,采用邻接矩阵表示,如何判断以下问题:图中有多少条边?任意两个顶 点i和j之间是否有边相连?任意一个顶点的度是多少? 【解答】 用邻接矩阵表示无向图时,因为是对称矩阵,对矩阵的上三角部分或下三角部分检测一遍,统计其 中的非零元素个数,就是图中的边数。如果邻接矩阵中A[订不为零,说明顶点i与顶点j之间有边相 连。此外统计矩阵第i行或第i列的非零元素个数,就可得到顶点i的度数。 7-7对于如右图所示的有向图,试写出: (1)从顶点①出发进行深度优先搜索所得到的深度优先生成树 (2)从顶点②出发进行广度优先搜索所得到的广度优先生成树 【解答】 (1)以顶点①为根的深度优先生成树(不唯一):②③④⑤⑥ 或 ③ (2)以顶点②为根的广度优先生成树: 7-8试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为 void Graph:DFS( const int v, int visited[. TreeNode*t)其中,指针t指向生成森林上具有图 顶点ⅴ信息的根结点。(提示:在继续按深度方向从根ⅴ的某一未访问过的邻接顶点w向下遍历之前, 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。) 【解答】 为建立生成森林,需要先给出建立生成树的算法,然后再在遍历图的过程中,通过一次次地调用这 个算法,以建立生成森林 te mplate void Graph: DFS Tree( const int v, int visited[, TreeNode *t)i ∥从图的顶点v出发,深度优先遍历图,建立以t(已在上层算法中建立)为根的生成树 ype p,q: int w=GetFirstNeighbor(v); ∥取第一个邻接顶点 while(wI=-1)t ∥若邻接顶点存在 该邻接结点未访问过 p= new TreeNode( Get Value(w)); ∥建立新的生成树结点 if first==1) ∥若根*还未链入任一子女 (t->set FirstChild(p): first=0; 新结点◆p成为根*的第一个子女 else q->setNextSibling(p); 否则新结点·p成为q的下一个兄弟
第 8 章 图 98 ① ② ③ ④ ⑤ 或 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ ① ② ③ ④ ⑤ 特例情况是当 n = 1 时，此时至少有 0 条边。 7-6 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶 点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？ 【解答】 用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其 中的非零元素个数，就是图中的边数。如果邻接矩阵中 A[i][j] 不为零，说明顶点 i 与顶点 j 之间有边相 连。此外统计矩阵第 i 行或第 i 列的非零元素个数，就可得到顶点 i 的度数。 7-7 对于如右图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 【解答】 (1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥ (2) 以顶点②为根的广度优先生成树： 7-8 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为 void Graph::DFS ( const int v, int visited [ ], TreeNode * t ) 其中，指针 t 指向生成森林上具有图 顶点 v 信息的根结点。（提示：在继续按深度方向从根 v 的某一未访问过的邻接顶点 w 向下遍历之前， 建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。） 【解答】 为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这 个算法，以建立生成森林。 te mplate void Graph :: DFS_Tree ( const int v, int visited [ ], TreeNode *t ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以 t (已在上层算法中建立)为根的生成树。 Visited[v] = 1; int first = 1; TreeNode * p, * q; int w = GetFirstNeighbor ( v ); //取第一个邻接顶点 while ( w != -1 ) { //若邻接顶点存在 if ( vosited[w] == 0 ) { //且该邻接结点未访问过 p = new TreeNode ( GetValue (w) ); //建立新的生成树结点 if ( first == 1 ) //若根*t 还未链入任一子女 { t->setFirstChild ( p ); first = 0; } //新结点*p 成为根*t 的第一个子女 else q->setNextSibling ( p ); //否则新结点*p 成为*q 的下一个兄弟
∥指针q总指示兄弟链最后一个结点 DFS_Tree(w, visited, q); ∥从向下建立子树 w= GetNextNeighbor (v, w ): 取顶点v排在邻接顶点w的下一个邻接顶点 下一个算法用于建立以左子女右兄弟链表为存储表示的生成森林 template void Graph: DFS Forest( Tree&T) ∥从图的顶点v出发,深度优先遍历图,建立以左子女右兄弟链表表示的生成森林T Troot= NULL; int n= NumberOfVertices ( ∥顶点个数 int*visited =new int [n ]:i ∥建立访问标记数组 for int v=0;v( Get Value(V)); ∥建立新结点*p if T root= NULL )T root=p ∥原来是空的生成森林,新结点成为根 else q->setNextSibling(p); 否则新结点p成为q的下一个兄弟 DFS Tree( v, visited, p ); ∥建立以·p为根的生成树 7-9用邻接表表示图时,顶点个数设为n,边的条数设为e,在邻接表上执行有关图的遍历操作时,时间 代价是On*e)?还是On+e)?或者是O(max(n,e)? 【解答】 在邻接表上执行图的遍历操作时,需要对邻接表中所有的边链表中的结点访问一次,还需要对所有 的顶点访问一次,所以时间代价是O(n+e) 10右图是一个连通图,请画出 (1)以顶点①为根的深度优先生成树 (2)如果有关节点,请找出所有的关节点 (3)如果想把该连通图变成重连通图,至少在图中加几条边? 如何加? 【解答】 (1)以顶点①为根的深度优先生成树:
第 8 章 图 99 q = p; //指针 q 总指示兄弟链最后一个结点 DFS_Tree ( w, visited, q ); //从*q 向下建立子树 } w = GetNextNeighbor ( v, w ); //取顶点 v 排在邻接顶点 w 的下一个邻接顶点 } } 下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。 template void Graph :: DFS_Forest ( Tree & T ) { //从图的顶点 v 出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林 T。 T.root = NULL; int n = NumberOfVertices ( ); //顶点个数 TreeNode * p, * q; int * visited = new int [ n ]; //建立访问标记数组 for ( int v = 0; v ( GetValue ( v ) ); //建立新结点*p if ( T.root == NULL ) T.root = p; //原来是空的生成森林, 新结点成为根 else q-> setNextSibling ( p ); //否则新结点*p 成为*q 的下一个兄弟 q = p; DFS_Tree ( v, visited, p ); //建立以*p 为根的生成树 } } 7-9 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的遍历操作时，时间 代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e))？ 【解答】 在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有 的顶点访问一次，所以时间代价是 O(n+e)。 7-10 右图是一个连通图，请画出 (1) 以顶点①为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节点。 (3) 如果想把该连通图变成重连通图，至少在图中加几条边？ 如何加？ 【解答】 (1) 以顶点①为根的深度优先生成树： ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨
第8章图 (2)关节点为①,②,③,⑦,⑧ 3)至少加四条边(1,10),(3,4,(4,5)(5,6)。从③的子孙结点⑩到③的祖先结点①引一条边,从② 的子孙结点④到根①的另一分支③引一条边,并将⑦的子孙结点⑤、⑥与结点④连结起来,可使其变为 重连通图 7-11编写一个完整的程序,首先定义堆和并查集的结构类型和 相关操作,再定义 Kruskal求连通网络的最小生成树算法的实 现。并以右图为例,写出求解过程中堆、并查集和最小生成树7 的变化 【解答】 求解过程的第一步是对所有的边,按其权值大小建堆: 127 面应4应d 山27[31d 加(1,2),(1,3) 血3山[249 加(2,4) 加(3,4) 山27 127Bs7 B山区249]2lio 加(3,5) 加(3,6) [249[23o368]加(5.6 血 求解过程中并查集与堆的变化: s66 ④⑥ 368
第 8 章 图 100 (2) 关节点为 ①,②,③,⑦,⑧ (3) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从③的子孙结点⑩到③的祖先结点①引一条边，从② 的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为 重连通图。 7-11 编写一个完整的程序，首先定义堆和并查集的结构类型和 相关操作，再定义 Kruskal 求连通网络的最小生成树算法的实 现。并以右图为例，写出求解过程中堆、并查集和最小生成树 的变化。 【解答】 求解过程的第一步是对所有的边，按其权值大小建堆： 求解过程中并查集与堆的变化： 1 3 11 ① ② ③ ④ ⑤ ⑥ 6 8 5 10 9 7 ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 1 2 7 1 3 11 2 3 10 1 2 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 2 3 10 2 4 9 加(1, 2), (1, 3), (2,3) 加(2, 4) 加(3, 4) 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 1 3 11 3 4 5 1 2 7 3 5 7 2 4 9 2 3 10 3 6 8 加(3, 5) 加(3, 6) 1 2 7 3 4 5 5 6 6 3 5 7 2 4 9 2 3 10 3 6 8 1 3 11 加(5, 6) ③ 5 6 6 1 2 7 3 5 7 ③ ④ ⑤ ⑥ 1 2 7 3 6 8 3 5 7
第8章图 选45国山国2图8]速6山区p]B 357 B3681 ②@Bd②E4 2310 选2n)血E 选(357)⑥[3山i ②④⑤ 2 ④ ⑥选(3.68),在同一连通分量上,不加②⑥选(24.9),结束 最后得到的生成树如下 6 并查集的存储表示 完整的程序如下 #include class MinHeap i enum i Maxheap Size=50; MinHeap( int Maxsize MaxHeap Size ) MinHeap( Type array[l int n ) void Insert( const Type &ele ) oid RemoveMin( Type &Min ) id Output (; private: void Filter Down( int start, int end ) void FilterUp( int end ) Type *pHe int Currentsize; class UFSets i enum i MaxUnionS UFSets( int MaxSize MaxUnionS ize ) UFSetsoi delete []m pArent; 3
第 8 章 图 101 最后得到的生成树如下 完整的程序如下: #include template class MinHeap { public: enum { MaxHeapSize = 50 }; MinHeap ( int Maxsize = MaxHeapSize ); MinHeap ( Type Array[ ], int n ); void Insert ( const Type &ele ); void RemoveMin ( Type &Min ); void Output (); private: void FilterDown ( int start, int end ); void FilterUp ( int end ); Type *pHeap; int HMaxSize; int CurrentSize; }; class UFSets { public: enum { MaxUnionSize = 50 }; UFSets ( int MaxSize = MaxUnionSize ); ~UFSets () { delete [ ] m_pParent; } 3 1 -6 3 3 5 1 3 11 3 5 7 2 4 9 3 6 8 2 3 10 ① ② ③ ④ ⑤ ⑥ 6 7 7 5 9 ④ 选(3,4,5) 1 3 11 2 4 9 2 3 10 3 6 8 选(5,6,6) 1 3 11 2 4 9 2 3 10 ③ ④ ⑤ ⑥ 选(1,2,7) ① ② ③ ④ ⑤ 选(3,5,7) ⑥ ① ② 1 3 11 2 4 9 2 3 10 3 6 8 ③ ④ ⑤ ⑥ 选(3,6,8), 在同一连通分量上, 不加 ① ② 1 3 11 2 3 10 2 4 9 ③ ④ ⑤ ⑥ 选(2,4,9), 结束 ① ② 1 3 11 2 3 10 0 1 2 3 4 5 6 并查集的存储表示
第8章图 ); int Find( int x ) rivate at m sIze: class Graph enum Max VerticesNum=50: Graph( int Vertices=0) Current Vertices= Vertices; InitGraph0; 3 void Kruskal O int Get Vertices(i return Current Vertices; 3 private: int Current Vertices } class GraphEdge i t head, tail int cost; int operator cost =0)x=m_pArent(x]:
第 8 章 图 102 void Union ( int Root1, int Root2 ); int Find ( int x ); private: int m_iSize; int *m_pParent; }; class Graph { public: enum { MaxVerticesNum = 50 }; Graph( int Vertices = 0) { CurrentVertices = Vertices; InitGraph(); } void InitGraph (); void Kruskal (); int GetVerticesNum () { return CurrentVertices; } private: int Edge[MaxVerticesNum][MaxVerticesNum]; int CurrentVertices; }; class GraphEdge { public: int head, tail; int cost; int operator cost = 0 ) x = m_pParent[x]; return x;
第8章图 template MinHeap: MinHeap( int Maxsize)( pHeap=new Type [HMax Size]; template MinHeap:: MinHeap( Type Array, int n)& pHeap=new Type [HMaxSize]: for( int i=0; i =0)i FilterDown( iPos, Currentsize ) template void MinHeap: Filter Down( int start, int end)i int i=star,j=2 start +1; Type Temp= pHeap[] if(j void MinHeap: FilterUp( int end )i 1)/2; if( pHeap[l <=Temp )break; i=j;j=(j-1)/2; pHeapi= Temp
第 8 章 图 103 } template MinHeap :: MinHeap ( int Maxsize ) { HMaxSize = Maxsize; pHeap = new Type[HMaxSize]; CurrentSize = -1; } template MinHeap :: MinHeap ( Type Array[], int n ) { HMaxSize = ( n = 0 ) { FilterDown ( iPos, CurrentSize ); iPos--; } } template void MinHeap :: FilterDown ( int start, int end ) { int i = start, j = 2 * start + 1; Type Temp = pHeap[i]; while ( j void MinHeap :: FilterUp ( int end ) { int i = end, j = ( end - 1 ) / 2; Type Temp = pHeap[i]; while ( i > 0 ) { if ( pHeap[j] <= Temp ) break; pHeap[i] = pHeap[j]; i = j; j = ( j - 1 ) / 2; } pHeap[i] = Temp; }
第8章图 template void MinHeap: Insert( const Type &ele )i Currents ize++; if( CurrentSize ==HMaxsSize )return FilterUp( Currentsize ) template void MinHeap: RemoveMin( Type &Min)i if( Currentsize void MinHeap: Output(( for ( int 1=0; i heap( VerticesNum"VerticesNum ) for (i=0; 1< Vertices Num; i++) for(j=i+l;j<VerticesNum: j++) e head =i;e tail =j;ecost=Edge[[]: heap. Insert(e )
第 8 章 图 104 template void MinHeap :: Insert ( const Type &ele ) { CurrentSize++; if ( CurrentSize == HMaxSize ) return; pHeap[CurrentSize] = ele; FilterUp ( CurrentSize ); } template void MinHeap :: RemoveMin ( Type &Min ) { if ( CurrentSize void MinHeap :: Output ( ) { for ( int i = 0; i heap ( VerticesNum *VerticesNum ); UFSets set ( VerticesNum ); for ( i = 0; i 0 ) { e.head = i; e.tail = j; e.cost = Edge[i][j]; heap.Insert ( e );
第8章图 while( count VerticesNum)t heap. RemoveMin(e); (e. head ) j=set. Find( e. tail ) set Union(1j); cout<<"("<<ehead <<","<<e tail <<", "< ecost <<")<<endl; 7-12利用 Dijkstra算法的思想,设计一个求最小生成树的算法 【解答】 计算连通网络的最小生成树的 Dijkstra算法可描述如下:将连通网络中所有的边以方便的次序逐步 加入到初始为空的生成树的边集合T中。每次选择并加入一条边时,需要判断它是否会与先前加入T的 边构成回路。如果构成了回路,则从这个回路中将权值最大的边退选, 下面以邻接矩阵作为连通网络的存储表示,并以并查集作为判断是否出现回路的工具,分析算法的 执行过程 ①②③④⑤⑥ 06 01811④ 026⑤ 14 并查集,表明4 个结点在同 ③④⑥ 连通分量上 最终得到的最小生成树为
第 8 章 图 105 } count = 1; while ( count < VerticesNum ) { heap.RemoveMin ( e ); i = set.Find ( e.head ); j = set.Find ( e.tail ); if ( i != j ) { set.Union ( i, j ); count++; cout << "( " << e.head << ", " << e.tail << ", " << e.cost << " )" << endl; } } } 7-12 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。 【解答】 计算连通网络的最小生成树的 Dijkstra 算法可描述如下：将连通网络中所有的边以方便的次序逐步 加入到初始为空的生成树的边集合 T 中。每次选择并加入一条边时，需要判断它是否会与先前加入 T 的 边构成回路。如果构成了回路，则从这个回路中将权值最大的边退选。 下面以邻接矩阵作为连通网络的存储表示，并以并查集作为判断是否出现回路的工具，分析算法的 执行过程。 最终得到的最小生成树为 ① ② ⑤ ④ ⑥ ③ 18 14 16 26 21 19 11 9 5 6 − − − − − − − − − − − − − − − = 0 0 26 0 18 11 0 6 0 5 9 19 0 16 14 21 Edge ① ② ③ ④ ⑤ ⑥ ① ② ③ ④ ⑤ ⑥ ① ② ⑤ ④ 14 ⑥ ③ 16 21 ① ② ⑤ ⑥ 并查集, 表明 4 个结点在同一 连通分量上 ① ② ⑤ ④ 14 ⑥ ③ 16 21 ① ② ⑤ ⑥ 19 9 5 ③ ④ ① ② ⑤ ④ 14 ⑥ ③ 16 ① ② ⑤ ⑥ 5 ③ ④ 19 9 6 ① ② ⑤ ④ 14 ⑥ ③ 16 ① ② ⑤ ⑥ 5 ③ 6 ④ 19 11 ① ② ⑥ ③ 16 5 6
