【正文】 可以利用深度優(yōu)先生成樹找到。 ?在重連通圖上 , 任何一對頂點之間至少存在有兩條路徑 , 在刪去某個頂點及與該頂點相關(guān)聯(lián)的邊時 , 也不破壞圖的連通性。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?重連通分量 (Biconnected Component) ?在無向連通圖 G中 , 當(dāng)且僅當(dāng)刪去 G中的頂點 v及所有依附于 v的所有邊后 , 可將圖分割成兩個或兩個以上的連通分量，則稱頂點 v為 關(guān)節(jié)點 。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?克魯斯卡爾 (Kruskal)算法 求最小生成樹 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 原圖 (a) (b) 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 10 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 14 12 原圖 (c) (d) 5 0 4 6 1 3 2 10 14 16 12 (e) (f) (g) 5 0 4 6 1 3 2 10 14 22 16 12 5 0 4 6 1 2 10 25 14 22 16 12 3 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?普里姆算法與克魯斯卡爾算法 比較 ?普里姆算法的時間復(fù)雜度為 O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊 稠密 的網(wǎng)的最小生成樹。 ?依次類推，直至于中所有頂點都在同一連通分量上為止。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?克魯斯卡爾 (Kruskal)算法 求最小生成樹 ?基本思想： ?假設(shè)連通網(wǎng) N=(V， {E})，則令最小生成樹的初始狀態(tài)為只有 n個頂點而無邊的非連通圖 T=(V， {})，圖中每個頂點自成一個連通分量。 ++j) if ([k][j].adjclosedge[j].lowcost) closedge[j]={[k],[k][j].adj}。 //第 k頂點并入 U集 for (j=0。 //{adjvex , lowcost} 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?closedge[k].lowcost =0； //初始， U={u} for ( i=1； i； ++i){ //選擇其余 k=minimum(closedge)； printf(closedge[k].adjvex, [k])。 ?存儲表示： ?鄰接矩陣 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 25 25 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 原圖 (a) (b) 5 0 4 6 1 3 2 10 (c) (d) (e) 5 0 4 6 1 3 2 10 22 12 5 0 4 6 1 2 10 25 14 22 16 12 3 25 22 12 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?以二維數(shù)組表示網(wǎng)的鄰接矩陣，令兩個頂點之間不存在的邊的權(quán)值為機(jī)內(nèi)允許的最大值 (INT_MAX)，則普里姆算法如下： ?//記錄從頂點集 U到 V— U的代價最小的邊的輔助數(shù)組定義： struct{ VertexType adjvex； VRType lowcost； }closedge[ MAX_VERTEX_NUM ] void MiniSpanTree_PRIM (MGraph G， VertexType u){ //用普里姆算法從第 u個頂點出發(fā)構(gòu)造網(wǎng) G的最小生成樹 T，輸出 T的各條邊。 ?以后每一步從一個頂點在 U 中 ,而另一個頂點不在 U 中的各條邊中選擇權(quán)值最小的邊 (u, v), 把它的頂點加入到集合 U 中。由此和假設(shè)矛盾。刪去邊 (u’, v’)，便可消除上述回路，同時得到另一棵生成樹 T。 ?設(shè) T是連通網(wǎng)上的一棵最小生成樹，當(dāng)將邊 (u， v)加入到 T中時，由生成樹的定義， T中必存在一條包含 (u , v)的回路。若 (u， v)是一條具有最小權(quán)值 (代價 )的邊，其中 u ∈U ， v∈V U，則必存在一棵包含邊 (u，v)的最小生成樹。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?背景知識（突破點） —— 構(gòu)造最小生成樹可以有多種算法。這個問題就是構(gòu)造連通網(wǎng)的最小代價生成樹 (簡稱為最小生成樹 )的問題。 ?對于 n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)。 ?在每兩個城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價。 //建立以 p為根的生成樹 } }//DFSForest 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?最小生成樹（ Minimum Cost Spanning Tree） ?問題背景 ?假設(shè)要在 n個城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通 n個城市只需要 n— 1條線路。 //是其它生成樹的根 (前一棵的根的 “ 兄弟 ” ) q = p。T){ //建立無向圖 G的深度優(yōu)先生成森林的 (左 )孩子 (右 )兄弟鏈表 T。 ?對非連通圖，則需從多個頂點出發(fā)進(jìn)行搜索，而每一次從一個新的起始點出發(fā)進(jìn)行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。 //對 v的尚未訪問的鄰接點 w遞歸調(diào)用DFS if (!found) Delete (PATH)。 Append(PATH, w)。!found。 w!=0amp。 // 訪問第 v個頂點 Append(PATH, getVertex(v))。 }//if }//while }//if }//BFSTraverse 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的遍歷應(yīng)用舉例： 求一條從頂點 i到頂點 s 的簡單路徑。 Visit(w)。 w。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。 w =NextAdjVex(G, v, w)) if(!visited[w]) DFS(G， w)； //對 v的尚未訪問的鄰接頂點 w 遞歸調(diào)用 DFS }// END of DFS 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的廣度優(yōu)先搜索 ?(Breadth_FirstSearch)遍歷類似于樹的按層次遍歷的過程。 //訪問標(biāo)志初始化 for(v=0； v； ++v) if( !visited[v] ) DFS(G， v)； //對尚未訪問的頂點調(diào)用 DFS } //END of DFST 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的深度優(yōu)先搜索算法 ? void DFS (Graph G， int v){ //從第 v個頂點出發(fā)遞歸地深度優(yōu)先 遍歷圖 G visited[v]=TRUE； VisitFunc(v)； //訪問第 v個頂點 for(w =FirstAdjVex(G, v)。 VisitFunc=Visit。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的深度優(yōu)先搜索 ?遍歷圖－－對每個頂點查找其鄰接點。 ?通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。 ?為了避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點。在鄰接多重表中，每一條邊用一個結(jié)點表示，由如下所示的六個域組成： 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的存儲結(jié)構(gòu) ?圖的鄰接多重表表示法： 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的遍歷 ?(Traversing Graph）是從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。因此，在進(jìn)行這一類操作的無向圖的問題中采用鄰接多重表作存儲結(jié)構(gòu)更為適宜。在鄰接表中每一條邊 (vi , vj)有兩個結(jié)點，分別在第 i個和第 j個鏈表中，這給某些圖的操作帶來不便。在十字鏈表中，對應(yīng)有向圖每個弧有一個結(jié)點，對應(yīng)于每個結(jié)點也有一個結(jié)點。在表頭結(jié)點中，除了設(shè)有鏈域 (firstarc)指向鏈表中第一個結(jié)點之外，還設(shè)有存儲頂點 vi的名或其它有關(guān)信息的數(shù)據(jù)域 (data)。 ?每個結(jié)點由三個域組成，其中鄰接點域 (adjvex)指示與頂點 vi鄰接的點在圖中的位置，鏈域 (nextarc)指示下一條邊或弧的結(jié)點；數(shù)據(jù)域 (info)存儲和邊或弧相關(guān)的信息，如權(quán)值等。 南昌航空大學(xué)計算機(jī)學(xué)院 /軟件學(xué)院 第 7章 圖 圖的存儲結(jié)構(gòu) ?圖的鄰接表表示法 ? 鄰接表 (AdjacencyList)是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。對無權(quán)圖，用 1或 0表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。 ?有向圖的鄰接矩陣的第 i行（或第 i列）非零元素（或非 ∞ 元素）的個數(shù)正好是第 i個頂點的出度 OD(vi)（或入度 ID(vi)） ?用鄰接矩陣方法存儲圖，容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進(jìn)行檢測，所花費的時間代價很大。在具體存放鄰接矩陣時只需存放上（或下）三角矩陣的元素即可。 ?它采用兩個數(shù)組來表示圖：一個是用于存儲頂點信息的一維數(shù)組，另一個是用于存儲圖中頂點之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個關(guān)聯(lián)