數(shù)據(jù)結(jié)構(gòu)教程第7單元-圖

1、數(shù)據(jù)結(jié)構(gòu)教程8 圖授課老師：彭偉國計算機學院8.1 圖的基本概念第8章 圖8.2 圖的存儲結(jié)構(gòu)8.3 圖的遍歷8.4 生成樹和最小生成樹8.5 最短路徑8.6 拓撲排序8.7 AOE網(wǎng)與關(guān)鍵路徑8.1 圖的基本概念 圖最常見的應(yīng)用是在交通運輸和通信網(wǎng)絡(luò)中找出造價最低的方案。通信網(wǎng)絡(luò)示例如下圖所示： 圖G是由一個頂點集V和一個邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。記為二元組形式： G= (V, E) 其中: V是由頂點構(gòu)成的非空有限集合，記為：VV0, V1, V2, Vn-1 E是由V中頂點的對偶構(gòu)成的有限集合，記為：E=(V0, V2), (V3, V4), ，若E為空，則圖中只有頂點而沒有邊。其中對偶可以

2、表示成： (Vi, Vj)無序的對偶稱為邊，即(Vi, Vj)=(Vj, Vi) ，其圖稱為無向圖 有序的對偶稱為弧，即 ，則稱Vi為弧尾，稱Vj為弧頭，該圖稱為有向圖8.1.1 圖的定義有向圖和無向圖示例：無向圖G1的二元組表示：V(G1)=V1, V2, V3, V4E(G1)=(V1, V2)，(V1, V3)，(V1, V4)，(V2, V3)，(V2, V4)，(V3, V4)有向圖G3的二元組表示： V(G3)=V1, V2, V3 E(G3)=，1. 端點和鄰接點 在一個無向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個端點,并稱它們互為鄰接點。 在一個有向圖中,若

3、存在一條邊,則稱此邊是頂點vi的一條出邊,同時也是頂點vj的一條入邊；稱vi和vj分別為此邊的起始端點(簡稱為起點)和終止端點(簡稱終點)；稱vi和vj互為鄰接點。8.1.2 圖的基本術(shù)語 2頂點的度、入度和出度在無向圖中，與頂點v相鄰接的邊數(shù)稱為該頂點的度，記為D(v)。在有向圖中，頂點v的度又分為入度和出度兩種：以頂點v為終點(弧頭)的弧的數(shù)目稱為頂點v的入度，記為ID(v)；以頂點v為起點(弧尾)的弧的數(shù)目稱為頂點v的出度，記為OD(v)；有向圖頂點v的度為該頂點的入度和出度之和，即 D(v)=ID(v)+OD(v)無論是有向圖還是無向圖，一個圖的頂點數(shù)n、邊(弧)數(shù)e和每個頂點的度di

4、之間滿足以下的關(guān)系式：即在有向圖或無向圖中：所有頂點度數(shù)之和 ：邊數(shù) = 2 ：13完全圖、稠密圖和稀疏圖在圖G中：若G為無向圖，任意兩個頂點之間都有一條邊，稱G為無向完全圖。頂點數(shù)為n，無向完全圖的邊數(shù)：e=n(n1)/2若G為有向圖，任意兩個頂點Vi, Vj之間都有弧 、 ，稱G為有向完全圖。如頂點數(shù)為n，有向完全圖的弧數(shù)： e =n(n1)例如，無向圖G1就是4個頂點無向完全圖。若一個圖接近完全圖，則稱其為稠密圖；反之，若一個圖含有很少條邊或?。磂n2），則稱其為稀疏圖。4子圖若有圖G=(V, E)和G=(V, E) 且V 是V的子集，即V V ，E是E的子集，即E E則稱圖G為圖G的

5、子圖。5路徑、回路和路徑長度在無向圖G中，若存在一個頂點序列(Vp , Vi1 , Vi2 , , Vin , Vq)，使(Vp, Vi1)，(Vi1, Vi2)，(Vin, Vq)均為圖G的邊，則該稱頂點的序列為頂點Vp到頂點Vq的路徑。若G是有向圖，則路徑是有向的。路徑長度定義為路徑上的邊數(shù)或者弧的數(shù)目。若一條路徑中不出現(xiàn)重復(fù)頂點，則稱此路徑為簡單路徑。若一條路徑的起點和終點相同（Vp=Vq）稱為回路或環(huán)。除了起點和終點相同外，其余頂點不相同的回路，稱為簡單回路或簡單環(huán)。例如，在無向圖G1中：頂點序列（V1, V2, V3, V4）是一條從頂點V1到頂點V4，長度為3的簡單路徑；頂點序列（

6、V1, V2, V4, V1, V3）是一條從頂點V1到頂點V3，長度為4的路徑，但不是簡單路徑；頂點序列（V1, V2, V3, V1）是一條長度為3的簡單回路。在有向圖G3中：頂點序列（V2, V3, V2）是一個長度為2的有向簡單環(huán)。6連通、連通分量和連通圖、生成樹在無向圖G中：如果從頂點Vi 到頂點Vj至少有一條路徑，則稱Vi與Vj是連通的。如果圖中任意兩個頂點都連通，則稱G為連通圖，否則稱為非連通圖。在非連通圖G中，任何一個極大連通子圖稱為G的連通分量。任何連通圖的連通分量只有一個，即其自身，而非連通圖有多個連通分量。在一個連通圖中，含有全部頂點的極小(邊數(shù)最少)連通子圖，稱為該連通

7、圖的生成樹。(包含圖的所有 n 個結(jié)點，但只含圖的 n-1 條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán))非連通圖G4ABCDEFGIJKABCDEIJKFG非連通圖G4的三個連通分量連通圖G5ABCD連通圖G5的兩棵生成樹ABCDABCD7強連通、強連通分量和強連通圖在有向圖G中：存在從頂點Vi 到頂點Vj的路徑，也存在從頂點Vj 到頂點Vi的路徑，則稱Vi與Vj是強連通的。如果圖中任意兩個頂點都是強連通，則稱G為強連通圖，否則稱為非強連通圖。在非強連通圖G中，任何一個極大強連通子圖稱為G的強連通分量。任何強連通圖的強連通分量只有一個，即其自身，而非強連通圖有多個強連通分量。有向圖G和

8、強連通分量示例： 8權(quán)、帶權(quán)圖、有向網(wǎng)和無向網(wǎng)在一個圖中，各邊(或弧)上可以帶一個數(shù)值，這個數(shù)值稱為權(quán)。這種每條邊都帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)有向網(wǎng)：帶權(quán)有向圖無向網(wǎng)：帶權(quán)無向圖 例8.1 有n個頂點的有向強連通圖最多需要多少條邊？最少需要多 少條邊？ 答：有n個頂點的有向強連通圖最多有n(n-1)條邊(構(gòu)成一個有向完全圖的情況)；最少有n條邊(n個頂點依次首尾相接構(gòu)成一個環(huán)的情況)。 8.2 圖的基本存儲結(jié)構(gòu)圖需存儲的信息：各頂點的數(shù)據(jù)各個邊（?。┑男畔?，包括：哪兩個頂點有邊（?。┤粲袡?quán)要表示出來頂點數(shù)、邊（?。?shù) V0 V4 V3 V1 V2 V0 V1 V2 V3 鄰接矩陣是表示頂點之間相鄰

9、關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n0)個頂點的圖,頂點的順序依次為(v0,v1,vn-1),則G的鄰接矩陣A是n階方陣即二維數(shù)組Ann,其定義如下（規(guī)定自身無邊、無?。?.2.1 鄰接矩陣存儲方法a ij=0 vi與vj無邊1 vi與vj有邊無向圖a ij=0 vi到vj無弧1 vi到vj有弧有向圖a ij=或0 vi與vj無邊（或vi到vj無?。﹚ vi與vj有邊（或vi到vj有?。┚W(wǎng)W 表示邊上的權(quán)值； 0 表示vi與vj是同一個頂點 表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。 1、舉例無向圖鄰接矩陣表示0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00

10、1 1 0 0V1V2 V4 V5 V3 特點：對稱行或列方向的非零元素（或1）的個數(shù)為此頂點的度無向網(wǎng)V1V2 V4 V5 V3 254311鄰接矩陣表示0 2 4 2 0 1 5 1 0 3 1 4 3 0 5 1 0 V1V2V3V4V5V1V2V3V4V5V1V2V3V4V5V1V2V3V4V51、舉例有向圖V1V2 V3 V4 0 1 1 00 0 0 00 0 0 11 0 0 0鄰接矩陣表示特點：不一定對稱行方向的非零元素（或1）的個數(shù)為此頂點的出度列方向的非零元素（或1）的個數(shù)為此頂點的入度V1V2V3V4V1V2V3V4注意：1) 圖中無鄰接到自身的弧，因此鄰接矩陣主對角線為

11、全零。2) 無向圖的鄰接矩陣必然是對稱矩陣。3) 無向圖中，頂點的度是鄰接矩陣對應(yīng)行（或列）的非零元素之和；有向圖中，對應(yīng)行的非零元素之和是該頂點的出度；對應(yīng)列的非零元素之和是該頂點的入度；則該頂點的度是對應(yīng)行和對應(yīng)列的非零元素之和。容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。⒄翼旤c的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：2、鄰接矩陣法特點3.鄰接矩陣的數(shù)據(jù)類型定義如下：#define MAXV typedef struct int no;/*頂點編號*/ InfoType in

12、fo; /*頂點其他信息*/ VertexType;/*頂點類型*/typedef struct /*圖的定義*/ int edgesMAXVMAXV; /*鄰接矩陣*/ int vexnum,arcnum; /*頂點數(shù),弧數(shù)*/ VertexType vexsMAXV;/*存放頂點信息*/ MGraph; /* 圖類型 */注：MGraph 既可以表示有向圖、無向圖，也可以表示有整型權(quán)的網(wǎng) 8.2.2 鄰接表存儲方法 圖的鄰接表存儲方法是一種順序分配與鏈式分配相結(jié)合的存儲方法。在鄰接表中,對圖中每個頂點建立一個單鏈表,第i個單鏈表中的結(jié)點表示依附于頂點vi的邊(對有向圖是以頂點vi為尾的弧)

13、。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點和表頭結(jié)點的結(jié)構(gòu)如下： 表結(jié)點 表頭結(jié)點advexnextarcinfodatafirstarc 類似樹的孩子鏈表。即對圖中的每個頂點vi建立一個單鏈表，表中結(jié)點表示依附于該頂點vi的邊或弧，表結(jié)點由三個域組成，表頭結(jié)點由兩個域組成。鄰接點域adjvex鏈域nextarc數(shù)據(jù)域info指示與頂點vi鄰接的點在圖中的位置指示下一條邊或弧的結(jié)點存儲和邊或弧相關(guān)的信息，如權(quán)值數(shù)據(jù)域data鏈域firstarc指向鏈表第一個結(jié)點存儲頂點vi和其他有關(guān)信息表結(jié)點表頭結(jié)點無向圖鄰接表表示V1V2 V4 V5 V3 頂點的度：該頂點所在單鏈表中表結(jié)點個數(shù)無向網(wǎng)V1V2

14、V4 V5 V3 254311鄰接表表示V1V2V3V4V501234130420212143V1V2V3V4V501234123402452111413304231521與頂點V1相鄰接的頂點在數(shù)組中的下標權(quán)值1、舉例1、舉例有向圖V1V2 V3 V4 鄰接表表示12V1V2V3V4012330以頂點V1為始點的弧的終點頂點在數(shù)組中的下標頂點的出度該頂點所在單鏈表中表結(jié)點個數(shù)頂點的入度查詢整個鄰接表中的表結(jié)點，與該頂點的序號（數(shù)組下標）一致的表結(jié)點個數(shù)注意：在無向圖的鄰接表中，1）第i個鏈表中結(jié)點數(shù)目為頂點i的度；2）所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)；3）占用的存儲單元數(shù)目為n+2e。在有

15、向圖的鄰接表中，1）第i個鏈表中結(jié)點數(shù)目為頂點i的出度；2）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；3）占用的存儲單元數(shù)目為n+e。 為求出每一個頂點的入度，必須另外建立有向圖的逆鄰接表。有向圖的逆鄰接表與鄰接表類似，只是它是從入度考慮結(jié)點，而不是從出度考慮結(jié)點。24 4 3 2 11 逆鄰接表3V1V3V2V4鄰接表的缺點：鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；判斷任意兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。2、鄰接表法特點3.鄰接表存儲結(jié)構(gòu)的定義如下：typedef struct ANode /*弧的結(jié)點結(jié)構(gòu)類型*/int adjvex; /*該弧的終點位置*/

16、struct ANode *nextarc; /*指向下一條弧的指針*/ InfoType info; /*該弧的相關(guān)信息*/ ArcNode;typedef struct Vnode /*鄰接表頭結(jié)點的類型*/Vertex data; /*頂點信息*/ ArcNode *firstarc; /*指向第一條弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中頂點數(shù)n和邊數(shù)e*/ ALGraph; /*圖的類型*/0 A 1 41 B 0

17、 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE例：圖的鄰接表存儲表示有向圖的鄰接表1 4230 12 0 1 2 3 4 A B C D EABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧ABECD有向圖的逆鄰接表A B C D E 30342001234在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧課堂作業(yè)：選擇題：1.設(shè)無向圖G中頂點數(shù)為n,則圖G中最少有( )條邊A.n(n-1) B.n-1 C.n+1 D.2n2.若圖G為n個頂點的有向圖,則圖G中最多有( )條邊A.n(n-1) B.n-1 C.n(n+1) D.n+1 3.在一個圖

18、G中,所有頂點的度數(shù)之和等于所有邊數(shù)的( )倍A.3 B.1/2 C.4 D.24.在具有n個頂點的無向完全圖G中邊的總數(shù)為( )A. n+1 B.n(n-1)/2 C.n(n+1) D.n-15.在具有6個頂點的無向圖G中至少應(yīng)有( )條邊才能確保是一個連通圖.A. 8 B. 7 C. 6 D. 56.對于一個具有n個頂點的無向圖,若采用鄰接矩陣表示,則該矩陣的大小是( )A.n-1 B.n+1 C.n2 D. (n-1)2答案：BADBDC8.3 圖的遍歷8.3.1 圖的遍歷的概念 從給定圖中任意指定的頂點(稱為初始點)出發(fā),按照某種搜索方法沿著圖的邊訪問圖中的所有頂點,使每個頂點僅被訪問

19、一次,這個過程稱為圖的遍歷。如果給定圖是連通的無向圖或者是強連通的有向圖,則遍歷過程一次就能完成,并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。 根據(jù)搜索方法的不同,圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法(DFS)；另一種叫做廣度優(yōu)先搜索法(BFS)。 深度優(yōu)先搜索(Depth_First Search)是指按照深度方向搜索，它類似于樹的先根遍歷。深度優(yōu)先搜索的基本思想是： 從圖中某個頂點vi出發(fā)，首先訪問vi 。 找出頂點vi的第一個未被訪問的鄰接點v j，然后訪問頂點v j。找出頂點v j的第一個未被訪問的鄰接點vj1，,重復(fù)本步驟，直到頂點v j1的所有的鄰接點都被訪問為止。

20、8.3.2 圖的深度優(yōu)先搜索 返回前一個訪問過的且仍有未被訪問的鄰接點的頂點，找出并訪問該頂點的下一個末被訪問的鄰接點，然后執(zhí)行步驟。否則行步驟。 若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復(fù)上述搜索過程，直至圖中所有頂點均被訪問過為止。深度優(yōu)先搜索的示例ACDEGBFIHACDEGBFIH123456789123456789前進回退深度優(yōu)先搜索過程 深度優(yōu)先生成樹acbdegfF F F F F F F TTTTTTTacbdgfe acbgfed訪問標志:訪問次序:例如:0 1 2 3 4 5 6 0234516如何判別V的鄰接點是否被訪問？解決的辦法是：為每個

21、頂點設(shè)立一個 “訪問標志 visitedw”。DFS 在訪問圖中某一起始頂點 v 后, 由v出發(fā), 訪問它的任一鄰接頂點 w1; 再從w1出發(fā),訪問與w1鄰接但還沒有訪問過的頂點w2; 然后再從w2 出發(fā),進行類似的訪問, 如此進行下去, 直至到達所有的鄰接頂點都被訪問過的頂點 u 為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發(fā),進行與前述類似的訪問; 如果沒有, 就再退回一步進行搜索。重復(fù)上述過程, 直到連通圖中所有頂點都被訪問過為止。 例如,以上圖的鄰接表為例調(diào)用DFS()函數(shù),假設(shè)初始頂點編號v=2,給出調(diào)用D

22、FS()的執(zhí)行過程,見教材。void DFS(ALGraph *G,int v) ArcNode *p; visitedv=1; /*置已訪問標記*/ printf(%d ,v); /*輸出被訪問頂點的編號*/ p=G-adjlistv.firstarc; /*p指向頂點v的第一條弧的弧頭結(jié)點*/ while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若p-adjvex頂點未訪問,遞歸訪問它*/ p=p-nextarc; /*p指向頂點v的下一條弧的弧頭結(jié)點*/ V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V3 V2

23、 V7 V6 V5 V4例序列1： V0,V1,V3,V7,V4,V2,V5,V6從v0出發(fā)的DFS序列為：由于沒有規(guī)定訪問鄰接點的順序，DFS序列不是唯一的序列2： V0,V1,V4,V7,V3,V2,V5,V6注意:深度優(yōu)先遍歷的訪問順序與圖的鄰接表存儲狀態(tài)有關(guān)，從剛才寫出的遍歷結(jié)果可以看出，從某一個頂點出發(fā)的遍歷結(jié)果是不唯一的。但是,但采用鄰接矩陣或鄰接表存儲結(jié)構(gòu)內(nèi)容已確定的圖,則從某一頂點出發(fā)的遍歷結(jié)果應(yīng)是唯一的。 由于圖的鄰接表不是唯一的，因此對于同一個圖，其深度優(yōu)先遍歷輸出的結(jié)果也可能是不同的。 例：從頂點v1出發(fā)，DFS下圖。頂點訪問序列為：v1,v2,v4,v8,v5,v3,v

24、6,v7v1v6v2v5v3v8v4v7連通圖的深度優(yōu)先搜索遍歷從圖中某個頂點V0 出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到。V0w1w3w2w4w5w6w8w7w10w9w11G1G2G3V0w1w3w2由此可以看出:1. 從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;2. 如何判別V的鄰接點是否被訪問？解決的辦法是:為每個頂點設(shè)立一個 “訪問標志 visitedw”;非連通圖的深度優(yōu)先搜索遍歷 以鄰接矩陣作為存儲結(jié)構(gòu),實現(xiàn)非連通圖的深度優(yōu)先搜索遍歷。對于非連通圖，一次遍歷僅能訪問開始頂點所在連通分量中的每

25、個頂點，其他連通分量中的頂點則無法訪問到。因此，對于非連通圖，在遍歷完一個連通分量之后，還要再選擇一個開始頂點，遍歷下一個連通分量，重復(fù)這個過程，直到圖中的所有頂點abchdekfg812345670achkfedbg例如:訪問次序:achdkfe bg分析 采用鄰接鏈表來表示圖時，需要訪問表頭向量時間為O(n)。而外接的邊結(jié)點無向圖為2e（e為圖的邊數(shù)）個，有向圖為e個，時間消耗大約為O(e)。因此DFS算法的時間復(fù)雜度為O(n+e)。 對于邊數(shù)很少的圖適合采用鄰接表存儲結(jié)構(gòu) .01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6

26、v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示以v1為遍歷的起點01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,

27、v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v

28、5,v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v

29、2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v

30、5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8

31、v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3

32、v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1v3,v2v1v5,v4v2,v8v4,v5v2v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5

33、v2v8,v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v6v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v

34、1v7,v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v

35、2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1

36、,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2

37、v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5,v1,v2v1v5,v4v2,v8v4,v5v2v8,v3v1v7,v6v3,v7v3v6練習題：對于下面一個圖及其存儲結(jié)構(gòu)，寫出以v

38、2、v8為起始點的深度優(yōu)先遍歷序列。01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示答案為：以v2為起始點：v2-v1-v3-v6-v7-v4-v8-v5以v8為起始點：v8-v4-v2-v1-v3-v6-v7-v5 廣度優(yōu)先搜索(Breadth First Search) 是指照廣度方向搜索，和深度優(yōu)先搜索不同的是：廣度優(yōu)先搜索先訪問完所有的鄰接點，再去尋找與鄰接點相鄰的下一層的其他頂點，它類似于樹的層次遍歷。 廣度優(yōu)先搜索的基本思想是： 從圖中某個頂點v0出發(fā)，首先訪

39、問v0 。 依次訪問v0的各個末被訪問的鄰接點。8.3.3 廣度優(yōu)先搜索 分別從這些鄰接點(端結(jié)點)出發(fā)，依次訪問它們的各個末被訪問的鄰接點(新的端結(jié)點)。訪問時應(yīng)保證：如果vi和vk為當前結(jié)點，且vi在vk之前被訪問，則vi的所有末被訪問的鄰接點應(yīng)在vk的所有未被訪問的鄰接點之前訪問。重復(fù)步驟，直到所有結(jié)點均沒有末被訪問的鄰接點為止。 若此時還有頂點末被訪問，則選一個未被訪問的頂點作為起始點，重復(fù)上述過程，直至所有頂點均被訪問過為止。 V0 V7 V6 V5 V4 V3 V2 V1V0 V1 V3 V2 V7 V6 V5 V4求圖G 的以V0起點的的廣度優(yōu)先序列: V0,V1,V2,V3,V

40、4,V5,V6,V7例c0c1c3c2c4c5從C0出發(fā)的BFS序列為：由于沒有規(guī)定訪問鄰接點的順序，BFS序列不是唯一的c0 c1 c2 c3 c4 c5從圖中某頂點vi出發(fā)：1）訪問頂點vi ；（容易實現(xiàn)）2）訪問vi 的所有未被訪問的鄰接點w1 ,w2 , wk ； 3）依次從這些鄰接點（在步驟 2）訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；為實現(xiàn) 3），需要保存在步驟2）中訪問的頂點，而且訪問這些頂點鄰接點的順序為：“先被訪問先出發(fā)”的原則。故用隊列來管理鄰接點出發(fā)的次序。2 .bfs算法實現(xiàn)在廣度優(yōu)先遍歷算法中，需設(shè)置一隊

41、列Q，保存已訪問的頂點，并控制遍歷頂點的順序。算法描述： (1) 定義一個隊列Q并初始化 (2) 開始頂點（如 v）入隊，置訪問標記為1； (3) 當隊列不空時，反復(fù)做：(a)隊頭頂點出隊w ，訪問w；(b)尋找w的所有未被訪問的鄰接頂點入隊，置訪問標記為1；2 .bfs算法實現(xiàn)Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4F F F F F F F F FTTTTTTTTT0 1 2 3 4 5 6 7 8VisitedQV訪問次序:w1w2w8w4w7w3w5w6QUEUEV0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7 V0 V7 V6 V5 V4

42、V3 V2 V1數(shù)據(jù)結(jié)構(gòu)：1）全局標記數(shù)組int visitedMAX; visitedi= 0 i號頂點未被訪問 1 i號頂點已被訪問2）鄰接表存儲結(jié)構(gòu)void BFS(ALGraph *G,int v) ArcNode *p; int w,i; int queueMAXV,front=0,rear=0;/*定義循環(huán)隊列*/ int visitedMAXV; /*定義存放結(jié)點的訪問標志的數(shù)組*/ for (i=0;in;i+) visitedi=0; /*訪問標志數(shù)組初始化*/ printf(%2d,v); /*輸出被訪問頂點的編號*/ visitedv=1; /*置已訪問標記*/ rear

43、=(rear+1)%MAXV; queuerear=v; /*v進隊*/while (front!=rear) /*若隊列不空時循環(huán)*/ front=(front+1)%MAXV; w=queuefront; /*出隊并賦給w*/ p=G-adjlistw.firstarc; /*找w的第一個的鄰接點*/ while (p!=NULL) if (visitedp-adjvex=0) printf(“%2d”,p-adjvex); /*訪問之*/visitedp-adjvex=1; rear=(rear+1)%MAXV;/*該頂點進隊*/queuerear=p-adjvex; p=p-nexta

44、rc; /*找下一個鄰接頂點*/ printf(n);01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示以v1為遍歷的起點01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5隊列v1訪問v101v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1V1入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1

45、v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1取隊頭元素01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1v2V1的鄰接點v2沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1v2v201v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1v2v2v3V1的鄰接點v3沒有被訪問過，訪問之，且入隊列01v12v

46、23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v301v12v23V34V

47、45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v3V2的鄰接點v1已經(jīng)被訪問過不再訪問01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v3v4V2的鄰接點v4沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v3v4v401v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v

48、2v8v3v7v3v6v4v5v1隊列v2v2v3v3v4v4v5V2的鄰接點v5沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v501v12

49、v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v5V3的鄰接點v1已經(jīng)被訪問過不再訪問01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v5v6V3的鄰接點v6沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8

50、v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v5v6v6v7V3的鄰接點v7沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2

51、v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v7V4的鄰接點v

52、2已經(jīng)被訪問過不再訪問01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v7v8V4的鄰接點v8沒有被訪問過，訪問之，且入隊列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3v4v5v5v6v6v7v7v8v801v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊列v2v3