【正文】 1 F 1 G 1 H 1 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 0 F 1 G 2 H 1 要將 AE， CG相連 只要將 E的雙親改為 0， G的雙親改為 2 A B C D E F G H 0 1 2 3 4 5 6 7 A 1 B 1 C 1 D 1 E 0 F 1 G 2 H 1 0 1 2 3 4 5 6 7 A 1 B 1 C 0 D 1 E 0 F 1 G 2 H 1 現(xiàn)在要加入邊 EG使連通度減?。? 先查 E所在分支的根， E的雙親是 0，即 A點， A的雙親是 1， A是根。 同一分支的結點聯(lián)成一棵樹。 重復以下步驟，直至 T連通： 取出最小邊，判斷這條邊的兩個端點，如果屬于T的不同的連通分支，加入 T, 把兩分支聯(lián)成一個。 } Kruskal 克魯斯卡爾算法 G=(V,E) 連通圖 令 T=(V,{ }) 是 G的所有頂點而無邊的非連通圖。 } } } } void main( ) { Graphchar G。 if(l0amp。 //將 w加進 U for( j=0。//取出這一邊 w=GetVertex(G,k)。 } for( i=1。 l=(v,w)。 closeEdge[0].lowcost=0。 } templateclass T void MiniSpanTreePrim(Graph T G) { int j,k,l,n=( )。amp。 return 0。a[i]a[min]) min=i 。 for(i=min+1。 } template class T int minimum(MiniCostEdgeInfoT *a,int n) { for(int i=0。 T中共有 n1條邊 D B C A E F H 10 28 25 22 12 16 18 14 24 D B C A E F H 10 28 25 22 12 16 18 14 24 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D 6 5 3 6 4 5 2 1 5 6 U={A}, T={(A,C)} U={A,C}, T={(A,C),(C,F)} U={A,C,F}, T={(A,C),(C,F),(D,F)} U={A,C,F,D}, T={(A,C),(C,F),(D,F),(B,C)} U={A,C,F,D,B}, T={(A,C),(C,F),(D,F),(B,C),(B,E)} U={A,C,F,D,B,E} C B E A F D 6 5 3 6 4 5 2 1 5 6 A B C D E F U T 0 A 6 A 1 A 5 A (A,C) C 5 0 C 6 C 4 C (C,F) C 5 F 2 C 6 0 F (D,F) 0 D (B,C) 0 B 3 B (B,E) 0 E 定義數(shù)組 closeEdge[n] 紀錄每點到 U的最短距離 (點，距離 ) U中點距離為 0， 每加入一個新點， 數(shù)組更新一次 templateclass T struct MiniCostEdgeInfo { T adjvex。 } PrintList(scList)。 for (( )。 !( )。 template class T void ConnectedComponent (GraphT amp。 cout endl。 for(( )。 !( )。 } template class T void UConnectedComponent (GraphT amp。G, T v, T w) { SeqListT L。 for (( )。 從一點出發(fā)，深度優(yōu)先或廣度優(yōu)先搜索到的子圖就是 連通分量。!( )。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 T vertex。 Graph T ::BreadthFirstSearch( const T amp。 } } return *L。 (adjL)。 (beginVertex)。 SeqListT *L, adjL。 //輸出頂點 StackT S。 LInsert(vertex)。 GraphT::DFS(const int v, int *visited) { SeqListT*L。 *L=DFS(0,visited)。 for(int i=0。 }。 } ( )。 vertex) { SeqListIteratorT iter(L)。 return。 } template class T void GraphT::DeleteEdge(const Tamp。row graphsize。row++) for (col = pos + 1。col graphsize。 graphsize。 int row, col。 } edge[pos1][pos2] = weight。 vertex1, const Tamp。 graphsize++。 } template class T void GraphT::InsertVertex(const Tamp。 } for(int i = v1+1。 i++) if(edge[v][i] 0) return i。 } template class T int GraphT::GetFirstNeighbor(const int v) {if (v 0||vgraphsize) { cerr “The vertex is not in the graph. endl。 i graphsize。 int pos = GetVertexPos(vertex)。 GraphT::GetNeighbors(const Tamp。 if (pos1 == 1 || pos2 == 1) { cerr GetWeight: a vertex is not in the graph. endl。 } return pos。 ( ) != vertex) { pos++。 vertex) { SeqListIteratorT liter(vertexList)。 } ( )。 i++) { f S1。 InsertVertex(S1)。 } f nvertices。 ifstream f。 (“”)。 j MaxGraphSize。 }。 beginVertex)。 DepthFirstSearch(const Tamp。 DFS( )。 vertex1, const Tamp。 vertex2, int weight)。 // graph modification methods void InsertVertex(const Tamp。 GetNeighbors(const Tamp。 int GetWeight(const Tamp。 A B public: ALGraph(void)。L, const Tamp。 EdgeT *firstedge。 EdgeT *next。 }。 int MinimumPath(const Tamp。 beginVertex)。 SeqListTamp。 vertex2)。 void DeleteVertex(const Tamp。 vertex)。 vertex)。 vertex1, const Tamp。 int GraphEmpty(void) const。 vertex)。 int edge [MaxGraphSize][MaxGraphSize]。 二、圖的存儲結構 用矩陣表示圖的頂點之間的相鄰關系。 連通圖的 生成樹 含有所有頂點的極小 連通圖 n個頂點盡可能少邊的連通圖有 n1條邊。 稀疏圖 |E|nlog n 稠密圖 |E|nlog n 帶權邊 具有邊長的邊 有權圖 圖的所有邊都是帶權邊。 圖的基本概念 路徑 vi,vn} 頂點 集 E={ (vi, vj) | vi,vj∈ V, vi≠vj} 邊 集 無向圖 E={vi, vj|vi , vj∈ V}有向邊 集 有向圖 有向邊 vi, vj ， vi起點 弧尾， vj終點 弧頭 TD(vi): 一個頂點的 度 ,以 vi為端點的邊的數(shù)目。? 圖 ? 圖的存儲表示 ? 圖的遍歷 ? 無向圖的連通分量和生成樹 ? 最短路徑 ? 拓撲排序 一、圖 圖 應用最廣泛的數(shù)據(jù)結構。 TD(vi)= OD(vi)+ ID(vi) OD=ID, TD=2|E|， |E| =1/2*TD TD OD ID 為整個圖的總度 ,出度 ,入度數(shù)。 路徑的長 路徑上邊的數(shù)目， 簡單路徑 頂點都不重復的路徑， 回路 環(huán) 首尾相接的路徑， 簡單回路 除第一個和最后一個頂點以外都不重 復的路徑， vivj連通 有路徑 vi 無向完全圖 共有邊 1/2(n*(n1)) 條 , 有向完全圖 共有邊 n(n1) 條。 強連通分量 一個圖的極大強連通子圖。 有向圖的 生成森林： 有向圖的一個子圖，含有所有頂點，構成若干互不相交的有向樹，叫做生成森林。 template class T class Graph { SeqListT vertexList。L, const Tamp。 public: Graph(void)。 int GetWeight(const Tamp。 GetNeighbors(const Tamp。 // graph modification methods void InsertVertex(const Tamp。 vertex2, int weight)。 vertex1, const Tamp。 DFS( )。 DepthFirstSearch(const Tamp。 beginVertex)。 // iterator used to scan the vertices friend class VertexIteratorT。 //第二個頂點的編號 int weight。 adj w templateclass T struct VNode { T vertex。 int FindVertex(SeqListT amp。 vertex)。 int Num