數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)chapter

1、第七章圖一、圖1、基本概念定義：圖 G 定義為 G=(V,E)，其中 V 是頂點（數(shù)據(jù)元素）的有限非空集合，E 是 V 上頂點偶對關(guān)系的有限集合，這些偶對叫邊。若 e 是頂點 x，y 之間的一條邊，稱 x，y 是e 的端點。若 E(G)為空，則圖 G 只有頂點而無邊。若圖中任意頂點 x,y 之間存在弧(x,y)、(y,x)，且(x,y)=(y,x)，稱此圖為無向圖，x,y 之間的邊記為(x,y)；若圖中任意頂點 x,y 之間存在弧(x,y)、(y,x)，且(x,y)(y,x)，稱此圖為有向圖，x 指向y 的弧記為，y 指向x 的弧記為。2211334圖 1（a）是一個無向圖，圖 1（b）是一個

2、有向圖。特性：非線性結(jié)構(gòu)，多對多關(guān)系。2、術(shù)語無向圖：邊的頂點偶對是無序的，即(vi,vj)=(vj,vi)。有向圖：邊的頂點偶對有無序的，即 。和是兩條不同的邊。 權(quán)和網(wǎng)：在圖中給每條邊標(biāo)上具有某種意義的數(shù)據(jù)，該值稱為邊的權(quán)。邊上帶權(quán)的圖叫帶權(quán)圖，也叫網(wǎng)。鄰接：若 (vi,vj) 存在，則稱 vi 和vj 互為鄰接點；若存在，則稱 vi 鄰接到 vj， vj 鄰接于 vi。關(guān)聯(lián)：若 (vi,vj)或存在，則稱該邊或弧關(guān)聯(lián)于 vi 和vj。頂點的度：與頂點相關(guān)聯(lián)的邊的數(shù)目，記為 D(v)。入度 ID(v):有向圖中指向該頂點的弧的數(shù)目；出度 OD(v):有向圖中離開該頂點的弧的數(shù)目。無向完全圖

3、：各頂點之間有且僅有一條邊的無向圖。當(dāng)頂點數(shù)為 n 時，頂點之間的邊數(shù)e=n(n-1)/2。有向完全圖：各頂點之間都有且僅有兩條方向相反的弧的有向圖。有向完全圖的頂點數(shù)為 n時，頂點之間的邊數(shù) e=n(n-1)。圖 1 圖的示例 (a)無向圖 (b)有向圖（b）（a）稀疏圖：與圖中頂點數(shù)相比，具有很少邊或弧的圖(enlog2n)。稠密圖：與圖中頂點數(shù)相比，具有較多邊或弧的圖。子圖：對于圖 G=(V,E)與 G=(V,E)，如果 V V，E E，且 E關(guān)聯(lián)的頂點都在 V中，則稱 G是 G 的子圖。生成子圖：如果子圖中 V=V，則稱該子圖為圖 G 的生成子圖。路徑：頭尾端點相互連接的邊的端點所頂點

4、的序列（Vp,Vl,VmVz,Vq）。的頂點序列。頂點 Vp 到頂點 Vq 的一條路徑是路徑長度：路徑上邊或弧的數(shù)目之和；在網(wǎng)中，則指路徑上所有邊或弧的權(quán)值之和。簡單路徑：若一條路徑上所有頂點除始點和終點外，彼此都不相同，則該路徑稱為簡單路徑?；芈罚喝粢粭l路徑的始點和終點是同一頂點，則稱其為回路。與簡單路徑對應(yīng)的回路叫簡單回路。連通圖：頂點 v1 到 v2 有路徑，則稱 v1 和 v2 是連通的。若無向圖中任意兩個頂點 vi,vj 都是連通的，則稱此圖為連通圖。否則為非連通圖。連通分量：無向圖的極大連通子圖稱連通分量。強連通圖：在有向圖中，任意兩個頂點 vi,vj 和 vj,vi 都是連通的，

5、則稱此圖為強連通圖。否則為非強連通圖。強連通分量：有向圖的極大連通子圖稱強連通分量。3、圖的圖的結(jié)構(gòu)結(jié)構(gòu)分為鄰接矩陣和鄰接鏈表，鄰接矩陣用二維數(shù)組表示，是圖的順序結(jié)構(gòu)。鄰接鏈表用鏈表表示，在圖的鏈表（1） 鄰接矩陣1)、定義結(jié)構(gòu)。對于具有 n 個頂點的圖的鄰接矩陣定義如下：對于具有 n 個頂點的網(wǎng)的鄰接矩陣可以定義為：邏輯定義如下：#define MAX 100 typedef char VertexType;typedefEdgeType;typedef structVertextType vertexMAX; EdgeType edgesMAXMAX;Graph;2）、鄰接矩陣表示下面是圖

6、 1 的兩個圖 G1 和 G2 的矩陣表示。wij存在(vi,vj)或E(G)Aij= E(G)中不存在相應(yīng)的邊1存在(vi,vj)或E(G)Aij=0E(G)中不存在相應(yīng)的邊001100110A2=從鄰接矩陣中得到如下的一些特點：無向圖的鄰接矩陣一定是對稱矩陣，有向圖的鄰接矩陣不對稱。對于無向圖，鄰接矩陣中第 j 行（或第 j 列）的非零元素的個數(shù)正好是第 j 個頂點的度。對于有向圖，鄰接矩陣中第 j 行（或第 j 列）的非零元素的個數(shù)正好是第 j 個頂點的出度（或第 j 個頂點的入度）。通過鄰接矩陣可以計算矩陣中的非零元的個數(shù)確定圖中邊的個數(shù)。對于無向圖，鄰接矩陣可以是上（下）三角矩陣中的

7、非零元的個數(shù)；對于有向圖，直接計算非零元的個數(shù)即可。（2） 鄰接鏈表用鏈表來圖是圖的一種結(jié)構(gòu)，叫鄰接鏈表。鄰接鏈表由表頭結(jié)點和表結(jié)點，其中表結(jié)點的結(jié)構(gòu)為：頂點域和鏈域表頭結(jié)點的結(jié)構(gòu)為：頂點的有關(guān)信息域和鏈域表頭結(jié)點和表頭結(jié)點數(shù)組：typedef struct nodeverdata;struct node *next;VnGraphn;其中，Vnode 是表頭結(jié)點，LGraph 是表頭結(jié)點數(shù)組。根據(jù)這個定義，可以把 G1 和 G2 表示成下圖的鄰接鏈表形式： (a) (b)4、圖的遍歷圖的的遍歷是圖的的基礎(chǔ)。圖的遍歷主要是深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷方式。圖的遍歷比樹的遍歷要復(fù)雜。（1）

8、 深度優(yōu)先搜索0 1 0 11 0 1 00 1 0 11 1 1 0圖 3 (a)G1 圖的鄰接鏈表 (b)G2 圖的鄰接鏈表33231123424221211234verdatanextvertexnext圖 2 G1 圖的鄰接矩陣 (b)G2 圖的鄰接矩陣A1=設(shè) G=(V,E)為無向連通圖，從 G 中任一頂點 V 出發(fā)的深度優(yōu)先搜索法進行遍歷的步驟為：設(shè)立搜索指針 p，使p 指向 V；p 結(jié)點，并使 p 指向與 p 相鄰接但尚未被若 p 不空，則重復(fù)，否則執(zhí)行；過的頂點；的頂點，使 p 指向它，然后沿剛才的次序，反向回溯到一個尚有鄰接頂點未被重復(fù)步驟，直到所有頂點完為止。圖 4 中從頂

9、點 A 開始的深度優(yōu)先搜索得到的序列為：ABEHIFCGJKDABCD（2） 廣度優(yōu)先搜索從 G 中任一頂點 V 出發(fā)的廣度優(yōu)先搜索法進行遍歷的步驟為：EGFVi 后，依次與Vi 相鄰接的所有頂點W1W2Wt；HIJK 再次，按 W1W2Wt 的順序，其中與每個頂點 Wi圖4鄰接的所有未被過的頂點； 重復(fù)步，直到所有的頂點被完為止。圖 4 中從頂點 A 開始的廣度優(yōu)先搜索得到的序列為：ABCDEFGHIJK5、圖的生成樹（1）基本概念在 n 個頂點的圖中，若為無向完全圖，共有 n(n-1)/2 條邊。如果，這個圖中任意兩個頂點 vi,vj都是連通的，則稱此圖為連通圖。設(shè) G=(V,E)為連通圖

10、，有 E(G)=A(G)+B(G)， 其中 A(G)是遍歷圖 G 時經(jīng)過的邊的集合，E(G)是過的邊的集合，則 G1=(V,A)是 G 的連通子圖，并稱 G1 是 G 的生成樹。按照深度優(yōu)先和廣度優(yōu)先搜索遍歷圖時得到的序列不同一樣，按照深度優(yōu)先和廣度優(yōu)先搜索遍歷圖得到的生成樹也不一樣，并成為深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖 5 是圖 4 中圖的深度優(yōu)先生成樹。圖 6 是圖 4 中圖的廣度優(yōu)先生成樹。AABCBCDDEEFGFGHHIIJKJK圖 5 圖6 頂點為 n 的生成樹有 n-1 條邊，再多一條就形成回路，所以生成樹是 n 個頂點的極小連同子圖。（2）最小生成樹求解最小生成樹有非常重要

11、的實際意義。最小生成樹？在網(wǎng)上求解最小連通子圖，當(dāng)獲得的生成樹是邊的權(quán)值為最小的生成樹時，叫最小生成樹。下面的圖 7城市的交通圖，在每個城市的之間的邊上賦有里程，這就是一個網(wǎng)。在這中尋找從某個城市到另外一個城市的最小代價生成樹，有其實際意義。在求最小生成樹中，有兩種算法，一個叫 Prim 算法，一個叫 Kruskal 算法，下面分別介紹。1）Prim 算法算法描述： 設(shè)T 是具有n 個頂點的連通圖G 的最小生成樹，V(T)是 T 頂點集合，E(T)是 T 邊集合，開始時 V(T)和 E(T)為空；B=G-T。 在連通圖中任選一個頂點 Vi 加入 T 中； 將下列步驟重復(fù) n-1 遍：蘭州450

12、03127013506502西安650600125076重慶512001900750700911008廣州圖 7Aa.在 ViV(T)，VjV(G-T)的所有邊中選擇權(quán)值最小的一條邊(Vi,Vj)；將頂點 Vj 加到 V(T) 中；將(Vi,Vj)加到 E(T) 中。564BD35Cb.c.4612EF6例：在圖 8 中求最小生成樹。解：用 Prim 算法求最小生成樹。從頂點 A 開始構(gòu)造最小生成樹。 圖 8 AAAAAA4 4444BB3D35CCCCC1E1E1E1E222FFF2）Kruskal 算法算法描述： 設(shè) T 是具有n 個頂點的連通圖 G 的最小生成樹，V(T)是 T 頂點集合

13、，E(T)是 T 邊集合，開始時 V(T)= V(G)，E(T)為空。 在連通圖中選權(quán)值最小的邊加入 E(T)中； 若一條邊不與 T 中已有的邊則不選取此邊?；芈罚覚?quán)值又最小，則將這條邊放入 T，若回路 重復(fù)，選擇 n-1 條邊進入 T 中。例：用 Kruskal 算法求最小生成樹。在圖 8 中求最小生成樹。AAAAAA4C4CBBBBBB3D35DDDDDCCCC1E21E21E1E21E2EFFFFFF圖 10 Kruskal 算法構(gòu)造生成樹的過程圖 9 Prim 算法構(gòu)造生成樹的過程6、最短路徑在網(wǎng)中，從某個頂點 Vi 到 Vj 的最短路徑在 Vi 到Vj 各邊權(quán)值相加的最小值。這個問

14、題就是從甲地到乙地走什么路最節(jié)約和代價最小。最短路徑的求解有兩種方法，一個是單點源到其余各頂點的最短距離，一個是求圖中任意一對頂點的最短路徑算法。（1）單點源到其余各頂點的最短距離設(shè) G=(V,E)為有向帶權(quán)圖，如何求 G 中某一頂點到其余頂點的最小距離？Dijkstra 提出了一個按路徑長度（權(quán)值）遞增的次序產(chǎn)生最短路徑的算法。算法描述：構(gòu)造一個代價矩陣 cost，這個代價矩陣就是該圖的鄰接矩陣。引入輔助向量 dist，其每個分量 disti為始點 V 到頂點 Vi 的所有路徑中的最短路徑；把網(wǎng)中頂點分成兩個集合 S，T。凡以頂點 V 為源點并已確定了最短路徑的終點并入 S，尚未確定最短路徑

15、的頂點并入 T。開始時，S 只包含頂點 V，按各頂點與 V 之間的最短路徑長度遞增的次序，逐個把 T 中頂點加到 S 中，使得從 V 到 S 中各頂點的路徑長度始終不大于 V 到 T 中各頂點的路徑長度。重復(fù)n-1 次。算法細則： 建立代價矩陣 cost； 開始時，取頂點 V 到第 i 個頂點 Vi 的最短路徑為：disti=mindisti | ViT，把 Vi 并入 S 中； 依次按路徑遞增的辦法選取下一個頂點，若 disti+costi,k distk，則令 distk=disti +costi,k ，即：distk=mindistk,disti +costi,k； 重復(fù)共 n-1 次。

16、例：對圖 11 所示的圖，求頂點 1 到其余各頂點的最短路徑。代價矩陣11010023010550603420以頂點 1 為始點的最短路徑構(gòu)造S終點dist0dist4初始10 10 30 1001,220 10 50 30 1001,2,440 10 50 30 901,2,4,330 10 50 30 601,2,4,3,550 10 50 30 60cost=0 10 30 100 0 50 0 20 10 0 60 0（2）任意一對頂點的最短路徑任意一對頂點間的最短路徑長度有兩種解法，一種是使用Dijkstra 方法n-1 次，另一種是Floyd算法。Floyd 算法的：若 vi,vj

17、 間存在=costij，但 vi,vj 間還有其他路徑，不一定是最短的，尚需作 N 次試探。首先選擇頂點 1，若存在與，則比較與誰最短，取小者為最短路徑，若不存在，則取，這條路徑叫中間頂點序號不大于 1 的最短路徑。然后取頂點 vi,vj 經(jīng)過頂點 2，若存在，則要求與是經(jīng)過頂點 2 的最短路徑。把與上次選出的頂點序號不大于 1 的最短路徑比較，取其最短的作為當(dāng)前求得的頂點號不大于 2 的最短路徑。若不存在，以前求得的最短路徑即為頂點號不大于 2 的最短路徑。依次取頂點號為 3，4，重復(fù)，可求得 vi,vj 之間的最短路徑。算法細則：對 n 個頂點的圖中任意兩個頂點，求 n+1 個矩陣：A(0

18、), A(1), A(2), A(k), A(n)。其中 A(k)ij是 vi,vj 間的中間序號不大于 k 的最短路徑，A(n)則為最終求得的 vi,vj 間的最短路徑。若 vi,vj 間無頂點，則對于 1kn，有 A(k)= A(0)=costij。如果已經(jīng)產(chǎn)生了 A(k-1)ij，則求得 A(k)ij的方法為： 若從 vi 到vj 的最短路徑不通過頂點 k，則 A(k)ij= A(k-1)ij； 若從 vi 到vj 的最短路徑通過頂點 k，則由與組成，又A(k-1)ik與 A(k-1)kj分別是從 vi 到vk 和從vk 到vj 的之間頂點序號不大于 k-1 的最短路徑，則有 A(k)i

19、k= A(k-1)ik+ A(k-1)kj為 vi,vj 間中間頂點序號不大于 k 的最短路徑長度。綜上所述，有：A(0)ij=costijA(k)ij=min A(k-1)ij,A(k-1)ik+ A(k-1)kj例：求圖 12 中各頂點間的最短路徑。（1）求 cost180850 853cost=30A(0)=cost=3 052 20 2032（2）計算各級 A(k)0 85085075A(2)=A(1)=A(3)=3 08308308 20520520圖 127、拓撲排序（1） AOV 網(wǎng)對于一個工程或教學(xué)過程，可以用圖來表示。一般情況下，幾乎所有的工程都可以分為若干個成為活動的子工程

20、。如某專業(yè)的學(xué)生必須完成一系列規(guī)定的課程后才能獲得學(xué)位，此時，工程就是完成給定的學(xué)習(xí)計劃，而活動就是學(xué)門課程。根據(jù)工程活動的進程可以產(chǎn)生有向圖，這個有向圖叫 AOV 網(wǎng)。在 AOV 網(wǎng)中，若從頂點 vi 到 vj 之間存在一條有向路徑，稱 vi 是 vj 的前驅(qū)，或稱 vj 是vi 的后繼。若是圖中的弧，則稱 vi 是的直接前驅(qū)，vj 是vi 的直接后繼。下表是計算機專業(yè)的課程計劃表根據(jù)這個可以畫出如下的網(wǎng)。這個網(wǎng)叫 AOV（Activity On Vertex Network）網(wǎng)。（2） 拓撲排序根據(jù)這個網(wǎng)，的性質(zhì)：可以產(chǎn)生一個排序序列，產(chǎn)生這個序列叫拓撲排序。這個線性序列有如下 若 vi

21、是vj 的直接前驅(qū)，則 vi 先于vj； 若 vi 不是vk 的前驅(qū)，而 vk 也不是 vi 之前驅(qū)，則為其建立一個人為的先后關(guān)系，或 vi 在vk 之前，或vk 在 vi 之前。具有上述性質(zhì)的線性序列稱為拓撲排序，如果某個 AOV 網(wǎng)的所有頂點都在它的拓撲序列中，那么該 AOV 網(wǎng)不存在又向回路，由該 AOV 網(wǎng)描述的工程是可行的。拓撲排序的步驟： 在網(wǎng)絡(luò)中選一個沒有前驅(qū)的頂點，且把它輸出； 從網(wǎng)中刪去該頂點和以它為尾的所有有向邊。例：在圖 13 的 AOV 網(wǎng)中構(gòu)造拓撲序列。根據(jù)這個圖得到的是排序序列是：163425或 163245，613245，613425。2513468、關(guān)鍵路徑（1）AOE 網(wǎng)圖 13課程代號課程名先行課程課程代號課程名先行課程C1程序設(shè)計導(dǎo)論無C9算法分析C3C2數(shù)值分析C1，C14C10高級語言C3，C4C3數(shù)據(jù)結(jié)構(gòu)C1，C14C11編譯系統(tǒng)C10C4匯編語言C1，C13C12操作系統(tǒng)C11C5自理論C15C13幾何無C6人工智能C3C14微積分C13C7計算機圖形學(xué)C3，C4，C10C15線性代數(shù)C14C8計算機原理C4在有向帶權(quán)圖中，以頂點表示事件，以有向邊表示活動，邊上的