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

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

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

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

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

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

6、圖無(wú)向圖) -拓?fù)渑判蛲負(fù)渑判?(有向圖，簡(jiǎn)介有向圖，簡(jiǎn)介) -最短路徑最短路徑 (無(wú)向圖無(wú)向圖)第第7章章 圖圖 7.1 圖的定義和術(shù)語(yǔ)圖的定義和術(shù)語(yǔ) 圖圖(Graph)G由兩個(gè)集合由兩個(gè)集合V(Vertex)和和E(Edge)組成組成, 記為記為G=(V,E),其中其中V是頂點(diǎn)的有限集合是頂點(diǎn)的有限集合, 記為記為V(G), E是連接是連接V中兩個(gè)中兩個(gè)不同頂點(diǎn)不同頂點(diǎn)(頂點(diǎn)對(duì)頂點(diǎn)對(duì))的邊的有限集合的邊的有限集合, 記為記為E(G)。 在圖在圖G中中,如果代表邊的頂點(diǎn)對(duì)是無(wú)序的如果代表邊的頂點(diǎn)對(duì)是無(wú)序的,則稱則稱G為為無(wú)向圖無(wú)向圖,無(wú)無(wú)向圖中代表邊的無(wú)序頂點(diǎn)對(duì)，通常用圓括號(hào)括起來(lái)向圖中代表

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

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

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

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

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

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

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

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

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

16、下性個(gè)頂點(diǎn)的網(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圖的鄰接矩陣圖的鄰接矩陣。的鄰接矩陣一定是一個(gè)的鄰接矩陣一定是一個(gè)。存儲(chǔ)可采用。存儲(chǔ)可采用。n弱鄰接矩陣是一個(gè)弱鄰接矩陣是一個(gè), ,可以采用可以采用表的方法存儲(chǔ)鄰接矩陣。表的方法存儲(chǔ)鄰接矩陣。對(duì)于無(wú)向圖對(duì)于無(wú)向圖, ,鄰接矩陣的第鄰接矩陣的第i i行行( (或第或第i i列列) )非零元素非零元素( (或或非非元素元素) )的個(gè)數(shù)正好是第的個(gè)數(shù)正好是第i

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

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

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

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

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

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

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

25、值置為它的初始值置為0,0,一旦訪問了頂點(diǎn)一旦訪問了頂點(diǎn)vi,vi,便置便置visitedivisitedi為為1 1或者為或者為被訪問時(shí)的次序號(hào)被訪問時(shí)的次序號(hào)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)先搜索遍歷( (過(guò)程過(guò)程) )：n訪問指定的某頂點(diǎn)訪問指定的某頂點(diǎn)V V，將，將V V作為當(dāng)前頂點(diǎn)作為當(dāng)前頂點(diǎn)n訪問當(dāng)前頂點(diǎn)的下一未被訪問過(guò)的鄰接點(diǎn)訪問當(dāng)

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

27、V0V0起點(diǎn)的的起點(diǎn)的的深深度優(yōu)先序列：度優(yōu)先序列：l V0,V1,V3,V7,V4,V2,V5,V6這是其中一種遍歷這是其中一種遍歷方案所經(jīng)過(guò)的路徑方案所經(jīng)過(guò)的路徑 V0V0 V1V1 V3V3 V2V2 V7V7 V6V6 V5V5 V4V4深到底深到底V0V1V3V7V4（V7V3V1均已訪問）均已訪問）深到底深到底V2V5V6回退回退深到底深到底回退回退訪問訪問u 由于沒有規(guī)定訪問鄰接點(diǎn)的順序，深度優(yōu)先由于沒有規(guī)定訪問鄰接點(diǎn)的順序，深度優(yōu)先遍歷序列不唯一遍歷序列不唯一u 如果將圖頂點(diǎn)的鄰接點(diǎn)看作二叉樹結(jié)點(diǎn)的左、如果將圖頂點(diǎn)的鄰接點(diǎn)看作二叉樹結(jié)點(diǎn)的左、右孩子，深度優(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的臨鄰接點(diǎn)，返回的臨鄰接點(diǎn)，返回v的相對(duì)于的相對(duì)于w的鄰接點(diǎn)的鄰接點(diǎn)第第7章章 圖圖 算法分析算法分析:n假設(shè)圖中有假設(shè)圖中有 n 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，e 條邊。遍歷過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂條邊。遍歷過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找鄰接點(diǎn)的過(guò)程。點(diǎn)查找鄰接點(diǎn)的過(guò)程。n如果用鄰接表表示圖，沿如果用鄰接表表示圖，沿 firsarc鏈可以找到某個(gè)頂點(diǎn)鏈可以找到某個(gè)頂點(diǎn) v 的所的所有鄰接頂點(diǎn)有鄰接頂點(diǎn) w。由于總共有。由于總共有 2e 個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為為O(e)。所以遍歷圖的時(shí)間復(fù)雜性為。所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。n如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的所有的邊，所需時(shí)間為需時(shí)間為O(n)，則遍歷圖中所有的