【正文】 2(G)，則包含 V的強連通分量的頂點集合是 ： T1(G)∩T2(G) 。 有向圖的強連通分量 對于有向圖，在其每一個 強連通分量中 ， 任何兩個頂點都是可達的 。 ⑵ 若 G=(V,E)是無向非連通圖 ， 對圖進行遍歷時得到若干個連通分量的頂點集 ： V1(G) ,V2(G) ,… ,Vn(G)和相應(yīng)所經(jīng)過的邊集 ： T1(G) ,T2(G) , … ,Tn(G) 則對應(yīng)的頂點集和邊集的二元組： Gi=(Vi(G),Ti(G)) (1≦ i≦ n)是對應(yīng)分量的生成樹 ，所有這些 生成樹構(gòu)成了原來非連通圖的生成森林 。 G’稱為圖 G的一棵生成樹 。若從 G中 任意點出發(fā)遍歷時， E(G)被分成兩個互不相交的集合： T(G) ：遍歷過程中所 經(jīng)過的邊 的集合； B(G) ：遍歷過程中 未經(jīng)過的邊 的集合； 顯然： E(G)=T(G)∪ B(G) ， T(G)∩B(G)=216。 無向圖的連通分量與生成樹 1 無向圖的連通分量和生成樹 對于無向圖，對其進行遍歷時： ◆ 若是 連通圖 ：僅需從圖中 任一頂點出發(fā) ，就能訪問圖中的所有頂點； ◆ 若是 非連通圖 ：需從圖中 多個頂點出發(fā) 。 3 算法分析 用 廣度優(yōu)先搜索算法 遍歷圖與 深度優(yōu)先搜索算法遍歷圖的 唯一區(qū)別 是 鄰接點搜索次序不同 ，因此， 廣度優(yōu)先搜索算法 遍歷圖的總時間復雜度為 O(n+e) 。上述圖的 BFS次序是 ： v1→ v2 → v4 → v3 → v5 (b) G’的正鄰接鏈表 1 3 ? 0 1 4 ? 2 ? 3 ? 0 1 2 3 4 MAX_VEX1 v1 2 v2 0 ? v3 3 v4 1 ┇ ┇ ┇ v5 1 圖 718 有向圖廣度優(yōu)先搜索遍歷 (a) 有向圖 G’ v1 v2 v3 v4 v5 2 算法實現(xiàn) 為了標記圖中頂點是否被訪問過，同樣需要一個訪問標記數(shù)組；其次，為了依此訪問與 vi相鄰接的各個頂點 ，需要附加一個隊列來保存訪問 vi的相鄰接的頂點。 1 算法思想 設(shè)初始狀態(tài)時圖中的所有頂點未被訪問，則： ⑴ 從圖中某個頂點 vi出發(fā) ，訪問 vi； ⑵ 訪問 vi的所有相 鄰接且未被訪問的所有頂點 vi1， vi2， … ，vim； ⑶ 以 vi1， vi2， … ， vim的次序 ，以 vij(1≦ j≦ m)依此作為vi ，轉(zhuǎn)⑴； ⑷ 繼續(xù)選取圖中 未被訪問 頂點 vk作為起始頂點 ，轉(zhuǎn)⑴，直到圖中所有頂點都被訪問為止。當圖有 e條邊，其時間復雜度為 O(e)，總時間復雜度為 O(n+e) 。 代碼詳見 P169 2 算法實現(xiàn) 3 算法分析 遍歷時，對圖的每個頂點至多調(diào)用一次 DFS函數(shù)。某種 DFS次序是 ： v1→ v3 → v2 → v4 → v5 由算法思想知，這是一個遞歸過程。 1 算法思想 設(shè)初始狀態(tài)時圖中的所有頂點未被訪問，則： ⑴ 從圖中某個頂點 vi出發(fā) ，訪問 vi；然后找到 vi的 一個鄰接頂點 vi1 ； ⑵ 從 vi1出發(fā)，深度優(yōu)先搜索訪問和 vi1相 鄰接且未被訪問的所有頂點； ⑶ 轉(zhuǎn)⑴ ，直到和 vi相 鄰接的所有頂點都被訪問為止 ⑷ 繼續(xù)選取圖中未被訪問頂點 vj作為起始頂點，轉(zhuǎn) (1)，直到圖中所有頂點都被訪問為止。采用的數(shù)據(jù)結(jié)構(gòu)是 (正 )鄰接鏈表 。設(shè)置一個輔助向量 Visited[1… n](n為頂點數(shù) )，其初值為 0，一旦訪問了頂點 vi后，使 Visited[i]為 1或為訪問的次序號 。 ◆ 復雜性： 圖的任意頂點可能和其余的頂點相鄰接，可能在訪問了某個頂點后，沿某條路徑搜索后又回到原頂點。 圖 715 無向圖及其多重鄰接鏈表 v1 v2 v3 v4 v1 v2 v3 v4 0 1 2 3 0 1 0 2∧ 2 1∧ 2 3 0∧ 3∧ 結(jié)構(gòu)體定義，詳見 P166167 圖的遍歷 圖的遍歷 (Travering Graph)：從圖的某一頂點出發(fā)，訪遍圖中的其余頂點，且每個頂點僅被訪問一次。 鄰接多重表的結(jié)構(gòu)和十字鏈表類似， 每條邊用一個結(jié)點表示 ；鄰接多重表中的頂點結(jié)點結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點包括六個域如圖 714所示。 弧結(jié)點 tailvex headvex info hlink tlink 頂點結(jié)點 Data firstin firstout 圖 712 十字鏈表結(jié)點結(jié)構(gòu) ◆ data域：存儲和頂點相關(guān)的信息； ◆ 指針域 firstin：指向 以該頂點為弧頭 的第一條弧所對應(yīng)的弧結(jié)點； ◆ 指針域 firstout：指向 以該頂點為弧尾 的第一條弧所對應(yīng)的弧結(jié)點； ◆ 尾域 tailvex：指示弧尾頂點在圖中的位置； ◆ 頭域 headvex：指示弧頭頂點在圖中的位置； ◆ 指針域 hlink：指向弧頭相同的下一條弧； ◆ 指針域 tlink：指向弧尾相同的下一條?。? ◆ Info域：指向該弧的相關(guān)信息； V0 V1 V2 V3 0 1 0 2 ∧ 2 0 2 3 ∧∧ 3 0 ∧ 3 1 ∧ 3 2 ∧∧ 0 2 1 3 V0 V1 ∧ V2 V3 圖 713 有向圖的十字鏈表結(jié)構(gòu) 有向圖的十字鏈表結(jié)構(gòu) 結(jié)構(gòu)體定義，詳見 P165 鄰接多重表 鄰接多重表 (Adjacency Multilist)是無向圖的另一種鏈式存儲結(jié)構(gòu)。 在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點和弧尾結(jié)點都存放在鏈表中，并將 弧結(jié)點 分別組織到 以弧尾結(jié)點為頭(頂點 )結(jié)點 和 以弧頭結(jié)點為頭 (頂點 )結(jié)點 的鏈表中。 圖 710 無向圖及其鄰接鏈表 v1 v2 v3 v4 v5 0 1 2 3 4 MAX_VEX1 v1 v2 v3 v4 ┇ ┇ v5 2 1 3 ? 0 2 ? 0 3 1 4 ? 2 0 4 ? 2 3 ? (a) 有向圖 v1 v2 v3 v4 v5 1 3 ? 0 1 4 ? 2 ? 3 ? 0 1 2 3 4 MAX_VEX1 v1 2 v2 0 ? v3 3 v4 1 ┇ ┇ ┇ v5 1 (b) 正鄰接鏈表，出度直觀 2 ? 0 2 ? 2 ? 0 1 2 3 4 MAX_VEX1 v1 1 v2 2 v3 1 v4 2 ┇ ┇ ┇ v5 1 3 ? 0 4 ? (c) 逆鄰接鏈表，入度直觀 圖 711 有向圖及其鄰接鏈表 結(jié)構(gòu)體定義，詳見 P163 鄰接表法的特點 ◆ 表頭向量中每個分量就是一個單鏈表的頭結(jié)點，分量個數(shù)就是圖中的頂點數(shù)目； ◆ 在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間； ◆ 在無向圖，頂點 Vi的度是第 i個鏈表的結(jié)點數(shù)； ◆ 對 有向圖 可以建立 正鄰接表 或 逆鄰接表 。 鏈域 (firstarc)指向鏈表中的第一個結(jié)點， 數(shù)據(jù)域 (data) 存儲頂點名或其他信息。對于無權(quán)圖，如果沒有與邊相關(guān)的其他信息，可省略此域。 1 結(jié)點結(jié)構(gòu)與鄰接鏈表示例 鏈表中的結(jié)點稱為 表結(jié)點 ，每個結(jié)點由三個域組成，如圖79(a)所示。每一個單鏈表設(shè)一個表頭結(jié)點。 /* 是無向圖或帶權(quán)的無向圖 ,需對稱賦值 */ } return(1) 。 Gadj[k][j].ArcInfo=arcArcInfo 。 /* 是有向圖或帶權(quán)的有向圖 */ } else { Gadj[k][j].ArcVal=arcArcVal 。 } if (Gkind==DG||Gkind==WDG) { Gadj[k][j].ArcVal=arcArcVal。 if (k==1||j==1) { printf(“Arc’s Vertex do not existed !\n”) 。 j=LocateVex(G , amp。 k=LocateVex(G , amp。 } (4) 向圖中增加一條弧 根據(jù)給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應(yīng)的數(shù)組元素。 Gadj[k][j].ArcVal=INFINITY 。 jGvexnum 。 j++) Gadj[j][k].ArcVal=Gadj[k][j].ArcVal=0 。 if (Gkind==DG||Gkind==AG) for (j=0 。 } k=Gvexnum 。 } if (LocateVex(G , vp)!=1) { printf(“Vertex has existed !\n”) 。 if (Gvexnum=MAX_VEX) { printf(“Vertex Overflow !\n”) 。 /* 圖中無此頂點 */ } (3) 向圖中增加頂點 向圖中增加一個頂點的操作，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。 k++) if (Gvexs[k]==*vp) return(k) 。 for (k=0 。 } (2) 圖的頂點定位 圖的頂點定位操作實際上是確定一個頂點在 vexs數(shù)組中的位置 (下標 ) ，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素。 Gvexnum=0 。 scanf(“%d”, amp。 /* 圖的結(jié)構(gòu)定義 */ 利用上述定義的數(shù)據(jù)結(jié)構(gòu)，可以方便地實現(xiàn)圖的各種操作。 /* 頂點向量 */ ArcCell arcs[MAX_VEX][MAX_VEX]。 /* 圖的種類標志 */ int vexnum , arum 。 /* 弧或邊的其它信息 */ }ArcCell 。 /* {有向圖，無向圖，帶權(quán)有向圖，帶權(quán)無向圖 } */ typedef struct ArcCell { VRType adj 。 3 圖的鄰接矩陣的操作 圖的鄰接矩陣的實現(xiàn)比較容易，定義兩個數(shù)組分別存儲 頂點信息 (數(shù)據(jù)元素 )和 邊或弧的信息 (數(shù)據(jù)元素之間的關(guān)系 ) 。其元素的定義如下： wij 若 vi,vj?E，即 vi , vj鄰接，權(quán)值為 wij ∞ 若 vi,vj?E，即 vi , vj不鄰接時 A[i][j]= 圖 78 帶權(quán)有向圖的數(shù)組存儲 (b) 頂點矩陣 vexs a b c d e (c) 鄰接矩陣 ∞ 6 2 ∞ ∞ ∞ ∞ ∞ ∞ 3 ∞ 3 ∞ 1 ∞ ∞ 4 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ (a) 帶權(quán)有向圖 3 5 4 1 2 6 a b c d e 3 有向圖鄰接矩陣的特性： ◆ 對于頂點 vi，第 i行的非 0元素的個數(shù)是其 出度OD(vi)；第 i列的非 0元素的個數(shù)是其 入度 ID(vi) 。 2 有向圖 無權(quán)圖的鄰接矩陣