數(shù)據(jù)結構07章學習教案

1、數(shù)據(jù)結構數(shù)據(jù)結構(sh j ji u)07章章第一頁，共80頁。7.1 圖的術語圖的術語(shy)ADT Graph D_Object: V = 具有具有(jyu)相同特性的數(shù)據(jù)元素的集相同特性的數(shù)據(jù)元素的集 合合，即：，即：V為頂點集。為頂點集。 D_Relation: R = VR VR = | v, wV且且P(v, w), 表示從表示從v到到w的弧，謂詞的弧，謂詞 P(v, w)定義了弧的意義或信息定義了弧的意義或信息 B_OP: (共共13種種) ADT Graph第1頁/共80頁第二頁，共80頁。 有時,圖G的頂點集記為V(G)；邊(或弧)的集記為E(G)(或A(G)，邊(或弧)的

2、集在不明確(mngqu)是何種圖時通常記為R(G)。第2頁/共80頁第三頁，共80頁。在 有 向 圖 G 中 ， 若 v i , v jV ( G ) , A(G), 則稱是G中的從vi到vj的一條(y tio)弧，且稱vi為弧尾(Tail)(或初始點(Initial Node)，vj為弧頭(Head)(或終端點(Terminal Node)；若A(G), 則vj是弧尾，vi是弧頭，且。第3頁/共80頁第四頁，共80頁。設圖G中有n個頂點(dngdin)，則G中弧的條數(shù)最多為n(n1)條。例：例：G11234V(G1)=v1, v2, v3, v4A(G1)=, , 第4頁/共80頁第五頁，共

3、80頁。注：1) 無論是有向圖，還是(hi shi)無向圖，若(vi, vj)R(G)，則要求vivj如：就不能出現(xiàn)(chxin)在圖中，即不能認為是圖中的邊(或弧)。第5頁/共80頁第六頁，共80頁。2) 圖中兩個頂點之間不允許多次出現(xiàn)同一條邊(或弧)，否則就不是(b shi)圖，而稱為多重圖。如：不是(b shi)圖3) 用n表示圖中頂點的數(shù)目(shm)，用e表示邊(或弧)的數(shù)目(shm)，那么，對于無向圖，0en(n1)/2；對于有向圖，0en(n1)。第6頁/共80頁第七頁，共80頁。無向(w xin)圖例：V(G)=v1, v2, v3, v4E(G)=(v1, v2), (v1,

4、v3), (v1, v4) , (v2, v3), (v2, v4) ,(v3, v4)1324此圖中邊數(shù)共6條，即：62) 14(4第7頁/共80頁第八頁，共80頁。1) 有向完全(wnqun)圖：n個頂點的有向圖中若有n(n1)條弧，則稱該圖為有向完全(wnqun)圖。2) 無向(w xin)完全圖：n個頂點的無向(w xin)圖中有2) 1( nn條邊，則稱該圖為無向完全圖。13241324第8頁/共80頁第九頁，共80頁。 具有n個頂點的圖G中邊(或弧)的條數(shù)(tio sh)很少(如enlogn)的圖稱為稀疏圖(Sparse Graph)，反之稱為稠密圖(Dense Graph)。(邊

5、的條數(shù)(tio sh)究竟少于多少才稱為稀疏圖，并無確切的限定)第9頁/共80頁第十頁，共80頁。帶權的圖 把一組與圖中的邊(或弧)相關的數(shù)稱作圖中相應(xingyng)邊(或弧)的權(Weight)(或權值)。帶權的圖稱為網(wǎng)(Network)。第10頁/共80頁第十一頁，共80頁。 V(G)V(G)，且R(G)R(G) 則稱G是G的子圖。第11頁/共80頁第十二頁，共80頁。圖等。第12頁/共80頁第十三頁，共80頁。 1) 對于無向(w xin)圖G = (V, E)，如果邊(vi, vj)E(G)，則稱頂點vi和vj互為鄰接點(Adjacent)，即： vi和v

6、j 相互鄰接；稱邊(vi, vj)依附 (Incident) (或關聯(lián))于頂點vi和vj, 或者說邊(vi, vj)與頂點vi和vj相關聯(lián)。注：鄰接表示頂點注：鄰接表示頂點(dngdin)之間的邏輯關系，之間的邏輯關系，關聯(lián)表示邊與頂點關聯(lián)表示邊與頂點(dngdin)之間的關系。之間的關系。 2) 對于有向圖G = (V, A)，如果弧A(G)，則稱頂點vi鄰接到鄰接到頂點vj，或頂點vj鄰接自鄰接自頂點vi；又稱弧與頂點vi和vj相關聯(lián)。第13頁/共80頁第十四頁，共80頁。 在無向圖中，與頂點在無向圖中，與頂點(dngdin)vi(viV(G)相關聯(lián)的邊的相關聯(lián)的邊的條數(shù)稱為條數(shù)稱為vi的

7、度，記為的度，記為TD(vi)。第14頁/共80頁第十五頁，共80頁。 在有向圖中，頂點在有向圖中，頂點(dngdin)vi的度的度TD(vi) = ID(vi) + OD(vi)。即：頂點。即：頂點(dngdin)的入度、的入度、出度之和，其中：出度之和，其中：入度(InDegree)：ID(vi)等于(dngy)以vi為頭的邊的數(shù)目。出度(OutDegre)：OD(vi)等于(dngy)以vi為尾的邊的數(shù)目。注注：一個：一個有有n個頂點、個頂點、e條邊條邊(或弧或弧)的無向的無向圖圖(或有向圖或有向圖)的頂?shù)捻旤c點的度，均滿足下列關系：的度，均滿足下列關系：niiivTDe)(21(n為圖

8、為圖G的頂點數(shù)的頂點數(shù))第15頁/共80頁第十六頁，共80頁。a) 若G是無向圖，如果(vp, vi1), (vi1, vi2), (vin, vq)E(G)，則頂點序列(xli)(vp, vi1, vi2, ，vin，vq)是頂點vp到vq的一條路徑。若G是有向圖，則路徑也是有向的，其頂點序列(xli)應滿足：，A(G)。b) 路徑長度(chngd)：路徑上邊(或弧)的條數(shù)。第16頁/共80頁第十七頁，共80頁。c) 簡單路徑：不重復出現(xiàn)同一(tngy)頂點的路徑。d) 回路(環(huán))：第一個頂點和最后一個頂點相同(xin tn)的路徑。e) 簡單(jindn)回路(或簡單(jindn)環(huán))：除

9、第一個和最后一個頂點之外，路徑上其余頂點不重復出現(xiàn)的回路。第17頁/共80頁第十八頁，共80頁。a) 連通：若從頂點vi到vj存在一條(y tio)路徑，則稱vi與vj是連通的。(注：有向圖中，vi與vj連通，不一定有vj與vi連通)b) 若G中的任意兩個(lin )不同頂點vi和vj都是連通的，則稱G是連通圖。第18頁/共80頁第十九頁，共80頁。即：(vi, vjv(G), vivj), vi, vj是連通(lintng)的，則G是連通(lintng)圖。132413241423連通(lintng)圖第19頁/共80頁第二十頁，共80頁。14231234非連通(lintng)圖第20頁/共

10、80頁第二十一頁，共80頁。c) 連通(lintng)分量：無向圖中的一個極大連通(lintng)子圖(一個極大連通(lintng)分支)。例例：G如132是G的一個連通子圖但不是(b shi)極大連通子圖。132456789第21頁/共80頁第二十二頁，共80頁。上圖G是一個非連通圖，但它有三個連通分量(fn ling)，分別為：132478956和第22頁/共80頁第二十三頁，共80頁。d) 強連通圖：在有向圖G中，若對于每一對頂點vi， vjV(G)， vivj，從vi到vj和從vj到vi都存在一條(y tio)路徑，則稱G是強連通圖。(注意(zh y)：并不要求vi到vj或vj到vi存

11、在弧)e) 強連通分量(fn ling)：有向圖中的一個極大強連通子圖。第23頁/共80頁第二十四頁，共80頁。例：例：123123存在兩個(lin )強連通分量和圖：123是強連通(lintng)圖第24頁/共80頁第二十五頁，共80頁。7.2 圖的存儲圖的存儲(cn ch)結構結構圖的存儲結構通常有，用數(shù)組表示的鄰接(ln ji)矩陣、鄰接(ln ji)表、十字鏈表和鄰接(ln ji)多重表。以下分別介紹： 用兩個數(shù)組分別存儲數(shù)據(jù)元素(yun s)(頂點)(一維)的信息和邊(或弧)(二維)的信息。其形式描述如下：P161第25頁/共80頁第二十六頁，共80頁。1) 設圖G=(V, R)是有

12、n(n1)個頂點的圖，則根據(jù)G中頂點間的鄰接關系可用二維數(shù)組建立具有下列性質(zhì)的nn階的鄰接矩陣作為(zuwi)G的存儲結構。即：Aij =1 若或(vi,vj)R(G)0 反之第26頁/共80頁第二十七頁，共80頁。例：例：42310 1 1 11 0 1 11 1 0 11 1 1 0 無向無向(w xin)圖：對稱鄰圖：對稱鄰接矩陣接矩陣第27頁/共80頁第二十八頁，共80頁。0 1 01 0 10 0 0231 有向圖：非對稱鄰接矩陣第28頁/共80頁第二十九頁，共80頁。借助鄰接矩陣可判定圖中任意(rny)兩個頂點vi、vj之間是否有邊(或弧)相連，即：無向圖中各頂點無向圖中各頂點(d

13、ngdin)的度的度: 第第i行行(或第或第j列列)元素之和。即：元素之和。即：1 -n0jiAij)TD(v10j)TD(vor nijiA當Aij =1 (vi和vj之間有邊(或弧)相連)0 (vi和vj之間無邊(或弧)并可求得：有向圖中各頂點有向圖中各頂點(dngdin)的度的度: 第第i行元素之和為頂點行元素之和為頂點(dngdin)vi的出度的出度OD(vi)，第，第j列元素之和為頂點列元素之和為頂點(dngdin)vj的入度的入度ID(vj)，即：，即：1010iii)OD(v)ID(v)TD(vnjnjijAjiA第29頁/共80頁第三十頁，共80頁。2) 網(wǎng)的鄰接矩陣可定義為：

14、wij為邊(vi, vj) or 弧上的權值。在無向圖中根據(jù)其對稱性，若要檢測圖中有多少(dusho)條邊，只需檢測其上三角矩陣或下三角矩陣即可。Aij =wij (Vi,Vj)orR(G) 反之例：見P162頁圖7.9第30頁/共80頁第三十一頁，共80頁。鄰接表是圖的一種鏈式存儲結構。它是將圖中的每一個頂點建立一個帶表頭結點的單鏈表，第i個單鏈表中的結點表示(biosh)依附于頂點vi的邊(有向圖中是以vi為尾的弧)以及與vi相鄰接的所有頂點；每個表頭結點有序地存儲在一個一維數(shù)組中，主要用于存儲頂點的有關信息及指向該頂點對應的單鏈表的指針。第31頁/共80頁第三十二頁，共80頁。1) 鄰接

15、(ln ji)表中鏈表結點結構：鄰接點域：鄰接點域：與頂與頂點點vi鄰接的點在圖鄰接的點在圖中的位置中的位置(序號序號)鏈域鏈域 ：指示下一指示下一條邊或弧的鄰接條邊或弧的鄰接點點adjvexnextarcinfo數(shù)據(jù)域：數(shù)據(jù)域：邊或弧邊或弧相關的信息或權相關的信息或權值等值等datafirstarc數(shù)據(jù)域：與數(shù)據(jù)域：與vi有關有關(yugun)的信息的信息(序號序號)鏈域：指示鏈鏈域：指示鏈表中第一表中第一(dy)結點結點b) 頭結點：頭結點：頂點在圖中位置是人為的編排的，頂點在圖中并沒有頂點在圖中位置是人為的編排的，頂點在圖中并沒有順序關系。順序關系。a) 表結點：表結點：第32頁/共80

16、頁第三十三頁，共80頁。2) 鄰接表的存儲(cn ch)結構如下： P163/-圖的鄰接表存儲表示圖的鄰接表存儲表示-typedef struct VNode Vnode, AdjListMAX_VERTEX_NUM;#define MAX_VERTEX_NUM 20 / 最大值頂點數(shù)最大值頂點數(shù)/ 指向第一條依附該頂點的弧的指針指向第一條依附該頂點的弧的指針typedef struct ALgraph;int vexnum, arcnum; / 圖的當前頂點數(shù)和弧數(shù)圖的當前頂點數(shù)和弧數(shù)AdjList vertices; int kind; / 圖的種類標志圖的種類標志ArcNode *fir

17、starc；int adjvex；typedef struct ArcNode ArcNode;InfoType *info; / 該弧相關信息的指針該弧相關信息的指針/ 該弧所指向的頂點的位置該弧所指向的頂點的位置/ 指向下一條弧的指針指向下一條弧的指針struct ArcNode *nextarc；vertexType data； / 頂點信息頂點信息第33頁/共80頁第三十四頁，共80頁。3) 結點結構：為簡便起見，我們采用兩個域的結點結構來建立(jinl)鄰接表： 注意：為使表頭結點注意：為使表頭結點(ji din)和表結點和表結點(ji din)同構，我們均采用同一種結點同構，我們均

18、采用同一種結點(ji din)結構來建立鄰接表，省略表結點結構來建立鄰接表，省略表結點(ji din)中的中的info域。域。例：例：v1v2v3v4無向無向(w xin)圖鄰接表：圖鄰接表：v10123v20123v301v4230123表頭數(shù)組第34頁/共80頁第三十五頁，共80頁。有向圖鄰接有向圖鄰接(ln ji)表：表：v2v3v12v1v2v301120表頭數(shù)組注：注： 無向圖中無向圖中n個頂點，個頂點，e條邊，則其鄰接表需條邊，則其鄰接表需n個頭結點個頭結點(ji din)和和2e個表結點個表結點(ji din)。 表結點表結點(ji din)中，中，adjvex域存放頂點在數(shù)組中

19、的序號。習慣上由大到小排列。域存放頂點在數(shù)組中的序號。習慣上由大到小排列。第35頁/共80頁第三十六頁，共80頁。由鄰接表可得：在無向圖的鄰接表中的第i個鏈表中的結點數(shù)等于(dngy)頂點vi的度。而對于有向圖，第i個鏈表中的結點數(shù)是頂點的vi的出度。若要求頂點vi的入度，則要遍歷整個鄰接表，求得鄰接表中表結點的鄰接點域adjvex的值=i1(頂點vi在數(shù)組中的序號)的結點的個數(shù)，即得頂點vi的入度。顯然比較麻煩(m fan)。為方便起見，我們可以建立另一個鄰接表逆鄰接表，即：對每個頂點vi建立一個以vi為弧頭的鄰接表，其表結點是連接vi的尾頂點，其頭結點與上相同。第36頁/共80頁第三十七頁

20、，共80頁。例：上圖的逆鄰接例：上圖的逆鄰接(ln ji)表：表：注：注： 第第i個鏈表中的結點數(shù)即為個鏈表中的結點數(shù)即為vi的入度；的入度； 鄰接表容易找出頂點之間的鄰接點，但要判斷鄰接表容易找出頂點之間的鄰接點，但要判斷vi和和vj之間是否存在邊之間是否存在邊(或弧或弧)，則要搜索，則要搜索(su su)第第i或第或第j個鏈表，不及鄰接矩陣方便。個鏈表，不及鄰接矩陣方便。2v1v2v301101表頭數(shù)組第37頁/共80頁第三十八頁，共80頁。 是有向圖的另一種鏈式存儲結構(jigu)，可以看成是將有向圖的鄰接表和逆鄰接表結合起來所得的一種鏈表。1) 結點結構結點結構(jigu)：每條弧有一

21、個結點，：每條弧有一個結點，每個頂點也有一個結點。每個頂點也有一個結點。 弧頭頂點弧頭頂點指示弧頭指示弧頭相同的下相同的下一條弧一條弧弧相關的弧相關的信息或權信息或權值等值等a) 表表(弧弧)結點：結點：tailvexheadvexhlinktlinkinfo弧尾頂點弧尾頂點指示弧指示弧尾相同尾相同的下一的下一條弧條弧第38頁/共80頁第三十九頁，共80頁。指向指向(zh xin)以以該頂點為該頂點為弧頭的第弧頭的第一個弧結一個弧結點點b) 頭頭(頂點頂點(dngdin)結點：結點：datafirstinfirstout與頂點相與頂點相關關(xinggun)的信的信息息指向以指向以該頂點該頂點

22、為弧尾為弧尾的第一的第一個弧結個弧結點點2) 有向圖的十字鏈表存儲表示如下：有向圖的十字鏈表存儲表示如下： P165 第39頁/共80頁第四十頁，共80頁。/-有向圖的十字鏈表存儲表示有向圖的十字鏈表存儲表示-typedef struct vexNode vexnode;#define MAX_VERTEX_NUM 20 / 最大值頂點數(shù)最大值頂點數(shù)/ 分別指向該頂點的第一條入弧和出弧分別指向該頂點的第一條入弧和出弧typedef struct OLgraph;int vexnum, arcnum; / 有向圖的當前頂點數(shù)和有向圖的當前頂點數(shù)和弧數(shù)弧數(shù)vexNode xlistMAX_VERT

23、EX_NUM; / 表頭數(shù)組表頭數(shù)組 ArcBox *firstin, *firstout；int tailvex, headvex；typedef struct ArcBox ArcBox;InfoType *info; / 該弧相關信息的指針該弧相關信息的指針/ 該弧的尾和頭頂點的位置該弧的尾和頭頂點的位置/ 分別為弧頭相同和弧尾相同的弧的鏈域分別為弧頭相同和弧尾相同的弧的鏈域struct ArcBox *hlink, *tlink；vertexType data； / 頂點信息頂點信息第40頁/共80頁第四十一頁，共80頁。 是無向圖的另一種鏈式存儲結構。從無向圖的鄰接表可以看出，每條邊

24、(vi, vj)是兩個頂點vi和vj表示，而它們分別在第i個鏈表和第j個鏈表中，這給某些圖的操作帶來不便。例如，某些應用(yngyng)中需要對邊進行操作，如對已搜索過的邊作記號或刪除一條邊等，此時需要找到表示同一條邊的兩個結點。對于這類操作采用鄰接多重表作為圖的存儲結構更為適宜。第41頁/共80頁第四十二頁，共80頁。1) 結點結構結點結構(jigu)：鄰接多重表的結構：鄰接多重表的結構(jigu)和十字鏈表類似，每條邊用一結點表示，和十字鏈表類似，每條邊用一結點表示，每個頂點也用一結點表示。每個頂點也用一結點表示。mark：標志域，標記該條邊是否：標志域，標記該條邊是否(sh fu)被搜索

25、過。被搜索過。ivex, jvex：為該邊依附的兩個頂點：為該邊依附的兩個頂點(dngdin)序號序號(在圖在圖中的位置中的位置)ilink, jlink：指針域，分別指向下一條依附于頂點指針域，分別指向下一條依附于頂點ivex和頂和頂點點jvex的邊。的邊。a) 表表(邊邊)結點：結點：markivex ilink jvex jlink infoinfo：數(shù)據(jù)域，存儲與邊相關的信息的指針域。：數(shù)據(jù)域，存儲與邊相關的信息的指針域。第42頁/共80頁第四十三頁，共80頁。指針指針(zhzhn)域：指域：指示第一條依附于該頂點示第一條依附于該頂點的邊的邊b) 頭頭(頂點頂點(dngdin)結點：結

26、點：datafirstedge數(shù)據(jù)域：存儲與頂點數(shù)據(jù)域：存儲與頂點相關相關(xinggun)的的信息信息第43頁/共80頁第四十四頁，共80頁。v4v2v3v1e1e2e6e5e4e31v1v2v3v421 32 3 01020 3如：如：0123e1e2e4e3e5e6第44頁/共80頁第四十五頁，共80頁。v1：e1 e2 e3v2：e1 e4 e5v3：e2 e4 e6v4：e4 e5 e6或：或：0 e2 1 e40 e1 2 e40 3 e51 e5 2e61 3 e62 3 v1v2v3v4e1e2e3e4e5e6第45頁/共80頁第四十六頁，共80頁。 對于加權圖也同樣可以鄰接表

27、和鄰接多對于加權圖也同樣可以鄰接表和鄰接多重表來作為存儲重表來作為存儲(cn ch)結構，只要加一個存放結構，只要加一個存放權值的域即可。權值的域即可。 除增加一個標志域外除增加一個標志域外(y wi)，鄰接多，鄰接多重表所需存儲空間與鄰接表相同；各種基本操重表所需存儲空間與鄰接表相同；各種基本操作也相似。作也相似。 鄰接多重表與鄰接表的差別：僅在于同鄰接多重表與鄰接表的差別：僅在于同一條邊在鄰接表中用兩個一條邊在鄰接表中用兩個(lin )結點表示，而在結點表示，而在鄰接多重表中只用一個結點表示，還可通過表頭結鄰接多重表中只用一個結點表示，還可通過表頭結點，把任一頂點依附的邊都點，把任一頂點依

28、附的邊都 接出來。接出來。注：注：第46頁/共80頁第四十七頁，共80頁。2) 無向圖的鄰接多重表存儲(cn ch)結構如下： P167/-無向圖的鄰接多重表存儲表示無向圖的鄰接多重表存儲表示-typedef struct vexBox vexBox;#define MAX_VERTEX_NUM 20 / 最大值頂點數(shù)最大值頂點數(shù)/ 指向第一條依附該頂點的邊指向第一條依附該頂點的邊typedef struct AMLGraph;int vexnum, arcnum; / 無向圖的當前頂點數(shù)和無向圖的當前頂點數(shù)和邊數(shù)邊數(shù)vexBox adjmulistMAX_VERTEX_NUM; / 表頭數(shù)組

29、表頭數(shù)組 EBox *firstedge；int ivex, jvex；typedef struct EBox EBox;InfoType *info; / 該邊相關信息的指針該邊相關信息的指針/ 該邊依附的兩個頂點的位置該邊依附的兩個頂點的位置/ 分別指向依附這兩個頂點的下一條邊分別指向依附這兩個頂點的下一條邊struct EBox *ilink, *jlink；vertexType data； / 頂點信息頂點信息VisitIf mark; / 訪問標記訪問標記typedef emnu unvisited, visited VisitIf;第47頁/共80頁第四十八頁，共80頁。7.3 圖

30、的遍歷圖的遍歷(bin l)與求圖的連通分與求圖的連通分量量在遍歷圖的過程中，訪問某個(mu )頂點之后，可能順著某條路徑再次訪問該頂點。為了避免多次訪問同一頂點，需設置一個一維輔助數(shù)組標識圖中的頂點是否已被訪問過，若G有n個頂點，則該數(shù)組大小為n。第48頁/共80頁第四十九頁，共80頁。即：即：Boolean visitedMAX;visitedi =TRUE 表示(biosh)vi已被訪問過FALSE 表示(biosh)vi未被訪問過 注：注： “ TRUE”亦可以是亦可以是“1”，或者，或者(huzh)被訪問時的次序號；被訪問時的次序號；“FALSE”亦可亦可以是以是“0”。第49頁/共

31、80頁第五十頁，共80頁。a) 深度深度(shnd)優(yōu)先搜索法優(yōu)先搜索法(Depth-First Search)(縱向優(yōu)先搜索縱向優(yōu)先搜索)基本基本(jbn)思想：思想： 從圖G(V, R)中某一頂點v1出發(fā)訪問與v1相鄰的任意頂點w1 再從w1出發(fā)，訪問與w1鄰接且未被訪問過的頂點w2，再從w2出發(fā)，如此重復訪問其未被訪問的鄰接點，直至一個所有鄰接點都 被 訪問過的頂點wk。然后逐步退回到wk-1，wk-2，w1找到一個還有鄰接點未被訪問過的頂點wj(與樹的先根遍歷類似，是其推廣與樹的先根遍歷類似，是其推廣)第50頁/共80頁第五十一頁，共80頁。 從從wj出發(fā)重復出發(fā)重復(chngf)步，

32、直至所有頂步，直至所有頂點都被訪問過一次且僅一次。簡稱點都被訪問過一次且僅一次。簡稱“DFS”。v1,v2,v4,v8,v7,v3,v6,v5或或v1v3v2v4v5v6v7v8例：例：P168從從V1出發(fā)出發(fā)(chf)可能得到的訪問順序有：可能得到的訪問順序有：v1,v2,v5,v8,v4,v6,v3,v7v1,v3,v6,v8,v7,v5,v2,v4第51頁/共80頁第五十二頁，共80頁。DFS遞歸算法遞歸算法(sun f)如下：如下：P169void DFSTraverse(Graph G, Status (*Visit)(int v) / 對對圖圖G作深度優(yōu)先遍歷作深度優(yōu)先遍歷Visi

33、tFunc = Visit; for (v=0; vG.vexnum; + +v)visitedv = FALSE; / 訪問標志數(shù)組初始化訪問標志數(shù)組初始化if (!visitedv) DFS(G, v); / DFSTraverse/ 使用全局變量使用全局變量VisitFunc,使使DFS不必設函數(shù)指針參數(shù)不必設函數(shù)指針參數(shù)for (v=0; vG.vexnum; + +v)/- 算法使用的全局變量算法使用的全局變量-Boolean visitedMAX; / 訪問標志數(shù)組訪問標志數(shù)組Status (*VisitFunc)(int v); / 函數(shù)變量函數(shù)變量/ 對尚未訪問的頂點調(diào)用對尚未

34、訪問的頂點調(diào)用DFS第52頁/共80頁第五十三頁，共80頁。注：這是一個遞歸過程。附設訪問標志注：這是一個遞歸過程。附設訪問標志(biozh)數(shù)組數(shù)組Visitedn，初值為，初值為“FALSE”，一旦被訪問，其值則為，一旦被訪問，其值則為“TRUE”。void DFS (Graph G, int v) / 從第從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖圖Gfor (w=FirstAdjvex(G, v); w; w=NextAdjvex(G,v,w)visitedv = TRUE; VisitFunc(v); / 訪問第訪問第v個頂點個頂點if (!visitedw)

35、DFS(G, w); / DFS/ 對對v的尚未訪問的鄰接頂點的尚未訪問的鄰接頂點w遞歸調(diào)用遞歸調(diào)用DFS函數(shù)函數(shù)(hnsh)DFS算法如下：算法如下：P169第53頁/共80頁第五十四頁，共80頁。DFS非遞歸算法如下非遞歸算法如下(rxi)：(補充補充)void DFSTraverse(Graph G, Status (*Visit)(int v) / 按深度優(yōu)先按深度優(yōu)先非遞歸非遞歸遍歷遍歷圖圖G。/ 使用輔助棧使用輔助棧S和訪問標志數(shù)組和訪問標志數(shù)組visited。InitStack(S); / 置空輔助棧置空輔助棧Sfor (v=0; vG.vexnum; v)visitedv =

36、FALSE; / 訪問標志數(shù)組初始化訪問標志數(shù)組初始化if (!visitedv) / v尚未訪問尚未訪問 / DFSTraversefor (v=0; vG.vexnum; v)visitedv = TRUE; Visit(v); GetTop(S, u); / 棧頂元素出棧并置為棧頂元素出棧并置為uwhile ( !StackEmpty(S) for (w=FirstAdjvex(G, u); w; w=NextAdjvex(G, u, w)if (!visitedw) / w為為u的尚未訪問的鄰接點的尚未訪問的鄰接點visitedw = TRUE; Visit(w); Push(S, v

37、); / v入棧入棧Push(S, w); break; /ifif (!w) Pop(S, w); / while / if第54頁/共80頁第五十五頁，共80頁。例：上圖的鄰接例：上圖的鄰接(ln ji)表：表：v1246777652 1 1 5310 0 43 72 v2v3v4v5v6v7v812345670頭結點頭結點表結點表結點第55頁/共80頁第五十六頁，共80頁。v1，v3 ，v7 ，v8 ，v6 ，v5 ，v2 ，v4 若從另一頂點(dngdin)出發(fā)，則遍歷后可得另一序列。(此時算法要適當修改，如何修改？請思考)。第56頁/共80頁第五十七頁，共80頁。b) 廣度優(yōu)先搜索廣

38、度優(yōu)先搜索(su su)(Breadth-First Search)(橫向優(yōu)先橫向優(yōu)先搜索搜索(su su)基本基本(jbn)思想：思想： 從圖從圖G中的某一頂點中的某一頂點v1出發(fā)，訪問出發(fā)，訪問(fngwn)與頂與頂點點v1鄰接的全部鄰接頂點，鄰接的全部鄰接頂點，w1，w2，wx； 依次訪問與w1，w2，wx鄰接且未被訪問過的頂點，依此類推，直至所有頂點都 被訪問為止。上例圖進行廣度優(yōu)先搜索可得：v1，v2 ，v3 ，v4 ，v5 ，v6 ，v7 ，v8(與樹的層序遍歷類似，是其推廣與樹的層序遍歷類似，是其推廣) 注：該遍歷過程也要設一訪問標志數(shù)組，并且為了順次訪問路徑長度為注：該遍歷過程

39、也要設一訪問標志數(shù)組，并且為了順次訪問路徑長度為2，3，的頂點，還要設隊列，依次存儲被訪問的頂點。的頂點，還要設隊列，依次存儲被訪問的頂點。第57頁/共80頁第五十八頁，共80頁。BFS算法算法(sun f)如下：如下：P170void BFSTraverse(Graph G, Status (*Visit)(int v) / 按廣度優(yōu)先按廣度優(yōu)先非遞歸非遞歸遍歷遍歷圖圖G。/ 使用輔助隊列使用輔助隊列Q和訪問標志數(shù)組和訪問標志數(shù)組visited。InitQueue(Q); / 置空輔助隊列置空輔助隊列Qfor (v=0; vG.vexnum; v)visitedv = FALSE; / 訪問

40、標志數(shù)組初始化訪問標志數(shù)組初始化if (!visitedv) / v尚未訪問尚未訪問 / BFSTraversefor (v=0; vG.vexnum; v)visitedv = TRUE; Visit(v); DeQueue(Q, u); / 隊頭元素出隊并置為隊頭元素出隊并置為uwhile ( !QueueEmpty(Q) for (w=FirstAdjvex(G, u); w; w=NextAdjvex(G,u,w)if (!visitedw) / w為為u的尚未訪問的鄰接點的尚未訪問的鄰接點visitedw = TRUE; Visit(w); EnQueue(Q, v); / v入隊列

41、入隊列EnQueue(Q, w); / if / while / if第58頁/共80頁第五十九頁，共80頁。求圖的連通分量，實際上是圖的遍歷的一種應用。當無向圖是非連通時，從圖中的某一頂點v1為出發(fā)遍歷圖，只能訪問到包含頂點v1的圖的一個連通分量，而不能訪問圖中的所有頂點。若要求含n個頂點的圖的所有連通分量的頂點序列集，則可從任一新的頂點vi(1i n) 出發(fā)，反復(fnf)遍歷圖，即可求得該圖的全部連通分量。第59頁/共80頁第六十頁，共80頁。檢測圖中的每一個(y )頂點，若該頂點已被訪問，則該頂點已落在圖中已求得的某個連通分量上；若未被訪問，則從該頂點出發(fā)遍歷圖，便可求得圖的另一個(y

42、 )連通分量。如此重復即可求得所有的連通分量。第60頁/共80頁第六十一頁，共80頁。void component(G) / 求具有求具有n個頂點的圖個頂點的圖G的所有連通分量的所有連通分量for (i=1; in; i) visitedi = FALSE;for (i=1; in; i)if (!visitedi)BFSTraverse(G, i); / component求圖的連通求圖的連通(lintng)分分量算法：量算法：第61頁/共80頁第六十二頁，共80頁。例：例：945101176有三個連通(lintng)分量1382第62頁/共80頁第六十三頁，共80頁。7.4 生成生成(sh

43、n chn)樹和樹和最小生成最小生成(shn chn)樹樹設是一個有n個頂點的連通圖。 它的生成樹是一個極小連通子圖，即：它含有圖中的全部頂點，但只有足以構成(guchng)一棵樹的n1條邊。如：G=(V,T)是一棵生成樹，即G是的子圖，且G中含中的全部頂點，僅有足以構成(guchng)一棵樹的n1條邊，則子圖G是的一棵生成樹。 如果在一棵生成樹上添加一條邊，必定構成(guchng)一環(huán)。因此一棵有n個頂點的生成樹有且僅有n1條邊。 若少于n1條邊，則是非連通圖，若多于n1條邊，則一定有環(huán)。1) 生成樹生成樹第63頁/共80頁第六十四頁，共80頁。若從圖中任一頂點出發(fā)遍歷圖時，必定將E(G)分

44、成兩個子集，分別(fnbi)記為B(G)和T(G)，其中B(G)為遍歷過程中沒有走過的邊，T(G)為遍歷過程中走過的邊。則子圖G=(V, T)就是一棵生成樹。而按DFS方法得的生成樹為深度優(yōu)先生成樹，按BFS方法得到的生成樹為廣度優(yōu)先生成樹。第64頁/共80頁第六十五頁，共80頁。例：例：GDFS生成(shn chn)樹：BFS生成(shn chn)樹：第65頁/共80頁第六十六頁，共80頁。 對于非連通圖，每個連通分量(fn ling)均可生成一棵樹，構成該非連通圖的生成森林。2) 生成生成(shn chn)森林森林 生成樹及生成森林(snln)的算法：P171-1723) 算法算法第66頁

45、/共80頁第六十七頁，共80頁。作為圖的應用，若在n個城市之間建立通訊網(wǎng)絡，連通n個城市僅需n1條線路即可。而最大可能建立n(n1)/2條線路。每條線路的建立都必須花費(hufi)一定的代價，為節(jié)約起見，在建立n個城市的通訊網(wǎng)絡時，一般考慮： 建立建立(jinl)n1條線路條線路 建立花費代價最小的n1條線路第67頁/共80頁第六十八頁，共80頁。我們可以用連通網(wǎng)來表示：把每一個城市作為一個頂點，每兩個城市間的線路看成是關聯(lián)兩個頂點的邊，則可繪制出n個城市間的通訊線路圖正好是一棵生成樹(一個生成樹森林)，每個生成樹的每條線路所花費的代價作為相應邊的權，則生成樹稱為代價生成樹。因此建立n個城市的

46、通訊網(wǎng)問題(wnt)就成為建立一最小代價生成樹(Minimum Cost Spanning Tree) (簡稱為“最小生成樹”)的問題(wnt)。注：對注：對n個城市所建立個城市所建立(jinl)的的n1條邊的網(wǎng)條邊的網(wǎng)絡圖不唯一，可形成一個生成樹森林。絡圖不唯一，可形成一個生成樹森林。第68頁/共80頁第六十九頁，共80頁。一棵代價(diji)生成樹T的代價(diji)：則最小代價(diji)生成樹的代價(diji)為：1n1iiGW(T)WSTT|(T)MinW)(TWGminG其中，ST為生成(shn chn)樹森林。其中，Wi為第i條邊的權值第69頁/共80頁第七十頁，共80頁。如何構

47、造最小生成樹？其算法有多種。我們必須(bx)尋求一種方法，使得所構造的生成樹的代價最小。兩種基本方法是：普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法。例例 ：給定：給定(i dn)如下圖所示的網(wǎng)：如下圖所示的網(wǎng)：12456356611162133141819第70頁/共80頁第七十一頁，共80頁。設U(T)是已落在最小生成樹T中的頂點集合，若頂點v和w都落在U(T)中，即v到w有一條連通路徑，則邊(v,w)加入T中必然構成(guchng)回路。根據(jù)此思想，Prim提出了一種構造最小生成樹的算法，用文字描述為： 設集合設集合(jh)U(T)的初態(tài)為空，的初態(tài)為空， 在連通圖上任選在連通圖上任選(rn xun)一頂點一頂點vi加入到加入到U(T)中中1) 普里姆普里姆(Prim)算法算法第71頁/共80頁第七十二頁，共80頁。 將下列步驟重復將下列步驟重復n1次次(或直到或直到(zhdo)U(T)=V為止為止)；a) 從一頂點(dngdin)屬于U(T) ，而另一頂點(dngdin)不屬于U(T)的邊中找權值最小的邊(vi,vj) (vi U(T)