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

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

2、表示成： (Vi, Vj)無(wú)序的對(duì)偶稱為邊，即(Vi, Vj)=(Vj, Vi) ，其圖稱為無(wú)向圖 有序的對(duì)偶稱為弧，即 ，則稱Vi為弧尾，稱Vj為弧頭，該圖稱為有向圖8.1.1 圖的定義有向圖和無(wú)向圖示例：無(wú)向圖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. 端點(diǎn)和鄰接點(diǎn) 在一個(gè)無(wú)向圖中,若存在一條邊(vi,vj),則稱vi和vj為此邊的兩個(gè)端點(diǎn),并稱它們互為鄰接點(diǎn)。 在一個(gè)有向圖中,若

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

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

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

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

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

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

9、關(guān)系的矩陣。設(shè)G=(V,E)是具有n(n0)個(gè)頂點(diǎn)的圖,頂點(diǎn)的順序依次為(v0,v1,vn-1),則G的鄰接矩陣A是n階方陣即二維數(shù)組Ann,其定義如下（規(guī)定自身無(wú)邊、無(wú)?。?.2.1 鄰接矩陣存儲(chǔ)方法a ij=0 vi與vj無(wú)邊1 vi與vj有邊無(wú)向圖a ij=0 vi到vj無(wú)弧1 vi到vj有弧有向圖a ij=或0 vi與vj無(wú)邊（或vi到vj無(wú)?。﹚ vi與vj有邊（或vi到vj有?。┚W(wǎng)W 表示邊上的權(quán)值； 0 表示vi與vj是同一個(gè)頂點(diǎn) 表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。 1、舉例無(wú)向圖鄰接矩陣表示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 特點(diǎn)：對(duì)稱行或列方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的度無(wú)向網(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鄰接矩陣表示特點(diǎn)：不一定對(duì)稱行方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的出度列方向的非零元素（或1）的個(gè)數(shù)為此頂點(diǎn)的入度V1V2V3V4V1V2V3V4注意：1) 圖中無(wú)鄰接到自身的弧，因此鄰接矩陣主對(duì)角線為

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

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

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

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

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

16、struct ANode *nextarc; /*指向下一條弧的指針*/ InfoType info; /*該弧的相關(guān)信息*/ ArcNode;typedef struct Vnode /*鄰接表頭結(jié)點(diǎn)的類型*/Vertex data; /*頂點(diǎn)信息*/ ArcNode *firstarc; /*指向第一條弧*/ VNode;typedef VNode AdjListMAXV;/*AdjList是鄰接表類型*/typedef struct AdjList adjlist; /*鄰接表*/ int n,e; /*圖中頂點(diǎn)數(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例：圖的鄰接表存儲(chǔ)表示有向圖的鄰接表1 4230 12 0 1 2 3 4 A B C D EABECD可見，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧ABECD有向圖的逆鄰接表A B C D E 30342001234在有向圖的逆鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧課堂作業(yè)：選擇題：1.設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為n,則圖G中最少有( )條邊A.n(n-1) B.n-1 C.n+1 D.2n2.若圖G為n個(gè)頂點(diǎn)的有向圖,則圖G中最多有( )條邊A.n(n-1) B.n-1 C.n(n+1) D.n+1 3.在一個(gè)圖

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

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

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

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

22、FS()的執(zhí)行過程,見教材。void DFS(ALGraph *G,int v) ArcNode *p; visitedv=1; /*置已訪問標(biāo)記*/ printf(%d ,v); /*輸出被訪問頂點(diǎn)的編號(hào)*/ p=G-adjlistv.firstarc; /*p指向頂點(diǎn)v的第一條弧的弧頭結(jié)點(diǎn)*/ while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); /*若p-adjvex頂點(diǎn)未訪問,遞歸訪問它*/ p=p-nextarc; /*p指向頂點(diǎn)v的下一條弧的弧頭結(jié)點(diǎn)*/ 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ī)定訪問鄰接點(diǎn)的順序，DFS序列不是唯一的序列2： V0,V1,V4,V7,V3,V2,V5,V6注意:深度優(yōu)先遍歷的訪問順序與圖的鄰接表存儲(chǔ)狀態(tài)有關(guān)，從剛才寫出的遍歷結(jié)果可以看出，從某一個(gè)頂點(diǎn)出發(fā)的遍歷結(jié)果是不唯一的。但是,但采用鄰接矩陣或鄰接表存儲(chǔ)結(jié)構(gòu)內(nèi)容已確定的圖,則從某一頂點(diǎn)出發(fā)的遍歷結(jié)果應(yīng)是唯一的。 由于圖的鄰接表不是唯一的，因此對(duì)于同一個(gè)圖，其深度優(yōu)先遍歷輸出的結(jié)果也可能是不同的。 例：從頂點(diǎn)v1出發(fā)，DFS下圖。頂點(diǎn)訪問序列為：v1,v2,v4,v8,v5,v3,v

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

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

26、v4v5v1v2v3v4v5v6v7v8例圖及其鄰接表表示以v1為遍歷的起點(diǎn)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練習(xí)題：對(duì)于下面一個(gè)圖及其存儲(chǔ)結(jié)構(gòu)，寫出以v

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

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

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

41、列Q，保存已訪問的頂點(diǎn)，并控制遍歷頂點(diǎn)的順序。算法描述： (1) 定義一個(gè)隊(duì)列Q并初始化 (2) 開始頂點(diǎn)（如 v）入隊(duì)，置訪問標(biāo)記為1； (3) 當(dāng)隊(duì)列不空時(shí)，反復(fù)做：(a)隊(duì)頭頂點(diǎn)出隊(duì)w ，訪問w；(b)尋找w的所有未被訪問的鄰接頂點(diǎn)入隊(duì)，置訪問標(biāo)記為1；2 .bfs算法實(shí)現(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）全局標(biāo)記數(shù)組int visitedMAX; visitedi= 0 i號(hào)頂點(diǎn)未被訪問 1 i號(hào)頂點(diǎn)已被訪問2）鄰接表存儲(chǔ)結(jié)構(gòu)void BFS(ALGraph *G,int v) ArcNode *p; int w,i; int queueMAXV,front=0,rear=0;/*定義循環(huán)隊(duì)列*/ int visitedMAXV; /*定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組*/ for (i=0;in;i+) visitedi=0; /*訪問標(biāo)志數(shù)組初始化*/ printf(%2d,v); /*輸出被訪問頂點(diǎn)的編號(hào)*/ visitedv=1; /*置已訪問標(biāo)記*/ rear

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

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

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

46、23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v1v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v2v3v301v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v2v3v301v12v23V34V

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

48、2v8v3v7v3v6v4v5v1隊(duì)列v2v2v3v3v4v4v5V2的鄰接點(diǎn)v5沒有被訪問過，訪問之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v3v4v4v5v501v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v3v4v4v5v501v12

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

50、v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v3v4v4v5v5v6v601v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v3v4v4v5v5v6v6v7V3的鄰接點(diǎn)v7沒有被訪問過，訪問之，且入隊(duì)列01v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2

51、v8v3v7v3v6v4v5v1隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v4v4v5v5v6v6v7v701v12v23V34V45v56v67v78v8v2v3v1v4v5v1v6v7v2v8v2v8v3v7v3v6v4v5v1隊(duì)列v2v3v4v4v5v5v6v6v7v7V4的鄰接點(diǎn)v

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