【文章內(nèi)容簡(jiǎn)介】 以采用十字鏈表法進(jìn)行存儲(chǔ)。此方法將有向圖的鄰接表和逆鄰接表合并。有向圖的十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖 。 圖 十字鏈表結(jié)點(diǎn)示意圖 鄰接多重表 ? 鄰接多重表采用與十字鏈表相似的結(jié)構(gòu)來(lái)存儲(chǔ)無(wú)向圖，將一條邊的兩個(gè)頂點(diǎn)均放在同一個(gè)鏈表中，這樣就將尋找同一條邊的兩個(gè)頂點(diǎn)的操作變得簡(jiǎn)單。 鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)如圖 。 ? 鄰接多重表有以下兩個(gè)特征。 所有依附于同一頂點(diǎn)的邊被串聯(lián)到同一個(gè)鏈表中。 由于每個(gè)邊有兩個(gè)頂點(diǎn)，因此每條邊又被串聯(lián)到兩個(gè)鏈表中。 圖 鄰接多重表的結(jié)點(diǎn)示意圖 圖 的 遍 歷 深度優(yōu)先遍歷 廣度優(yōu)先遍歷 深度優(yōu)先遍歷 ? 圖的深度優(yōu)先遍歷算法 (depthfirst search)類似于樹的先序遍歷算法，其基本思想是：初始時(shí)，設(shè)圖中的所有頂點(diǎn)均未曾訪問(wèn)到，首先從圖中某個(gè)頂點(diǎn) v0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從 v0的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v0有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)尚有頂點(diǎn)沒(méi)有被訪問(wèn)到，則從中選取一個(gè)頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)均被訪問(wèn)到為止。 ? 對(duì)圖進(jìn)行深度優(yōu)先遍歷時(shí)，有下面兩點(diǎn)需要注意。 圖采用鄰接表進(jìn)行存儲(chǔ)時(shí)，一個(gè)圖的深度優(yōu)先序列不唯一。 鄰接矩陣表示的圖確定起始結(jié)點(diǎn)后，其深度優(yōu)先序列唯一。 廣度優(yōu)先遍歷 ? 圖的廣度優(yōu)先遍歷 (breadthfirst search)類似于樹的按層次遍歷的過(guò)程。其基本思想是：初始時(shí)，圖中的所有頂點(diǎn)均未曾訪問(wèn)過(guò)。首先，從圖的某個(gè)頂點(diǎn) v0出發(fā)，訪問(wèn)了 v0之后，依次訪問(wèn)的 v0個(gè)未曾訪問(wèn)過(guò)的鄰接頂點(diǎn)，然后分別從這些鄰接頂點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問(wèn)過(guò)的頂點(diǎn)的鄰接點(diǎn)都已訪問(wèn)過(guò)。如果圖中仍存在沒(méi)有訪問(wèn)過(guò)的頂點(diǎn)，則從中選取一個(gè)作為起始點(diǎn)，重復(fù)上述過(guò)程，直到圖中不存在未被訪問(wèn)過(guò)的頂點(diǎn)。圖 。 圖 廣度優(yōu)先遍歷過(guò)程 圖的連通性 無(wú)向圖的連通性 有向圖的連通性 無(wú)向圖的連通性 根據(jù)圖的連通性的定義，有這樣的結(jié)論：如果一個(gè)圖是連通的，當(dāng)且僅當(dāng)從任一結(jié)點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先遍歷均可訪問(wèn)到每一個(gè)結(jié)點(diǎn)。 深度優(yōu)先生成樹的構(gòu)造步驟如下。 (1) 深度優(yōu)先生成樹的樹根是 A，是圖中第一個(gè)被訪問(wèn)到的結(jié)點(diǎn)。 (2) 當(dāng)遍歷到圖的一條邊 (vi, vj)時(shí)，如果 vj是未訪問(wèn)過(guò)的，那么就將樹的結(jié)點(diǎn) vi建立一條邊來(lái)表示圖的這一條邊 (vi, vj)。 (3) 當(dāng)遍歷到圖的一條邊 (vi, vj)時(shí)，如果 vj是已訪問(wèn)過(guò)的，那么就將樹的結(jié)點(diǎn) vi建立一條虛邊來(lái)表示這一條邊。 (4) 重復(fù)步驟 (2)、 (3)，直到圖中的所有結(jié)點(diǎn)均訪問(wèn)完。 有向圖的連通性 如果有向圖 G中，若對(duì)于 V(G)中任意兩個(gè)不同的頂點(diǎn) vi和 vj，都存在從 vi到 vj以及從 vj到 vi的路徑，則稱 G是強(qiáng)連通圖。 求強(qiáng)連通分量有 3種算法，分別是 Kosaraju算法、 Gabow算法和Tarjan算法。這里只介紹 Kosaraju算法。 Kosaraju算法的步驟很簡(jiǎn)單，只有以下兩步，這里假設(shè)有向圖采用十字鏈表的結(jié)構(gòu)進(jìn)行存儲(chǔ)。 (1)首先對(duì)圖 G進(jìn)行一次 DFS，并記錄下回溯的順序。 (2)把圖 G的有向邊反向，得到圖 G′ ，并沿回溯順序倒序，再進(jìn)行一次DFS，所提的深度優(yōu)先樹即為強(qiáng)連通分量的劃分。 最小生成樹 基本概念 Prim算法 Kruskal算法 基本概念 ? 對(duì)于連通的帶權(quán)圖 (連通圖 )G，其生成樹也是帶權(quán)的。生成樹 T各邊的權(quán)值總和稱為該樹的權(quán)，記作： 這里， TE表示 T的邊集， w(u, v)表示邊 (u, v)的權(quán)。權(quán)最小的生成樹稱為 G的最小生成樹 (Minimum Spannirng Tree， MST)。 ? 最小生成樹有以下性質(zhì)： 設(shè) G=(V, E)是一個(gè)連通網(wǎng)絡(luò)， U是頂點(diǎn)集 V的一個(gè)真子集。若 (u, v)是一條具有最小權(quán)值的邊，其中 u∈ U， v∈ VU，則一定存在 G的一棵最小生成樹包括此邊 (u, v)。 E( , )( ) ( , )u v TW J W u v?? ? Prim算法 Prim算法是采用最小生成樹性質(zhì)來(lái)構(gòu)造最小生成樹，其算法步驟如下。 設(shè)圖 G =(V, E)，其生成樹的頂點(diǎn)集合為 U。 (1)把 v0放入 U。 (2)在所有 u∈ U， v∈ VU的邊 (u, v)∈ E中找一條最小權(quán)值的邊，加入生成樹。 (3)把第 (2)步中找到的邊的 v加入 U集合。如果 U集合已有 n個(gè)元素，則結(jié)束；否則繼續(xù)執(zhí)行第 2步。 Kruskal算法 ? Kruskal算法與 Prim算法正好相反，它是連續(xù)地按照最小的權(quán)選擇邊，并且當(dāng)所選擇的邊不產(chǎn)生環(huán)時(shí)，就把它作為取定的邊。其算法步驟如下所示。 ? 設(shè)圖 G =(V, E)，其生成樹 T的頂點(diǎn)集合也為 V，邊集合為 TE。 (1)在 E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在 T中不同的連通分量上，則將此邊加入 TE；否則舍棄，而選擇下一條代價(jià)最小的邊。 (2)若 T中有 |V|1條邊，結(jié)束；否則轉(zhuǎn)步驟 (1)。 最 短 路 徑 從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 所有點(diǎn)對(duì)最短路徑 從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 ? 求一個(gè)帶權(quán)有向圖 G中，頂點(diǎn) 0到其他頂點(diǎn)的最短路徑。其最直觀的一個(gè)算法是先求出所有以 0為起點(diǎn)、 n為終點(diǎn)的路徑，比較它們的長(zhǎng)度，長(zhǎng)度最短的路徑即為所取最小的路徑。 ? 稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn) (source)，最后一個(gè)頂點(diǎn)為終點(diǎn)(destination)。設(shè) S為最短路徑已確定的頂點(diǎn)集， VS是最短距離尚未確定的頂點(diǎn)集。 (1)初始時(shí)，將源點(diǎn) v0添加到頂點(diǎn)集 S中，即 S={v0}。 (2)重復(fù)以下工作，按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)的最短路徑。 所有點(diǎn)對(duì)最短路徑 ? 有時(shí)想要求解所有點(diǎn)對(duì)的最短路徑，對(duì)于這個(gè)問(wèn)題，最直觀的一個(gè)算法就是對(duì)每一個(gè)頂點(diǎn)采用 Dijkstra算法，這樣整個(gè)算法的時(shí)間復(fù)雜度將達(dá)到 O(n3)。在這里將介紹由 Floyd提出的另一種算法，雖然它的時(shí)間復(fù)雜度也是 O(n3)，但是它在形式上更簡(jiǎn)單些。 ? Floyd算法仍采用帶權(quán)鄰接矩陣表示的圖，它通過(guò)一個(gè)三重循環(huán)，產(chǎn)生一個(gè)存儲(chǔ)每個(gè)結(jié)點(diǎn)最短距離的矩陣。兩個(gè)頂點(diǎn)的最短距離有以下 3種情況。 ? (1) 最短路徑為兩個(gè)頂點(diǎn)之間的直達(dá)路徑。 ? (2) 最短路徑為兩個(gè)頂點(diǎn)之間通過(guò)一個(gè)中間點(diǎn)相連以后的距離最短。 ? (3) 最短路徑為兩個(gè)頂點(diǎn)之間通過(guò)兩個(gè)以上的中間頂點(diǎn)相連以后而得到的距離最短。 Floyd算法的基本思想如下。 (1)初始化時(shí)，用 D[v][w]=G[v][w]。 (2)依次掃描每一個(gè)點(diǎn)，查看是否有通過(guò)此頂點(diǎn)后，頂點(diǎn)對(duì)的 D[v][w]值更小的路徑，如果有則更新 D[v][w]。 (3)所求得的 D[v][w]即為每個(gè)點(diǎn)對(duì)最小路徑的長(zhǎng)度。 有向無(wú)環(huán)圖的應(yīng)用 拓?fù)渑判? 求解關(guān)鍵路徑 拓?fù)渑判? 拓?fù)渑判?(topplogical sort)是一種操作，它從某個(gè)集合上的一個(gè)偏序求出該集合上的全序。簡(jiǎn)單地說(shuō)，拓?fù)渑判蚓褪菍⒓仙系脑匕茨撤N關(guān)系進(jìn)行排序。拓?fù)渑判虻亩x中的偏序和全序的定義如下。 若集合 X上的關(guān)系 R是自反的、反對(duì)稱的和傳遞的，則稱 R是集合 X上的偏序 (partial order)關(guān)系。 設(shè) R是集合 X上的偏序關(guān)系，如果對(duì)于每個(gè) x， y∈ X必有 xRy或 yRx，則稱 R是集合 X上的全序 (total order)關(guān)系。 求解拓?fù)渑判虻姆椒ê芎?jiǎn)單，其基本思想如下： (1)選擇圖中沒(méi)有前驅(qū)的頂點(diǎn) v開始遍歷。 (2)輸出頂點(diǎn) v。 (3)刪除頂點(diǎn) v，若存在以 v為尾的弧，則將其刪除。 (4)重復(fù)步驟 (1)～ (3)，直到圖中的頂點(diǎn)均已全部輸出，或者圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止。 求解關(guān)鍵路徑 路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑 (critical path)。 求解關(guān)鍵路徑的算法步驟如下。 (1)輸入 e條弧 j, k，建立 AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)。 (2)從源點(diǎn) v1出發(fā)，令 ve(1)=0，按拓?fù)溆行蚯?ve(j) 2≤ j≤n 。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中的頂點(diǎn)個(gè)數(shù)，則說(shuō)明 AOE網(wǎng)存在環(huán)，不能求解關(guān)鍵路徑，算法終止。否則執(zhí)行步驟 (3)。 (3)從匯點(diǎn) vn出發(fā)，令 vl(n)=ve(n)，按逆拓?fù)溆行蚯?vl(i)， 1≤ j≤ n1。 (4)根據(jù)各頂點(diǎn)的 ve和 vl值，求每條弧 s(活動(dòng) )的最早開始時(shí)間 e(s)和最晚開始時(shí)間 l(s)，其中 e(s)=l(s)為關(guān)鍵活動(dòng)。 第 8章 查 找 本章主要內(nèi)容 線性表上的查找 樹上的查找 哈希表 線性表上的查找 順序表上的查找 有序表上的查找 索引順序表上的查找 線性表上的查找算法比較 順序表上的查找 ? 順序表或者線性鏈表上的查找用順序查找算法來(lái)實(shí)現(xiàn)，順序查找算法是從序列的最后一個(gè)元素開始從后往前依次進(jìn)行比較，如果匹配則查找成功，如果直到所有的記錄都比較過(guò)仍然沒(méi)有匹配則查找失敗。 ? 下面給出順序查找的算法 void straipass(int * SqList, int key,int len) { SqList[0]=key。 //設(shè)置監(jiān)視哨 //從右至左查找第一個(gè)與 key匹配記錄的位置 for(int i=len。Sqlist[i]!=key。i)。 return i。 //如果返回值為 0則查找失敗，否則查找成功 } 有序表上的查找 折半查找又稱為二分查找，它要求線性表是有序的，即表中的結(jié)點(diǎn)按關(guān)鍵字有序進(jìn)行排列，并且需要采用一維數(shù)組進(jìn)行存儲(chǔ)。 折半查找的基本思想如下。 假設(shè) L[low..high]為當(dāng)前的查找區(qū)間。 (1) 首先確定該區(qū)間中點(diǎn)位置。即 mid=[(low+high)]。 (2) 將待查找的 k值與 L[mid].key進(jìn)行比較，如果 k=L[mid].key，則查找成功，返回此位置；否則，需要確定新的查找區(qū)間，在新的查找區(qū)間中繼續(xù)進(jìn)行折半查找，直至找到關(guān)鍵字為 k的結(jié)點(diǎn)，或者直至當(dāng)前的查找區(qū)間為空 (即查找失敗 )時(shí)停止。 ①如果 kL[mid].key，則待查找的 k值必定在子區(qū)間 L[low..mid1]中，因此新查找的區(qū)間為 L[low..mid1]。 ②如果 kL[mid].key，則待查找的 k值必定在子區(qū)間 L[mid+1..high]中，因此新查找的區(qū)間為 L[mid+1..high]。 索引順序表上的查找 索引順序查找又稱為分塊查找 (blocking search)。