【文章內(nèi)容簡(jiǎn)介】 一條弧所對(duì)應(yīng)的弧結(jié)點(diǎn)； ◆ 尾域 tailvex：指示弧尾頂點(diǎn)在圖中的位置； ◆ 頭域 headvex：指示弧頭頂點(diǎn)在圖中的位置； ◆ 指針域 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)體定義，詳見(jiàn) P165 鄰接多重表 鄰接多重表 (Adjacency Multilist)是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 鄰接表是無(wú)向圖的一種有效的存儲(chǔ)結(jié)構(gòu)，在無(wú)向圖的鄰接表中，一條邊 (v,w)的兩個(gè)表結(jié)點(diǎn)分別初選在以 v和 w為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會(huì)帶來(lái)不便。 鄰接多重表的結(jié)構(gòu)和十字鏈表類似， 每條邊用一個(gè)結(jié)點(diǎn)表示 ；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個(gè)域如圖 714所示。 data firstedge 頂點(diǎn)結(jié)點(diǎn) 圖 714 鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu) 表結(jié)點(diǎn) mark ivex ilink jvex jlink info ◆ Data域：存儲(chǔ)和頂點(diǎn)相關(guān)的信息； ◆ 指針域 firstedge：指向依附于該頂點(diǎn)的第一條邊所對(duì)應(yīng)的表結(jié)點(diǎn)； ◆ 標(biāo)志域 mark：用以標(biāo)識(shí)該條邊是否被訪問(wèn)過(guò)； ◆ ivex和 jvex域：分別保存該邊所依附的兩個(gè)頂點(diǎn)在圖中的位置； ◆ info域：保存該邊的相關(guān)信息； ◆ 指針域 ilink：指向下一條依附于頂點(diǎn) ivex的邊； ◆ 指針域 jlink：指向下一條依附于頂點(diǎn) jvex的邊； 鄰接多重表與鄰接表的區(qū)別 ： 后者的同一條邊用兩個(gè)表結(jié)點(diǎn)表示，而前者只用一個(gè)表結(jié)點(diǎn)表示 ； 除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實(shí)現(xiàn)也基本相似。 圖 715 無(wú)向圖及其多重鄰接鏈表 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)體定義，詳見(jiàn) P166167 圖的遍歷 圖的遍歷 (Travering Graph)：從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問(wèn)一次。圖的遍歷算法是各種圖的操作的基礎(chǔ)。 ◆ 復(fù)雜性： 圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問(wèn)了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。 ◆ 解決辦法： 在遍歷過(guò)程中記下已被訪問(wèn)過(guò)的頂點(diǎn)。設(shè)置一個(gè)輔助向量 Visited[1… n](n為頂點(diǎn)數(shù) )，其初值為 0，一旦訪問(wèn)了頂點(diǎn) vi后，使 Visited[i]為 1或?yàn)樵L問(wèn)的次序號(hào) 。 圖的遍歷算法有 深度優(yōu)先搜索算法 和 廣度優(yōu)先搜索算法 。采用的數(shù)據(jù)結(jié)構(gòu)是 (正 )鄰接鏈表 。 深度優(yōu)先搜索算法 深度優(yōu)先搜索 (Depth First SearchDFS)遍歷類似 樹(shù)的先序遍歷 ，是 樹(shù)的先序遍歷的推廣 。 1 算法思想 設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則： ⑴ 從圖中某個(gè)頂點(diǎn) vi出發(fā) ，訪問(wèn) vi；然后找到 vi的 一個(gè)鄰接頂點(diǎn) vi1 ； ⑵ 從 vi1出發(fā)，深度優(yōu)先搜索訪問(wèn)和 vi1相 鄰接且未被訪問(wèn)的所有頂點(diǎn)； ⑶ 轉(zhuǎn)⑴ ，直到和 vi相 鄰接的所有頂點(diǎn)都被訪問(wèn)為止 ⑷ 繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn) vj作為起始頂點(diǎn)，轉(zhuǎn) (1)，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。 圖 717 無(wú)向圖深度優(yōu)先搜索遍歷 (a) 無(wú)向圖 G v1 v2 v3 v4 v5 (b) G的鄰接鏈表 0 1 2 3 4 MAX_VEX1 v1 v2 v3 v4 ┇ ┇ v5 2 1 ? 2 0 ? 0 1 ? 4 ? 3 ? 無(wú)向圖的深度優(yōu)先搜索遍歷示例 (紅色箭頭 )。某種 DFS次序是 ： v1→ v3 → v2 → v4 → v5 由算法思想知，這是一個(gè)遞歸過(guò)程。因此，先設(shè)計(jì)一個(gè)從某個(gè)頂點(diǎn) (編號(hào) )為 v0開(kāi)始 深度優(yōu)先 搜索的函數(shù) ，便于調(diào)用。 代碼詳見(jiàn) P169 2 算法實(shí)現(xiàn) 3 算法分析 遍歷時(shí)，對(duì)圖的每個(gè)頂點(diǎn)至多調(diào)用一次 DFS函數(shù)。其實(shí)質(zhì)就是對(duì)每個(gè)頂點(diǎn)查找鄰接頂點(diǎn)的過(guò)程，取決于存儲(chǔ)結(jié)構(gòu)。當(dāng)圖有 e條邊，其時(shí)間復(fù)雜度為 O(e)，總時(shí)間復(fù)雜度為 O(n+e) 。 廣度優(yōu)先搜索算法 廣度優(yōu)先搜索 (Breadth First SearchBFS)遍歷類似 樹(shù)的按層次遍歷 的過(guò)程 。 1 算法思想 設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則： ⑴ 從圖中某個(gè)頂點(diǎn) vi出發(fā) ，訪問(wèn) vi； ⑵ 訪問(wèn) vi的所有相 鄰接且未被訪問(wèn)的所有頂點(diǎn) vi1， vi2， … ，vim； ⑶ 以 vi1， vi2， … ， vim的次序 ，以 vij(1≦ j≦ m)依此作為vi ，轉(zhuǎn)⑴； ⑷ 繼續(xù)選取圖中 未被訪問(wèn) 頂點(diǎn) vk作為起始頂點(diǎn) ，轉(zhuǎn)⑴，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。 有向圖的廣度優(yōu)先搜索遍歷示例 (紅色箭頭 )。上述圖的 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 算法實(shí)現(xiàn) 為了標(biāo)記圖中頂點(diǎn)是否被訪問(wèn)過(guò)，同樣需要一個(gè)訪問(wèn)標(biāo)記數(shù)組；其次，為了依此訪問(wèn)與 vi相鄰接的各個(gè)頂點(diǎn) ，需要附加一個(gè)隊(duì)列來(lái)保存訪問(wèn) vi的相鄰接的頂點(diǎn)。 代碼實(shí)現(xiàn)詳見(jiàn) P170。 3 算法分析 用 廣度優(yōu)先搜索算法 遍歷圖與 深度優(yōu)先搜索算法遍歷圖的 唯一區(qū)別 是 鄰接點(diǎn)搜索次序不同 ，因此， 廣度優(yōu)先搜索算法 遍歷圖的總時(shí)間復(fù)雜度為 O(n+e) 。 圖的連通性問(wèn)題 本節(jié)所討論的內(nèi)容是圖的遍歷算法的具體應(yīng)用。 無(wú)向圖的連通分量與生成樹(shù) 1 無(wú)向圖的連通分量和生成樹(shù) 對(duì)于無(wú)向圖，對(duì)其進(jìn)行遍歷時(shí)： ◆ 若是 連通圖 ：僅需從圖中 任一頂點(diǎn)出發(fā) ，就能訪問(wèn)圖中的所有頂點(diǎn)； ◆ 若是 非連通圖 ：需從圖中 多個(gè)頂點(diǎn)出發(fā) 。每次從一個(gè)新頂點(diǎn)出發(fā)所訪問(wèn)的頂點(diǎn)集序列 恰好是 各個(gè)連通分量的頂點(diǎn)集； (a) 無(wú)向圖 G v1 v2 v3 v4 v5 (b) G的鄰接鏈表 0 1 2 3 4 MAX_VEX1 v1 v2 v3 v4 ┇ ┇ v5 2 1 ? 2 0 ? 0 1 ? 4 ? 3 ? 圖 719 無(wú)向圖及深度優(yōu)先生成森林 (c) 深度優(yōu)先生成森林 v1 v2 v3 v4 v5 無(wú)向非連通圖，按圖中給定的鄰接表進(jìn)行深度優(yōu)先搜索遍歷， 2次調(diào)用 DFS所得到的頂點(diǎn)訪問(wèn)序列集是： { v1 ,v3 ,v2}和 { v4 ,v5 } ⑴ 若 G=(V,E)是無(wú)向連通圖 ， 頂點(diǎn)集和邊集分別是 V(G) ， E(G) 。若從 G中 任意點(diǎn)出發(fā)遍歷時(shí)， E(G)被分成兩個(gè)互不相交的集合： T(G) ：遍歷過(guò)程中所 經(jīng)過(guò)的邊 的集合； B(G) ：遍歷過(guò)程中 未經(jīng)過(guò)的邊 的集合； 顯然： E(G)=T(G)∪ B(G) ， T(G)∩B(G)=216。 顯然， 圖 G’=(V, T(G))是 G的極小連通子圖 ，且 G’是一棵樹(shù) 。 G’稱為圖 G的一棵生成樹(shù) 。 從任意點(diǎn)出發(fā) 按 DFS算法 得到生成樹(shù) G’稱為 深度優(yōu)先生成樹(shù) ； 按 BFS算法 得到的 G’稱為 廣度優(yōu)先生成樹(shù) 。 ⑵ 若 G=(V,E)是無(wú)向非連通圖 ， 對(duì)圖進(jìn)行遍歷時(shí)得到若干個(gè)連通分量的頂點(diǎn)集 ： V1(G) ,V2(G) ,… ,Vn(G)和相應(yīng)所經(jīng)過(guò)的邊集 ： T1(G) ,T2(G) , … ,Tn(G) 則對(duì)應(yīng)的頂點(diǎn)集和邊集的二元組： Gi=(Vi(G),Ti(G)) (1≦ i≦ n)是對(duì)應(yīng)分量的生成樹(shù) ，所有這些 生成樹(shù)構(gòu)成了原來(lái)非連通圖的生成森林 。 說(shuō)明 ： 當(dāng)給定無(wú)向圖要求畫(huà)出其對(duì)應(yīng)的生成樹(shù)或生成森林時(shí)， 必須先給出相應(yīng)的鄰接表，然后才能根據(jù)鄰接表畫(huà)出其對(duì)應(yīng)的生成樹(shù)或生成森林 。 有向圖的強(qiáng)連通分量 對(duì)于有向圖，在其每一個(gè) 強(qiáng)連通分量中 ， 任何兩個(gè)頂點(diǎn)都是可達(dá)的 。 ?V?G，與 V可相互到達(dá)的所有頂點(diǎn)就是包含 V的強(qiáng)連通分量的所有頂點(diǎn) 。 設(shè)從 V可到達(dá) (以 V為起點(diǎn)的所有有向路徑的終點(diǎn) )的頂點(diǎn)集合為 T1(G)，而到達(dá) V (以 V為終點(diǎn)的所有有向路徑的起點(diǎn) )的頂點(diǎn)集合為 T2(G)，則包含 V的強(qiáng)連通分量的頂點(diǎn)集合是 ： T1(G)∩T2(G) 。 求有向圖 G的強(qiáng)連通分量的 基本步驟 是： ⑴ 對(duì) G進(jìn)行深度優(yōu)先遍歷，生成 G的深度優(yōu)先生成森林 T。 ⑵ 對(duì) 森林 T的頂點(diǎn)按 中序遍歷 順序進(jìn)行編號(hào)。 ⑶ 改變 G中每一條弧的方向 ，構(gòu)成一個(gè)新的有向圖 G’。 ⑷ 按⑵中標(biāo)出的頂點(diǎn)編號(hào)，從編號(hào)最大的頂點(diǎn)開(kāi)始對(duì)G’進(jìn)行深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹(shù)。若一次完整的搜索過(guò)程沒(méi)有遍歷 G’的所有頂點(diǎn)，則從未訪問(wèn)的頂點(diǎn)中選擇一個(gè)編號(hào)最大的頂點(diǎn)，由它開(kāi)始再進(jìn)行深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹(shù)。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹(shù)中的頂點(diǎn)就是 G的一個(gè)強(qiáng)連通分量的所有頂點(diǎn)。 ⑸ 重復(fù)步驟⑷ ，直到 G’中的所有頂點(diǎn)都被訪問(wèn)。 d a c f e b (a) 有向圖 G 6 5 4 3 2 1 d a c f e b (b) 執(zhí)行步驟 (1)和 (2) a c d f e b (c) 執(zhí)行步驟 (3) a d c b e f (d) 執(zhí)行步驟 (4)和 (5) 圖 720 利用深度優(yōu)先搜索求有向圖的強(qiáng)連通分量 在算法實(shí)現(xiàn)時(shí)，建立一個(gè)數(shù)組 in_order[n]存放深度優(yōu)先生成森林的中序遍歷序列。對(duì)每個(gè)頂點(diǎn) v，在調(diào)用 DFS函數(shù)結(jié)束時(shí) ， 將頂點(diǎn)依次存放在 數(shù)組 in_order[n]中 。圖采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)最合適。 最小生成樹(shù) 如果 連通圖 是一個(gè)帶權(quán)圖，則其生成樹(shù)中的邊也帶權(quán)，生成樹(shù)中 所有邊的權(quán)值之和 稱為 生成樹(shù)的代價(jià) 。 最小生成樹(shù) (Minimum Spanning Tree) ： 帶權(quán)連通圖中代價(jià)最小的生成樹(shù)稱為最小生成樹(shù) 。 最小生成樹(shù)在實(shí)際中具有重要用途，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示城市，邊表示兩個(gè)城市之間的通信線路，邊的權(quán)值表示建造通信線路的費(fèi)用。 n個(gè)城市之間最多可以建n?(n1)/2條線路 ，如何選擇其中的 n1條，使總的建造費(fèi)用最低 ? 基本原則是： ◆ 盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路； ◆ 選擇 n1條邊構(gòu)成最小生成樹(shù) 。 以上的基本原則是基于 MST的如下性質(zhì)： 設(shè) G=(V， E)是一個(gè)帶權(quán)連通圖， U是頂點(diǎn)集 V的 一個(gè)非空子集。若 u∈ U ， v∈ VU，且 (u, v)是 U中頂點(diǎn)到 VU中頂點(diǎn)之間權(quán)值最小的邊，則必存在一棵包含邊(u, v)的最小生成樹(shù)。 構(gòu)造最小生成樹(shù)的算法有許多，基本原則是： 設(shè)圖 G的任何一棵最小生成樹(shù)都不包含邊 (u,v)。設(shè) T是 G的一棵生成樹(shù) ，則 T是連通的 ，從 u到 v必有一條路徑 (u,… ,v)，當(dāng)將 邊 (u,v)加入到 T中時(shí)就構(gòu)成了回路 。則 路徑 (u, … ,v)中必有一條邊 (u’,v’) ，滿足 u’∈ U ， v’∈ VU 。刪去 邊 (u’,v’) 便可消除回路 ，同時(shí)得到另一棵生成樹(shù) T’。