數(shù)據(jù)結(jié)構(gòu)-圖(1)

1、第第7章章 圖圖 電子科技大學(xué)電子科技大學(xué)第第7章章 圖圖 樹的存儲結(jié)構(gòu)：樹的存儲結(jié)構(gòu)：n雙親表示法雙親表示法n孩子表示法孩子表示法n孩子兄弟表示法孩子兄弟表示法思路：思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。n左指針指向該結(jié)點的第一個孩子；左指針指向該結(jié)點的第一個孩子；n右指針指向該結(jié)點的下一個兄弟結(jié)點。右指針指向該結(jié)點的下一個兄弟結(jié)點。 data firstChild nextSibling指向左孩子指向左孩子指向右兄弟指向右兄弟雙親只管長子雙親只管長子長子連接兄弟長子連接兄弟第第7章章 圖圖 樹和二叉樹之間的轉(zhuǎn)換：樹和二叉樹

2、之間的轉(zhuǎn)換：方法：方法：加線加線抹線抹線旋轉(zhuǎn)旋轉(zhuǎn) abeidfhgcabeidfhgc兄弟相連兄弟相連長兄為父長兄為父孩子靠左孩子靠左第第7章章 圖圖 二叉樹還原為樹二叉樹還原為樹abeidfhgc要點：要點：把所有右孩子變?yōu)樾值?！把所有右孩子變?yōu)樾值埽?abeidfhgc第第7章章 圖圖 l森林轉(zhuǎn)換為二叉樹：將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹，森林轉(zhuǎn)換為二叉樹：將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹，形成若干個二叉樹的森林；第一棵二叉樹不動，從第二棵二形成若干個二叉樹的森林；第一棵二叉樹不動，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前

3、一棵二叉樹根結(jié)點的右孩子，根結(jié)點的右孩子， 當所有二叉樹連在一起后，所得到的二叉當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。樹就是由森林轉(zhuǎn)換得到的二叉樹。 l二叉樹還原為森林：將二叉樹中根結(jié)點與其右孩子連線，及二叉樹還原為森林：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成一組沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成一組孤立的二叉樹；將孤立的二叉樹依次還原成樹孤立的二叉樹；將孤立的二叉樹依次還原成樹第第7章章 圖圖 樹的遍歷：樹的遍歷：n先根遍歷先根遍歷等同于轉(zhuǎn)換的二叉樹進行等同于轉(zhuǎn)換的二叉樹進行先序遍歷先序遍歷n后根遍歷后

4、根遍歷-等同于轉(zhuǎn)換的二叉樹進行等同于轉(zhuǎn)換的二叉樹進行中序遍歷中序遍歷森林的遍歷：森林的遍歷：n先序遍歷先序遍歷等同于轉(zhuǎn)換的二叉樹進行等同于轉(zhuǎn)換的二叉樹進行先序遍歷先序遍歷n中序遍歷中序遍歷等同于轉(zhuǎn)換的二叉樹進行等同于轉(zhuǎn)換的二叉樹進行中序遍歷中序遍歷第第7章章 圖圖 哈夫曼樹（哈夫曼樹（Huffman）樹是一類帶權(quán)路徑長度）樹是一類帶權(quán)路徑長度(WPL)最短的樹最短的樹構(gòu)造構(gòu)造 Huffman樹算法樹算法1) 以權(quán)值分別為以權(quán)值分別為W1,W2的各結(jié)點，構(gòu)成的各結(jié)點，構(gòu)成n棵棵二叉樹二叉樹T1,T2,Tn并組成森林并組成森林F=T1,T2,Tn,其中每棵二叉樹其中每棵二叉樹 Ti僅有一個權(quán)值為僅

5、有一個權(quán)值為 Wi的根結(jié)點；的根結(jié)點；2) 在在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹上根結(jié)點的權(quán)值之和；上根結(jié)點的權(quán)值之和；3) 從從F中刪除這兩棵二叉樹，同時將新二叉樹加入到中刪除這兩棵二叉樹，同時將新二叉樹加入到F中中;4) 重復(fù)重復(fù)2)-3)步直到步直到F中只含一棵二叉樹為止，這棵二叉樹中只含一棵二叉樹為止，這棵二叉樹就是就是Huffman 樹。樹。第第7章章 圖圖 第第7章章 圖圖 7.4 圖的應(yīng)用圖的應(yīng)用 -最小生成樹最小生成樹 (無向

6、圖無向圖) -拓撲排序拓撲排序 (有向圖，簡介有向圖，簡介) -最短路徑最短路徑 (無向圖無向圖)第第7章章 圖圖 7.1 圖的定義和術(shù)語圖的定義和術(shù)語 圖圖(Graph)G由兩個集合由兩個集合V(Vertex)和和E(Edge)組成組成, 記為記為G=(V,E),其中其中V是頂點的有限集合是頂點的有限集合, 記為記為V(G), E是連接是連接V中兩個中兩個不同頂點不同頂點(頂點對頂點對)的邊的有限集合的邊的有限集合, 記為記為E(G)。 在圖在圖G中中,如果代表邊的頂點對是無序的如果代表邊的頂點對是無序的,則稱則稱G為為無向圖無向圖,無無向圖中代表邊的無序頂點對，通常用圓括號括起來向圖中代表

7、邊的無序頂點對，通常用圓括號括起來,用以表示一用以表示一條無向邊。條無向邊。 如：如：(vi,vj) 如果表示邊的頂點對是有序的如果表示邊的頂點對是有序的,則稱則稱G為為有向圖有向圖,在有向圖中在有向圖中代表邊的頂點對，通常用尖括號括起來代表邊的頂點對，通常用尖括號括起來 (稱為稱為弧弧)。如：。如： 1. 圖的定義圖的定義 ViVjViVj弧頭弧頭弧尾弧尾第第7章章 圖圖 有向圖、無向圖示例有向圖、無向圖示例 第第7章章 圖圖 本章不予討論的圖本章不予討論的圖第第7章章 圖圖 Internet 網(wǎng)分布圖網(wǎng)分布圖腦網(wǎng)絡(luò)圖腦網(wǎng)絡(luò)圖蛋白質(zhì)相互作用圖蛋白質(zhì)相互作用圖第第7章章 圖圖 2. 基本術(shù)語基

8、本術(shù)語 l完全圖完全圖(邊達到最大邊達到最大)、稀疏圖與稠密圖、稀疏圖與稠密圖n:圖中頂點的個數(shù)圖中頂點的個數(shù); e:圖中邊或弧的數(shù)目。圖中邊或弧的數(shù)目。無向圖其邊數(shù)無向圖其邊數(shù)e的取值范圍是的取值范圍是0n(n-1)/2。 無向完全圖無向完全圖：有：有n(n-1)/2條邊的無向圖。條邊的無向圖。有向圖其邊數(shù)有向圖其邊數(shù)e的取值范圍是的取值范圍是0n(n-1)。 有向完全圖有向完全圖：有：有n(n-1)條邊的有向圖。條邊的有向圖。 稀疏圖稀疏圖：對于有很少條邊或弧的圖：對于有很少條邊或弧的圖(enlogn)， 反之稱為反之稱為稠密圖稠密圖。 第第7章章 圖圖 l子圖子圖有兩個圖有兩個圖G=(V

9、, E)和圖和圖G=(V, E), 若若V V且且E E, 則稱圖則稱圖G為為G的子圖。的子圖。l鄰接點鄰接點 :邊的兩個頂點對邊的兩個頂點對 (vi,vj) 和和 n無向圖：無向圖：vi和和vj互為鄰接點互為鄰接點；n有向圖：有向圖：vi和和vj互為鄰接點互為鄰接點，弧頂，弧頂(vj)是是弧尾弧尾(vi)的的出邊鄰接點出邊鄰接點，弧尾，弧尾(vi)是弧頂是弧頂(vj)的是的的是的入邊鄰接點入邊鄰接點； 1 3 0 2 4 (a) (b) 1 3 0 2 4 1 3 0 2 4 (c) 第第7章章 圖圖 l頂點的度、入度和出度頂點的度、入度和出度n在在無向圖無向圖中中,頂點所具有的邊的數(shù)目稱為

10、該頂點所具有的邊的數(shù)目稱為該頂點的度頂點的度。n在在有向圖有向圖中中,以頂點以頂點v為頭的弧的數(shù)目為頭的弧的數(shù)目,稱為該頂點的稱為該頂點的入度入度。以頂點以頂點v為尾的弧的數(shù)目為尾的弧的數(shù)目,稱為該頂點的稱為該頂點的出度出度。一個頂點的。一個頂點的入度與出度的和為該頂點的入度與出度的和為該頂點的度度。n一般地，若圖一般地，若圖G中有中有n個頂點，個頂點，e條邊或弧，則圖中頂點的條邊或弧，則圖中頂點的度與邊的關(guān)系如下：度與邊的關(guān)系如下： 2)(1niivTDeWhy?一個邊被兩個頂點分，一個邊被兩個頂點分，對于度來說有兩次貢獻對于度來說有兩次貢獻第第7章章 圖圖 l 權(quán)與網(wǎng)權(quán)與網(wǎng) 在實際應(yīng)用中，

11、有時圖的邊或弧上往往與具有一定意義的在實際應(yīng)用中，有時圖的邊或弧上往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個頂點到另一個頂點的距離或耗費等信息。我們以表示從一個頂點到另一個頂點的距離或耗費等信息。我們將這種帶權(quán)的圖叫做將這種帶權(quán)的圖叫做賦權(quán)圖賦權(quán)圖或或網(wǎng)網(wǎng)。 帶權(quán)無向圖的例子帶權(quán)無向圖的例子第第7章章 圖圖 l路徑與回路路徑與回路 無向圖無向圖G=(V,E)中從頂點中從頂點v到到v的路徑是一個頂點序列的路徑是一個頂點序列(v=vi0,vi1,vi2,vin=v)其中其中(vij-1, vij)E, 1

12、jn。如果圖如果圖G是有向圖，是有向圖，則路徑也是有向的則路徑也是有向的，頂點序列應(yīng)滿足，頂點序列應(yīng)滿足E， 1jn。n路徑的長度路徑的長度: 路徑上經(jīng)過的弧或邊的數(shù)目；路徑上經(jīng)過的弧或邊的數(shù)目；n回路回路或或環(huán)環(huán): 第一個頂點和最后一個頂點相同時；第一個頂點和最后一個頂點相同時；n簡單路徑簡單路徑:表示路徑的頂點序列中的頂點各不相同；表示路徑的頂點序列中的頂點各不相同；n簡單回路簡單回路:除了第一個和最后一個頂點外，其余各頂點均不除了第一個和最后一個頂點外，其余各頂點均不重復(fù)出現(xiàn)的回路。重復(fù)出現(xiàn)的回路。 n例例4：在圖：在圖a中，中，V0,V1,V2,V3 是簡單路徑；是簡單路徑； V0,V

13、1,V2,V4,V1不是簡不是簡單路徑；在圖單路徑；在圖b中，中， V0,V2,V3,V0是簡單回路，也是一個環(huán)。是簡單回路，也是一個環(huán)。V0V3V2V1V0V4V3V1V2(a)(b)第第7章章 圖圖 l連通圖連通圖: 無向圖中任意兩個頂點都連通無向圖中任意兩個頂點都連通連通分量連通分量:無向圖中的極大連通子圖。無向圖中的極大連通子圖。l強連通圖強連通圖: 有向圖每對頂點之間都存在路徑有向圖每對頂點之間都存在路徑強連通分量強連通分量: 有向圖的極大強連通子圖。有向圖的極大強連通子圖。 V0V4V3V1V2連通圖V0V4V3V1非連通圖V2V0V4V3V1強連通圖V0V4V3V1非強連通圖第第

14、7章章 圖圖 l生成樹生成樹: 連通圖的生成樹是一個連通圖的生成樹是一個，它含有圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。條邊。 en-1 一定有回路一定有回路 e=n-1 不一定都是圖的生成樹不一定都是圖的生成樹 第第7章章 圖圖 例例2：有：有n個頂點的有向強連通圖最多需要多少條邊？最少需要個頂點的有向強連通圖最多需要多少條邊？最少需要多少條邊？多少條邊？ 答案：有答案：有n個頂點的有向強連通圖最多有個頂點的有向強連通圖最多有n(n-1)條邊條邊( (構(gòu)成構(gòu)成一個有向完全圖的情況一個有向完全圖的情況) )；最少有；最少有n條邊條邊( (n個

15、頂點依次首尾相接個頂點依次首尾相接構(gòu)成一個環(huán)的情況構(gòu)成一個環(huán)的情況) )。 例例1：G是是非連通無向圖非連通無向圖，共，共28條邊，至少有多少個頂點？（條邊，至少有多少個頂點？（注注意審題意審題）答案：答案：9個頂點個頂點第第7章章 圖圖 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)1. 鄰接矩陣表示法（數(shù)組表示法）鄰接矩陣表示法（數(shù)組表示法） l圖圖G是一個具有是一個具有n個頂點的無權(quán)圖，個頂點的無權(quán)圖，G的鄰接矩陣是具有如下的鄰接矩陣是具有如下性質(zhì)的性質(zhì)的nn矩陣矩陣A： 1, ,), , 0, ijijv vv vVA i j若(或其它l若圖若圖G是一個有是一個有n個頂點的網(wǎng)，則它的鄰接矩陣是具有如

16、下性個頂點的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的質(zhì)的nn矩陣矩陣A：, ,), , , ijijijwv vv vVA i j若(或其它第第7章章 圖圖 第第7章章 圖圖 第第7章章 圖圖 鄰接矩陣表示法類型描述鄰接矩陣表示法類型描述 :define MAX_VERTEX_NUM 20 define INFINITY INT_MAX typedef enumDG, DN, UDG, UDN GraphKind; typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX

17、_NUM; typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum, arcnum; GraphKind kind; MGraph;第第7章章 圖圖 n圖的鄰接矩陣圖的鄰接矩陣。的鄰接矩陣一定是一個的鄰接矩陣一定是一個。存儲可采用。存儲可采用。n弱鄰接矩陣是一個弱鄰接矩陣是一個, ,可以采用可以采用表的方法存儲鄰接矩陣。表的方法存儲鄰接矩陣。對于無向圖對于無向圖, ,鄰接矩陣的第鄰接矩陣的第i i行行( (或第或第i i列列) )非零元素非零元素( (或或非非元素元素) )的個數(shù)正好是第的個數(shù)正好是第i

18、i個頂點個頂點v vi i的度。對于有向圖的度。對于有向圖, ,鄰接矩陣的鄰接矩陣的第第i i行行( (或第或第i i列列) )非零元素非零元素( (或非或非元素元素) )的個數(shù)正好是第的個數(shù)正好是第i i個頂點個頂點v vi i的的出度出度( (或入度或入度) )。用鄰接矩陣方法存儲圖用鄰接矩陣方法存儲圖, ,容易確定圖中任意兩個頂點之間是容易確定圖中任意兩個頂點之間是否有邊相連。但是否有邊相連。但是, ,要確定圖中有多少條邊要確定圖中有多少條邊, ,則必須按行、按列對每則必須按行、按列對每個元素進行檢測個元素進行檢測, ,所花費的時間代價很大。所花費的時間代價很大。第第7章章 圖圖 2.2

19、.鄰接表存儲方法：圖的鏈式存儲結(jié)構(gòu)鄰接表存儲方法：圖的鏈式存儲結(jié)構(gòu) 在鄰接表中在鄰接表中, ,對圖中每個頂點建立一個單鏈表對圖中每個頂點建立一個單鏈表, ,第第i i個單鏈個單鏈表中的結(jié)點表示依附于頂點表中的結(jié)點表示依附于頂點v vi i的邊的邊( (對有向圖是以頂點對有向圖是以頂點v vi i為尾為尾的弧的弧) )。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點和表頭結(jié)點。每個單鏈表上附設(shè)一個表頭結(jié)點。表結(jié)點和表頭結(jié)點的結(jié)構(gòu)如下：的結(jié)構(gòu)如下：adjvexnextarcinfodatafirstarc表結(jié)點表結(jié)點表頭結(jié)點表頭結(jié)點ndata存儲頂點存儲頂點vi的名稱或其他信息的名稱或其他信息; first

20、arc指向鏈表中第一指向鏈表中第一個結(jié)點。個結(jié)點。n adjvex指示與頂點指示與頂點vi鄰接的點在圖中的位置鄰接的點在圖中的位置;nextarc指示下指示下一條邊或弧的結(jié)點一條邊或弧的結(jié)點; info存儲與邊或弧相關(guān)的信息存儲與邊或弧相關(guān)的信息,如權(quán)值等。如權(quán)值等。第第7章章 圖圖 第第7章章 圖圖 鄰接表存儲結(jié)構(gòu)的類型定義：鄰接表存儲結(jié)構(gòu)的類型定義：typedef struct ArcNode/表結(jié)點結(jié)構(gòu)類型表結(jié)點結(jié)構(gòu)類型int adjvex; /該弧該弧(邊邊)的終點位置的終點位置 struct ArcNode *nextarc; /指向下一條弧的指針指向下一條弧的指針 InfoType

21、 info; /該弧的相關(guān)信息，如權(quán)重該弧的相關(guān)信息，如權(quán)重 ArcNode;typedef struct Vnode /頭結(jié)點的類型頭結(jié)點的類型Vertex data; /頂點信息頂點信息 ArcNode *firstarc; /指向第一條弧指向第一條弧 VNode, AdjListMAX_VERTEX_NUM;typedef struct /鄰接表鄰接表 AdjList vertices; int vexnum, arcnum; /圖中頂點數(shù)圖中頂點數(shù)n和邊數(shù)和邊數(shù)e int kind; /圖的類型圖的類型 ALGraph; 第第7章章 圖圖 鄰接表的特點如下鄰接表的特點如下：n鄰接表鄰接

22、表。這是因為在每個頂點對應(yīng)的單鏈表中。這是因為在每個頂點對應(yīng)的單鏈表中, ,各各邊結(jié)點的鏈接次序可以是任意的邊結(jié)點的鏈接次序可以是任意的, ,取決于建立鄰接表的算法以取決于建立鄰接表的算法以及邊的輸入次序。及邊的輸入次序。n對于有對于有n個頂點和個頂點和e條邊的無向圖條邊的無向圖, ,其鄰接表有其鄰接表有n個頭結(jié)點和個頭結(jié)點和2e個個表結(jié)點。顯然表結(jié)點。顯然, ,在總的邊數(shù)小于在總的邊數(shù)小于n(n-1)/2的情況下的情況下, ,鄰接表比鄰鄰接表比鄰接矩陣要接矩陣要。n對于對于, ,鄰接表的頂點鄰接表的頂點vi對應(yīng)的第對應(yīng)的第i i個鏈表的表結(jié)點數(shù)目正個鏈表的表結(jié)點數(shù)目正好是頂點好是頂點vi的的

23、。n對于對于, ,鄰接表的頂點鄰接表的頂點vi對應(yīng)的第對應(yīng)的第i i個鏈表的表結(jié)點數(shù)目僅個鏈表的表結(jié)點數(shù)目僅僅是僅是vi的的。其入度為鄰接表。其入度為鄰接表中所有中所有adjvex域值為域值為i的表結(jié)點數(shù)目。（的表結(jié)點數(shù)目。（）第第7章章 圖圖 圖圖G1的逆鄰接表表示法的逆鄰接表表示法 3. 十字鏈表十字鏈表 (課后自學(xué)課后自學(xué)) 4. 鄰接多重表鄰接多重表 (課后自學(xué)課后自學(xué))第第7章章 圖圖 7.3 圖圖 的的 遍遍 歷歷 n圖遍歷的概念圖遍歷的概念: :從給定圖中任意指定的頂點從給定圖中任意指定的頂點( (稱為初始點稱為初始點) )出發(fā)出發(fā), ,按照某種按照某種搜索方法沿著圖的邊訪問圖中

24、的所有頂點搜索方法沿著圖的邊訪問圖中的所有頂點, ,使每個頂點僅被訪問一次使每個頂點僅被訪問一次, ,這這個過程稱為個過程稱為圖的遍歷圖的遍歷。n對于圖遍歷，需注意以下兩點：對于圖遍歷，需注意以下兩點：n如果給定圖是連通的無向圖或者是強連通的有向圖如果給定圖是連通的無向圖或者是強連通的有向圖, ,則遍歷過程則遍歷過程一次就能完成一次就能完成, ,并可按訪問的先后順序得到由該圖所有頂點組成并可按訪問的先后順序得到由該圖所有頂點組成的一個序列。的一個序列。n為避免同一頂點被訪問多次為避免同一頂點被訪問多次, ,設(shè)一個輔助數(shù)組設(shè)一個輔助數(shù)組visited0.n-1,visited0.n-1,它的初始

25、值置為它的初始值置為0,0,一旦訪問了頂點一旦訪問了頂點vi,vi,便置便置visitedivisitedi為為1 1或者為或者為被訪問時的次序號被訪問時的次序號n根據(jù)搜索方法的不同根據(jù)搜索方法的不同, ,圖的遍歷方法有兩種：圖的遍歷方法有兩種：n深度優(yōu)先搜索法深度優(yōu)先搜索法DFS(Depth-First Search)n廣度優(yōu)先搜索法廣度優(yōu)先搜索法BFS (Breadth-First Search) 第第7章章 圖圖 深度優(yōu)先搜索遍歷深度優(yōu)先搜索遍歷( (過程過程) )：n訪問指定的某頂點訪問指定的某頂點V V，將，將V V作為當前頂點作為當前頂點n訪問當前頂點的下一未被訪問過的鄰接點訪問當

26、前頂點的下一未被訪問過的鄰接點n重復(fù)重復(fù)1 1和和2 2，直到當前頂點的所有鄰接點都被訪問點。，直到當前頂點的所有鄰接點都被訪問點。n沿搜索路徑回退，退到尚有鄰接點未被訪問過的某沿搜索路徑回退，退到尚有鄰接點未被訪問過的某結(jié)點，將該結(jié)點作為當前結(jié)點，重復(fù)以上步驟，直結(jié)點，將該結(jié)點作為當前結(jié)點，重復(fù)以上步驟，直到所有頂點被訪問過的為止。到所有頂點被訪問過的為止。顯然顯然, ,這個遍歷過程是個遞歸過程。這個遍歷過程是個遞歸過程。第第7章章 圖圖 圖的深度優(yōu)先搜索過程圖示圖的深度優(yōu)先搜索過程圖示 V0V0 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2 V1V1例：求圖例：求圖G G以以

27、V0V0起點的的起點的的深深度優(yōu)先序列：度優(yōu)先序列：l V0,V1,V3,V7,V4,V2,V5,V6這是其中一種遍歷這是其中一種遍歷方案所經(jīng)過的路徑方案所經(jīng)過的路徑 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4深到底深到底V0V1V3V7V4（V7V3V1均已訪問）均已訪問）深到底深到底V2V5V6回退回退深到底深到底回退回退訪問訪問u 由于沒有規(guī)定訪問鄰接點的順序，深度優(yōu)先由于沒有規(guī)定訪問鄰接點的順序，深度優(yōu)先遍歷序列不唯一遍歷序列不唯一u 如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、如果將圖頂點的鄰接點看作二叉樹結(jié)點的左、右孩子，深度優(yōu)先遍歷與先序遍歷很類似

28、右孩子，深度優(yōu)先遍歷與先序遍歷很類似第第7章章 圖圖 int visitedMAX; void DFSTraverse(Graph G) for (v=0; vG.vexnum; +v) visitedv = FALSE ; for( v=0; v=0; w=) if(!visitedw) DFS(G,w); 返回返回v的臨鄰接點，返回的臨鄰接點，返回v的相對于的相對于w的鄰接點的鄰接點第第7章章 圖圖 算法分析算法分析:n假設(shè)圖中有假設(shè)圖中有 n 個頂點，個頂點，e 條邊。遍歷過程實質(zhì)上是對每個頂條邊。遍歷過程實質(zhì)上是對每個頂點查找鄰接點的過程。點查找鄰接點的過程。n如果用鄰接表表示圖，沿如果用鄰接表表示圖，沿 firsarc鏈可以找到某個頂點鏈可以找到某個頂點 v 的所的所有鄰接頂點有鄰接頂點 w。由于總共有。由于總共有 2e 個邊結(jié)點，所以掃描邊的時間個邊結(jié)點，所以掃描邊的時間為為O(e)。所以遍歷圖的時間復(fù)雜性為。所以遍歷圖的時間復(fù)雜性為O(n+e)。n如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為需時間為O(n)，則遍歷圖中所有的