[理學(xué)]數(shù)據(jù)結(jié)構(gòu)第七章 圖ppt課件

1、第7章 圖本章中介紹以下主要內(nèi)容：l圖的定義l圖的存儲構(gòu)造l圖的遍歷操作l圖的幾個典型問題第第7 7章章 圖圖 圖圖Graph是一種比線性表和樹更為復(fù)雜的數(shù)是一種比線性表和樹更為復(fù)雜的數(shù)據(jù)構(gòu)造。據(jù)構(gòu)造。 線性構(gòu)造線性構(gòu)造：是研究數(shù)據(jù)元素之間的一對一關(guān)系。：是研究數(shù)據(jù)元素之間的一對一關(guān)系。在這種構(gòu)造中，除第一個和最后一個元素外，任何一在這種構(gòu)造中，除第一個和最后一個元素外，任何一個元素都有唯一的一個直接前驅(qū)和直接后繼。個元素都有唯一的一個直接前驅(qū)和直接后繼。 樹構(gòu)造樹構(gòu)造：是研究數(shù)據(jù)元素之間的一對多的關(guān)系。：是研究數(shù)據(jù)元素之間的一對多的關(guān)系。在這種構(gòu)造中，每個元素對下在這種構(gòu)造中，每個元素對下層

2、層可以有可以有0個或多個或多個元素相聯(lián)絡(luò)，對上個元素相聯(lián)絡(luò)，對上層層只有唯一的一個元素相關(guān)，只有唯一的一個元素相關(guān)，數(shù)據(jù)元素之間有明顯的層次關(guān)系。數(shù)據(jù)元素之間有明顯的層次關(guān)系。 圖構(gòu)造圖構(gòu)造：是研究數(shù)據(jù)元素之間的多對多：是研究數(shù)據(jù)元素之間的多對多的關(guān)系。在這種構(gòu)造中，任意兩個元素之間可的關(guān)系。在這種構(gòu)造中，任意兩個元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。圖中任意元素之間都可能相關(guān)。 圖的應(yīng)用極為廣泛，已滲入到諸如語言圖的應(yīng)用極為廣泛，已滲入到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)學(xué)、邏輯學(xué)、物理、化學(xué)、

3、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。以及數(shù)學(xué)的其它分支。第第7章章 圖圖7.1 圖的根本概念圖的根本概念7.1.1 圖的定義和術(shù)語圖的定義和術(shù)語 一個圖一個圖G定義為一個偶對定義為一個偶對V,E ，記為，記為G=V,E 。其中：其中： V是是頂點(diǎn)頂點(diǎn)Vertex的非空有限集合，記為的非空有限集合，記為VG；E是無序集是無序集V&V的一個子集，記為的一個子集，記為EG ，其元素是圖的，其元素是圖的弧弧Arc。 將頂點(diǎn)集合為空的圖稱為空圖。其形式化定義為：將頂點(diǎn)集合為空的圖稱為空圖。其形式化定義為：G=V ，EV=v|v data objectE=| v,w Vpv,wPv,w表示從頂點(diǎn)表

4、示從頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)w有一條直接通路。有一條直接通路。 弧弧Arc ：表示兩個頂點(diǎn)表示兩個頂點(diǎn)v和和w之間存在一個之間存在一個關(guān)系，用頂點(diǎn)偶對關(guān)系，用頂點(diǎn)偶對表示。通常根據(jù)圖的頂點(diǎn)偶表示。通常根據(jù)圖的頂點(diǎn)偶對將圖分為有向圖和無向圖。對將圖分為有向圖和無向圖。 有向圖有向圖Digraph： 假設(shè)圖假設(shè)圖G的關(guān)系集合的關(guān)系集合EG中，頂點(diǎn)偶對中，頂點(diǎn)偶對的的v和和w之間是之間是有序有序的的，稱，稱圖圖G是有向圖。是有向圖。 在有向圖中，假設(shè)在有向圖中，假設(shè) EG ，表示從頂點(diǎn)，表示從頂點(diǎn)v到頂點(diǎn)到頂點(diǎn)w有一條有一條弧弧。 其中：其中：v稱為稱為弧尾弧尾tail或或始點(diǎn)始點(diǎn)initial node

5、，w稱為稱為弧頭弧頭head或或終點(diǎn)終點(diǎn)terminal node 。定義和術(shù)語定義和術(shù)語2 2 無向圖無向圖Undigraph： 假設(shè)圖假設(shè)圖G的關(guān)系集合的關(guān)系集合EG中，頂點(diǎn)偶對中，頂點(diǎn)偶對的的v和和w之間是之間是無序無序的，的，稱圖稱圖G是無向圖。是無向圖。 在無向圖中，假設(shè)在無向圖中，假設(shè) EG ，有，有 EG ，即，即EG是對稱，那么用無序是對稱，那么用無序?qū),w 表示表示v和和w之間的一條之間的一條邊邊Edge，因，因此此v,w 和和w,v代表的是同一條邊。代表的是同一條邊。定義和術(shù)語定義和術(shù)語3 3 例例1：設(shè)有有向圖：設(shè)有有向圖G1和無向圖和無向圖G2，形式化定義，形式化定

6、義：G1=V1 ，E1V1=a,b,c,d,eE1=, , ,G2=V2 ，E2V2=a,b,c,dE2=a,b, a,c, a,d, b,d, b,c, c,dabcd(b) 無向圖無向圖G2 (a) 有向圖有向圖G1 acbde 完全無向圖完全無向圖：對于無向圖，假設(shè)圖中頂點(diǎn)數(shù)為對于無向圖，假設(shè)圖中頂點(diǎn)數(shù)為n ，用用e表示邊的數(shù)目，那么表示邊的數(shù)目，那么e 0，nn-1/2 。具有。具有nn-1/2條邊的無向圖稱為完全無向圖。條邊的無向圖稱為完全無向圖。 完全無向圖另外的定義是：完全無向圖另外的定義是： 對于無向圖對于無向圖G=V，E，假設(shè)，假設(shè) vi，vj V ，當(dāng)，當(dāng)vivj時，有時，

7、有vi ,vj E，即，即圖中任意兩個不同的頂點(diǎn)圖中任意兩個不同的頂點(diǎn)間都有一條無向邊間都有一條無向邊，這樣的無向圖稱為，這樣的無向圖稱為完全無向圖完全無向圖。定義和術(shù)語定義和術(shù)語4 4 完全有向圖完全有向圖：對于有向圖，假設(shè)圖中頂點(diǎn)數(shù)為：對于有向圖，假設(shè)圖中頂點(diǎn)數(shù)為n ，用用e表示弧的數(shù)目，那么表示弧的數(shù)目，那么e 0，nn-1 。具有。具有nn-1條邊的有向圖稱為完全有向圖。條邊的有向圖稱為完全有向圖。 完全有向圖另外的定義是：完全有向圖另外的定義是： 對于有向圖對于有向圖G=V，E，假設(shè)，假設(shè) vi，vj V ，當(dāng)，當(dāng)vi vj時，有時，有 E E ，即，即圖中任意圖中任意兩個不同的頂點(diǎn)

8、間都有一條弧兩個不同的頂點(diǎn)間都有一條弧，這樣的有向圖稱為，這樣的有向圖稱為完完全有向圖全有向圖。定義和術(shù)語定義和術(shù)語5 5 有很少邊或弧的圖有很少邊或弧的圖enn的圖稱為的圖稱為稀疏圖稀疏圖，反之稱為反之稱為稠密圖稠密圖。 權(quán)權(quán)Weight：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的間隔表示從一個頂點(diǎn)到另一個頂點(diǎn)的間隔 或消耗?；蛳?。 子圖和生成子圖子圖和生成子圖：設(shè)有圖：設(shè)有圖G=V，E和和G=V，E，假設(shè)，假設(shè)V V且且E E ，那么稱圖，那么稱圖G是是G的的子圖子圖；假；假設(shè)設(shè)V=V且且E E，那么稱圖，那么稱圖G是是G的一個的一個生成子圖生

9、成子圖。定義和術(shù)語定義和術(shù)語6 6 頂點(diǎn)的鄰接頂點(diǎn)的鄰接Adjacent：對于無向圖對于無向圖G=V，E，假設(shè)邊假設(shè)邊v,w E，那么稱頂點(diǎn)，那么稱頂點(diǎn)v和和w 互為互為鄰接點(diǎn)鄰接點(diǎn)，即，即v和和w相相鄰接。邊鄰接。邊v,w依附依附incident與頂點(diǎn)與頂點(diǎn)v和和w 。 對于有向圖對于有向圖G=V ，E，假設(shè)有向弧，假設(shè)有向弧 E，那么，那么稱頂點(diǎn)稱頂點(diǎn)v “鄰接到鄰接到頂點(diǎn)頂點(diǎn)w，頂點(diǎn)，頂點(diǎn)w “鄰接自鄰接自頂點(diǎn)頂點(diǎn)v ，弧，弧 與頂點(diǎn)與頂點(diǎn)v和和w “相關(guān)聯(lián)相關(guān)聯(lián) 。 頂點(diǎn)的度、入度、出度頂點(diǎn)的度、入度、出度：對于無向圖對于無向圖G=V，E， vi V，圖，圖G中中依附于于vi的邊的數(shù)目

10、稱為頂點(diǎn)的邊的數(shù)目稱為頂點(diǎn)vi的的度度degree，記為記為TDvi。定義和術(shù)語定義和術(shù)語7 7 顯然，在無向圖中，所有頂點(diǎn)度的和是圖中邊的顯然，在無向圖中，所有頂點(diǎn)度的和是圖中邊的2倍。倍。 即即 TDvi=2e i=1,2, ,n，e為圖的邊為圖的邊數(shù)數(shù)。 對有向圖對有向圖G=V，E，假設(shè)，假設(shè) vi V ，圖，圖G中中以以vi作為起點(diǎn)作為起點(diǎn)的有向邊的有向邊弧弧的數(shù)目稱為頂點(diǎn)的數(shù)目稱為頂點(diǎn)vi的的出度出度Outdegree，記為，記為ODvi ；以以vi作為終點(diǎn)作為終點(diǎn)的有的有向邊向邊弧弧的數(shù)目稱為頂點(diǎn)的數(shù)目稱為頂點(diǎn)vi的的入度入度Indegree，記，記為為IDvi 。頂點(diǎn)。頂點(diǎn)vi的

11、的出度出度與與入度入度之和稱為之和稱為vi的的度度，記，記為為TDvi 。即。即 TDvi=ODvi+IDvi 定義和術(shù)語定義和術(shù)語8 8 途徑途徑Path、途徑長度、回路、途徑長度、回路Cycle ：對：對無向圖無向圖G=V，E，假設(shè)從頂點(diǎn)，假設(shè)從頂點(diǎn)vi經(jīng)過假設(shè)干條邊經(jīng)過假設(shè)干條邊能到達(dá)能到達(dá)vj，稱頂點(diǎn)，稱頂點(diǎn)vi和和vj是是連通連通的，又稱頂點(diǎn)的，又稱頂點(diǎn)vi到到vj有有途徑途徑。 對有向圖對有向圖G=V，E，從頂點(diǎn)，從頂點(diǎn)vi到到vj有有有向途有向途徑徑，指的是從頂點(diǎn)，指的是從頂點(diǎn)vi經(jīng)過假設(shè)干條有向邊經(jīng)過假設(shè)干條有向邊弧弧能到能到達(dá)達(dá)vj。 或或途徑途徑是圖是圖G中連接兩頂點(diǎn)間所經(jīng)

12、過的頂點(diǎn)序列。中連接兩頂點(diǎn)間所經(jīng)過的頂點(diǎn)序列。Path=vi0vi1vim ，vij V且且vij-1, vij E j=1,2, ,m定義和術(shù)語定義和術(shù)語9 9 途徑上邊或有向邊途徑上邊或有向邊弧弧的數(shù)目稱為該途徑的的數(shù)目稱為該途徑的長長度度。 在一條途徑中，假設(shè)在一條途徑中，假設(shè)沒有重復(fù)一樣沒有重復(fù)一樣的頂點(diǎn)，該途的頂點(diǎn)，該途徑稱為徑稱為簡單途徑簡單途徑；第一個頂點(diǎn)和最后一個頂點(diǎn)一樣的；第一個頂點(diǎn)和最后一個頂點(diǎn)一樣的途徑稱為途徑稱為回路回路環(huán)環(huán)；在一個回路中，假設(shè)除第一個；在一個回路中，假設(shè)除第一個與最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為與最后一個頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為

13、簡單回路簡單回路簡單環(huán)簡單環(huán)。定義和術(shù)語定義和術(shù)語1010 連通圖、圖的連通分量連通圖、圖的連通分量：對無向圖：對無向圖G=V，E，假設(shè)假設(shè) vi ，vj V，vi和和vj都是連通的，那么稱圖都是連通的，那么稱圖G是是連連通圖通圖，否那么稱為，否那么稱為非連通圖非連通圖。假設(shè)。假設(shè)G是非連通圖，那么是非連通圖，那么極大的連通子圖極大的連通子圖稱為稱為G的的連通分量連通分量。 對有向圖對有向圖G=V，E，假設(shè)，假設(shè) vi ，vj V，都有，都有以以vi為起點(diǎn)為起點(diǎn)， vj 為終點(diǎn)為終點(diǎn)以及以以及以vj為起點(diǎn)，為起點(diǎn)，vi為終點(diǎn)的有為終點(diǎn)的有向途徑，稱圖向途徑，稱圖G是是強(qiáng)連通圖強(qiáng)連通圖，否那么稱

14、為，否那么稱為非強(qiáng)連通圖非強(qiáng)連通圖。假設(shè)假設(shè)G是非強(qiáng)連通圖，那么是非強(qiáng)連通圖，那么極大的強(qiáng)連通子圖極大的強(qiáng)連通子圖稱為稱為G的的強(qiáng)連通分量強(qiáng)連通分量。 “極大極大的含義：指的是對子圖再增加圖的含義：指的是對子圖再增加圖G中的其中的其它頂點(diǎn)，子圖就不再連通。它頂點(diǎn)，子圖就不再連通。定義和術(shù)語定義和術(shù)語1111 生成樹、生成森林生成樹、生成森林：一個連通圖一個連通圖無向圖無向圖的的生成樹是一個極小連通子圖，它生成樹是一個極小連通子圖，它含有圖中全部含有圖中全部n個頂點(diǎn)個頂點(diǎn)和只有足以構(gòu)成一棵樹的和只有足以構(gòu)成一棵樹的n-1條邊條邊，稱為圖的，稱為圖的生成樹生成樹，如圖如圖7-2所示。所示。 關(guān)于無

15、向圖的生成樹的幾個結(jié)論：關(guān)于無向圖的生成樹的幾個結(jié)論： 一棵有一棵有n個頂點(diǎn)的生成樹有且僅有個頂點(diǎn)的生成樹有且僅有n-1條邊；條邊； 假如一個圖有假如一個圖有n個頂點(diǎn)和小于個頂點(diǎn)和小于n-1條邊，那么是非條邊，那么是非連通圖；連通圖；adbc圖圖7-2 圖圖G2的一棵生成樹的一棵生成樹 假如多于假如多于n-1條邊，那么一條邊，那么一定有環(huán)；定有環(huán)； 有有n-1條邊的圖不一定是生條邊的圖不一定是生成樹。成樹。 有向圖的有向圖的生成森林生成森林是這樣一個子圖，由假設(shè)干棵是這樣一個子圖，由假設(shè)干棵有有向樹向樹組成，含有圖中全部頂點(diǎn)。組成，含有圖中全部頂點(diǎn)。 有向樹有向樹是只有一個頂點(diǎn)的入度為是只有一

16、個頂點(diǎn)的入度為0 ，其余頂點(diǎn)的入，其余頂點(diǎn)的入度均為度均為1的有向圖，如圖的有向圖，如圖7-3所示。所示。 網(wǎng)網(wǎng)：每個邊每個邊或弧或弧都附加一個權(quán)值的圖，稱為都附加一個權(quán)值的圖，稱為帶權(quán)圖帶權(quán)圖。帶權(quán)的連通圖帶權(quán)的連通圖包括弱連通的有向圖包括弱連通的有向圖稱為稱為網(wǎng)網(wǎng)或網(wǎng)絡(luò)或網(wǎng)絡(luò)。網(wǎng)絡(luò)是工程上常用的一個概念，用來表示一個。網(wǎng)絡(luò)是工程上常用的一個概念，用來表示一個工程或某種流程，如圖工程或某種流程，如圖7-4所示。所示。圖圖7-3 有向圖及其生成森林有向圖及其生成森林abcdea 有向圖有向圖b 生成森林生成森林acbde354126abcde3圖圖7-4 帶權(quán)有向圖帶權(quán)有向圖7.1.2 圖的抽

17、象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義 圖是一種數(shù)據(jù)構(gòu)造，加上一組根本操作就構(gòu)成了圖圖是一種數(shù)據(jù)構(gòu)造，加上一組根本操作就構(gòu)成了圖的抽象數(shù)據(jù)類型。的抽象數(shù)據(jù)類型。 圖的抽象數(shù)據(jù)類型定義如下：圖的抽象數(shù)據(jù)類型定義如下：ADT Graph數(shù)據(jù)對象數(shù)據(jù)對象V：具有一樣特性的數(shù)據(jù)元素集合具有一樣特性的數(shù)據(jù)元素集合，稱為頂點(diǎn)集稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：R=VRVR=| v,w Vpv,w ，表表示示 從從v到到w的弧，的弧，Pv,w定定義了弧義了弧的信息的信息 根本操作根本操作P： Create_Graph ： 圖的創(chuàng)立操作圖的創(chuàng)立操作。 初始條件：無。初始條件：無。 操作結(jié)果：生成一個沒有頂點(diǎn)的空圖操

18、作結(jié)果：生成一個沒有頂點(diǎn)的空圖G。GetVexG, v ： 求圖中的頂點(diǎn)求圖中的頂點(diǎn)v的值。的值。初始條件：圖初始條件：圖G存在，存在，v是圖中的一個頂點(diǎn)。是圖中的一個頂點(diǎn)。操作結(jié)果：生成一個沒有頂點(diǎn)的空圖操作結(jié)果：生成一個沒有頂點(diǎn)的空圖G。 DFStraverG,V：從：從v出發(fā)對圖出發(fā)對圖G深度優(yōu)先遍歷深度優(yōu)先遍歷。 初始條件：圖初始條件：圖G存在。存在。 操作結(jié)果：對圖操作結(jié)果：對圖G深度優(yōu)先遍歷，每個頂點(diǎn)訪問且只訪問深度優(yōu)先遍歷，每個頂點(diǎn)訪問且只訪問一次。一次。 ADT Graph7.2 7.2 圖的存儲構(gòu)造圖的存儲構(gòu)造 圖的存儲構(gòu)造比較復(fù)雜，其復(fù)雜性主要表如今：圖的存儲構(gòu)造比較復(fù)雜，

19、其復(fù)雜性主要表如今： 任意頂點(diǎn)之間可能存在聯(lián)絡(luò)，無法以數(shù)據(jù)元素任意頂點(diǎn)之間可能存在聯(lián)絡(luò)，無法以數(shù)據(jù)元素在存儲區(qū)中的在存儲區(qū)中的物理位置來表示元素之間的關(guān)系物理位置來表示元素之間的關(guān)系。 圖中頂點(diǎn)的度不一樣，有的可能相差很大，假圖中頂點(diǎn)的度不一樣，有的可能相差很大，假設(shè)按度數(shù)最大的頂點(diǎn)設(shè)計(jì)構(gòu)造，那么會浪費(fèi)很多存設(shè)按度數(shù)最大的頂點(diǎn)設(shè)計(jì)構(gòu)造，那么會浪費(fèi)很多存儲單元，反之按每個頂點(diǎn)自己的度設(shè)計(jì)不同的構(gòu)造，儲單元，反之按每個頂點(diǎn)自己的度設(shè)計(jì)不同的構(gòu)造，又會影響操作。又會影響操作。 圖的常用的存儲構(gòu)造有：圖的常用的存儲構(gòu)造有：鄰接矩陣鄰接矩陣、鄰接鏈表鄰接鏈表、十字鏈表十字鏈表、鄰接多重表鄰接多重表和和邊

20、表邊表。7.2.1 鄰接矩陣鄰接矩陣數(shù)組數(shù)組表表示法示法 根本思想根本思想：對于有對于有n個頂點(diǎn)的圖，用一維數(shù)組個頂點(diǎn)的圖，用一維數(shù)組vexsn存儲頂點(diǎn)信息，用二維數(shù)組存儲頂點(diǎn)信息，用二維數(shù)組Ann存儲頂存儲頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣鄰接矩陣。在。在鄰接矩陣中，以頂點(diǎn)在鄰接矩陣中，以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素鄰接矩陣中的元素Aij存放的是頂點(diǎn)存放的是頂點(diǎn)i到頂點(diǎn)到頂點(diǎn)j之間之間關(guān)系的信息。關(guān)系的信息。 1 無向圖無向圖-無權(quán)圖的鄰接矩陣無權(quán)圖的鄰接矩陣 無向無權(quán)圖無向無權(quán)圖G=V，E有有nn1個頂點(diǎn)

21、，其鄰接矩陣個頂點(diǎn)，其鄰接矩陣是是n階對稱方陣，如圖階對稱方陣，如圖7-5所示。其元素的定義如下：所示。其元素的定義如下：(a) 無向圖無向圖 abcd圖圖7-5 無向無權(quán)圖的數(shù)組存儲無向無權(quán)圖的數(shù)組存儲(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 鄰接矩陣鄰接矩陣1 若若(vi , vj) E，即，即vi , vj鄰接鄰接0 若若(vi , vj) E，即，即vi , vj不鄰接不鄰接Aij= 1 無向圖無向圖-帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 無向帶權(quán)圖無向帶權(quán)圖G=V，E 的鄰接矩陣如圖的鄰接矩陣如圖7-6所所示。其元素的定義如下

22、：示。其元素的定義如下：(a) 帶權(quán)無向圖帶權(quán)無向圖 (b) 頂點(diǎn)矩陣頂點(diǎn)矩陣圖圖7-6 無向帶權(quán)圖的數(shù)組存儲無向帶權(quán)圖的數(shù)組存儲(c) 鄰接矩陣鄰接矩陣354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若(vi , vj) E，即，即vi , vj不鄰接時不鄰接時Aij= 無向圖鄰接矩陣的特性：無向圖鄰接矩陣的特性： 鄰接矩陣是鄰接矩陣是對稱方陣對稱方陣； 對于頂點(diǎn)對于頂點(diǎn)vi，其，其度數(shù)度數(shù)是第是第i行的非行的非0元素的個數(shù)；元素的個數(shù)； 無向圖的無向圖

23、的邊數(shù)邊數(shù)是上是上或下或下三角形矩陣中非三角形矩陣中非0元素個數(shù)。元素個數(shù)。 2 有向圖有向圖- 無權(quán)圖的鄰接矩陣無權(quán)圖的鄰接矩陣 假設(shè)有向無權(quán)圖假設(shè)有向無權(quán)圖G=V，E有有nn1個頂點(diǎn)，個頂點(diǎn)，那么其鄰接矩陣是那么其鄰接矩陣是n階對稱方陣階對稱方陣，如圖，如圖7-7所示。元素定所示。元素定義如下：義如下：1 若若 E，從，從vi到到vj有弧有弧Aij=0 若若 E 從從vi到到vj 沒有弧沒有弧(a) 有向圖有向圖acbde圖圖7-7 有向無權(quán)圖的數(shù)組存儲有向無權(quán)圖的數(shù)組存儲(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcde(c) 鄰接矩陣鄰接矩陣0 1 1 0 10 0 0 0 00 0 0 1

24、11 1 0 0 00 0 0 1 0 2 有向圖有向圖- 帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 有向帶權(quán)圖有向帶權(quán)圖G=V，E的鄰接矩陣如圖的鄰接矩陣如圖7-8所示。所示。其元素的定義如下：其元素的定義如下：wij 若若 E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若 E，即，即vi , vj不鄰接時不鄰接時Aij=圖圖7-8 帶權(quán)有向圖的數(shù)組存儲帶權(quán)有向圖的數(shù)組存儲(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcde(c) 鄰接矩陣鄰接矩陣 6 2 3 3 1 4 5 (a) 帶權(quán)有向圖帶權(quán)有向圖 354126abcde3 有向圖鄰接矩陣的特性：有向圖鄰接矩陣的特性： 對于頂點(diǎn)對于頂點(diǎn)vi

25、，第，第i行的非行的非0元素的個數(shù)是其元素的個數(shù)是其出度出度ODvi；第；第i列的非列的非0元素的個數(shù)是其元素的個數(shù)是其入度入度IDvi 。 鄰接矩陣中非鄰接矩陣中非0元素的個數(shù)就是圖的弧的數(shù)目。元素的個數(shù)就是圖的弧的數(shù)目。 3 圖的鄰接矩陣的操作圖的鄰接矩陣的操作 圖的鄰接矩陣的實(shí)現(xiàn)比較容易，定義兩個數(shù)組分圖的鄰接矩陣的實(shí)現(xiàn)比較容易，定義兩個數(shù)組分別存儲別存儲頂點(diǎn)信息頂點(diǎn)信息數(shù)據(jù)元素?cái)?shù)據(jù)元素和和邊或弧的信息邊或弧的信息數(shù)據(jù)數(shù)據(jù)元素之間的關(guān)系元素之間的關(guān)系 。其。其存儲構(gòu)造形式定義存儲構(gòu)造形式定義如下：如下：#define INFINITY MAX_VAL /* 最大值最大值 */ /* 根據(jù)

26、圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù)根據(jù)圖的權(quán)值類型，分別定義為最大整數(shù)或?qū)崝?shù) */#define MAX_VEX 30 /* 最大頂點(diǎn)數(shù)目最大頂點(diǎn)數(shù)目 */typedef enum DG, AG, WDG,WAG GraphKind ; /* 有向圖，無向圖，帶權(quán)有向圖，帶權(quán)無向圖有向圖，無向圖，帶權(quán)有向圖，帶權(quán)無向圖 */typedef struct ArcCell VRType adj ; /*弧或邊兩頂點(diǎn)關(guān)系弧或邊兩頂點(diǎn)關(guān)系,1或或0或權(quán)值或無窮或權(quán)值或無窮 */InfoType *Info ; /* 弧或邊的其它信息弧或邊的其它信息 */ArcCell ; /* 弧或邊的構(gòu)造定義弧

27、或邊的構(gòu)造定義 */typedef struct GraphKind kind ; /* 圖的種類標(biāo)志圖的種類標(biāo)志 */int vexnum , arcnum ; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) */VexType vexsMAX_VEX ; /* 頂點(diǎn)向量頂點(diǎn)向量 */ArcCell arcsMAX_VEXMAX_VEX;MGraph ; /* 圖的構(gòu)造定義圖的構(gòu)造定義 */ 利用上述定義的數(shù)據(jù)構(gòu)造，可以方便地實(shí)利用上述定義的數(shù)據(jù)構(gòu)造，可以方便地實(shí)現(xiàn)圖的各種操作?，F(xiàn)圖的各種操作。1 圖的創(chuàng)立圖的創(chuàng)立AdjGraph *Create_GraphMGraph * G printf

28、“請輸入圖的種類標(biāo)志：請輸入圖的種類標(biāo)志： ;scanf“%d, &G-kind ;G-vexnum=0 ; /* 初始化頂點(diǎn)個數(shù)初始化頂點(diǎn)個數(shù) */returnG ; 2 圖的頂點(diǎn)定圖的頂點(diǎn)定位位 圖的頂點(diǎn)定位操作實(shí)際上是確定一個頂點(diǎn)在圖的頂點(diǎn)定位操作實(shí)際上是確定一個頂點(diǎn)在vexs數(shù)組中的位置數(shù)組中的位置下標(biāo)下標(biāo) ，其過程完全等同于在順序，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素。存儲的線性表中查找一個數(shù)據(jù)元素。int LocateVexMGraph *G , VexType *vp int k ; for k=0 ; kvexnum ; k+ if G-vexsk=*v

29、p returnk ; return-1 ; /* 圖中無此頂點(diǎn)圖中無此頂點(diǎn) */ 3 向圖中增加頂點(diǎn)向圖中增加頂點(diǎn) 向圖中增加一個頂點(diǎn)的操作，類似在順序存儲的向圖中增加一個頂點(diǎn)的操作，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。線性表的末尾增加一個數(shù)據(jù)元素。int AddVertexMGraph *G , VexType *vp int k , j ;if G-vexnum=MAX_VEX printf“Vertex Overflow !n ; return-1 ; if LocateVexG , vp!=-1 printf“Vertex has existed !n ; return-1

30、 ; k=G-vexnum ; G-vexsG-vexnum+=*vp ;if G-kind=DG|G-kind=AG for j=0 ; jvexnum ; j+G-adjjk.ArcVal=G-adjkj.ArcVal=0 ; /* 是不帶權(quán)的有向圖或無向圖是不帶權(quán)的有向圖或無向圖 */elsefor j=0 ; jvexnum ; j+ G-adjjk.ArcVal=INFINITY ; G-adjkj.ArcVal=INFINITY ; /* 是帶權(quán)的有向圖或無向圖是帶權(quán)的有向圖或無向圖 */returnk ; 4 向圖中增加一條弧向圖中增加一條弧 根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改鄰

31、接矩陣根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改鄰接矩陣中所對應(yīng)的數(shù)組元素。中所對應(yīng)的數(shù)組元素。 int AddArcMGraph *G , ArcType *arc int k , j ;k=LocateVexG , &arc-vex1 ;j=LocateVexG , &arc-vex1 ;if k=-1|j=-1 printf“Arcs Vertex do not existed !n ;return-1 ;if G-kind=DG|G-kind=WDG G-adjkj.ArcVal=arc-ArcVal;G-adjkj.ArcInfo=arc-ArcInfo ; /* 是有向圖或

32、帶權(quán)的有向圖是有向圖或帶權(quán)的有向圖*/else G-adjkj.ArcVal=arc-ArcVal ;G-adjjk.ArcVal=arc-ArcVal ;G-adjkj.ArcInfo=arc-ArcInfo ;G-adjjk.ArcInfo=arc-ArcInfo ; /* 是無向圖或帶權(quán)的無向圖是無向圖或帶權(quán)的無向圖,需對稱賦值需對稱賦值 */return1 ; 7.2.2 鄰接鏈表法鄰接鏈表法 根本思想：根本思想：對圖的每個頂點(diǎn)建立一個單鏈對圖的每個頂點(diǎn)建立一個單鏈表，存儲該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。表，存儲該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。每一個單鏈表設(shè)一個表頭結(jié)點(diǎn)。每一個單鏈表設(shè)

33、一個表頭結(jié)點(diǎn)。 第第i個單鏈表表示依附于頂點(diǎn)個單鏈表表示依附于頂點(diǎn)Vi的邊的邊對對有向圖是以頂點(diǎn)有向圖是以頂點(diǎn)Vi為頭或尾的弧為頭或尾的弧。 1 結(jié)點(diǎn)構(gòu)造與鄰接鏈表例如結(jié)點(diǎn)構(gòu)造與鄰接鏈表例如 鏈表中的結(jié)點(diǎn)稱為鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)表結(jié)點(diǎn)，每個結(jié)點(diǎn)由三個域組成，如圖，每個結(jié)點(diǎn)由三個域組成，如圖7-9a所示。其中所示。其中鄰接點(diǎn)域鄰接點(diǎn)域adjvex指示與頂點(diǎn)指示與頂點(diǎn)Vi鄰接的鄰接的頂點(diǎn)在圖中的位置頂點(diǎn)在圖中的位置頂點(diǎn)編號頂點(diǎn)編號，鏈域鏈域nextarc指向下一個指向下一個與頂點(diǎn)與頂點(diǎn)Vi鄰接的表結(jié)點(diǎn)，鄰接的表結(jié)點(diǎn)，數(shù)據(jù)域數(shù)據(jù)域info存儲和邊或弧相關(guān)的信存儲和邊或弧相關(guān)的信息，如權(quán)值等。對于無

34、權(quán)圖，假如沒有與邊相關(guān)的其他信息，可息，如權(quán)值等。對于無權(quán)圖，假如沒有與邊相關(guān)的其他信息，可省略此域。省略此域。 每個鏈表設(shè)一個表頭結(jié)點(diǎn)每個鏈表設(shè)一個表頭結(jié)點(diǎn)稱為稱為頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)，由兩個域組成，由兩個域組成，如圖如圖7-9b所示。所示。鏈域鏈域firstarc指向鏈表中的第一個結(jié)點(diǎn)，指向鏈表中的第一個結(jié)點(diǎn)，數(shù)據(jù)域數(shù)據(jù)域data 存儲頂點(diǎn)名或其他信息。存儲頂點(diǎn)名或其他信息。adjvex info nextarc表結(jié)點(diǎn)表結(jié)點(diǎn)：data firstarc頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)：圖圖7-9 鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu)鄰接鏈表結(jié)點(diǎn)結(jié)構(gòu) 用鄰接鏈表存儲圖時，對無向圖，其鄰接鏈表是唯用鄰接鏈表存儲圖時，對無向圖，其鄰接

35、鏈表是唯一的，如圖一的，如圖7-10所示；對有向圖，其鄰接鏈表有兩種形所示；對有向圖，其鄰接鏈表有兩種形式，如圖式，如圖7-11所示。所示。圖圖7-10 無向圖及其鄰接鏈表無向圖及其鄰接鏈表v1v2v3v4v501234MAX_VEX-1v1 v2v3 v4 v5 213 02 0314 204 23 (a) 有向圖有向圖v1v2v3v4v513 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 (b) 正鄰接鏈表，出度直觀正鄰接鏈表，出度直觀2 02 2 01234MAX_VEX-1v1 1v2 2v3 1v4 2 v5 1 3 04 (c) 逆鄰接

36、鏈表，入度直觀逆鄰接鏈表，入度直觀圖圖7-11 有向圖及其鄰接鏈表有向圖及其鄰接鏈表構(gòu)造體定義，詳見P163 鄰接表法的特點(diǎn)鄰接表法的特點(diǎn) 表頭向量中每個分量就是一個單鏈表的頭結(jié)點(diǎn)，分量個數(shù)就是圖中表頭向量中每個分量就是一個單鏈表的頭結(jié)點(diǎn)，分量個數(shù)就是圖中的頂點(diǎn)數(shù)目；的頂點(diǎn)數(shù)目； 在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲在邊或弧稀疏的條件下，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；空間； 在無向圖，頂點(diǎn)在無向圖，頂點(diǎn)Vi的度是第的度是第i個鏈表的結(jié)點(diǎn)數(shù)；個鏈表的結(jié)點(diǎn)數(shù)； 對對有向圖有向圖可以建立可以建立正鄰接表正鄰接表或或逆鄰接表逆鄰接表。正鄰接表是以頂點(diǎn)。正鄰接表是以頂點(diǎn)

37、Vi為出為出度度即為弧的起點(diǎn)即為弧的起點(diǎn)而建立的鄰接表；逆鄰接表是以頂點(diǎn)而建立的鄰接表；逆鄰接表是以頂點(diǎn)Vi為入度為入度即即為弧的終點(diǎn)為弧的終點(diǎn)而建立的鄰接表；而建立的鄰接表； 在有向圖中，第在有向圖中，第i個鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)個鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)Vi的出的出 或入或入度；求入度；求入 或出或出度，須遍歷整個鄰接表；度，須遍歷整個鄰接表； 在鄰接表上容易找出任一頂點(diǎn)的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)；在鄰接表上容易找出任一頂點(diǎn)的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)；7.2.3 十字鏈表法十字鏈表法 十字鏈表十字鏈表Orthogonal List是有向圖的另一種是有向圖的另一種鏈?zhǔn)酱鎯?gòu)造，是將有向圖的正鄰

38、接表和逆鄰接表結(jié)合鏈?zhǔn)酱鎯?gòu)造，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。起來得到的一種鏈表。 在這種構(gòu)造中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都在這種構(gòu)造中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都存放在鏈表中，并將存放在鏈表中，并將弧結(jié)點(diǎn)弧結(jié)點(diǎn)分別組織到分別組織到以弧尾結(jié)點(diǎn)為頭以弧尾結(jié)點(diǎn)為頭頂點(diǎn)頂點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)和和以弧頭結(jié)點(diǎn)為頭以弧頭結(jié)點(diǎn)為頭頂點(diǎn)頂點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)的鏈表中。的鏈表中。這種構(gòu)造的結(jié)點(diǎn)邏輯構(gòu)造如圖這種構(gòu)造的結(jié)點(diǎn)邏輯構(gòu)造如圖7-12所示。所示?；〗Y(jié)點(diǎn)弧結(jié)點(diǎn)tailvex headvex info hlink tlink頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)Data firstin firstout圖圖7-12 十字鏈表

39、結(jié)點(diǎn)結(jié)構(gòu)十字鏈表結(jié)點(diǎn)結(jié)構(gòu) data域：存儲和頂點(diǎn)相關(guān)的信息；域：存儲和頂點(diǎn)相關(guān)的信息； 指針域指針域firstin：指向：指向以該頂點(diǎn)為弧頭以該頂點(diǎn)為弧頭的第一條的第一條弧所對應(yīng)的弧結(jié)點(diǎn)；弧所對應(yīng)的弧結(jié)點(diǎn)； 指針域指針域firstout：指向：指向以該頂點(diǎn)為弧尾以該頂點(diǎn)為弧尾的第一條的第一條弧所對應(yīng)的弧結(jié)點(diǎn)；弧所對應(yīng)的弧結(jié)點(diǎn)； 尾域尾域tailvex：指示弧尾頂點(diǎn)在圖中的位置；：指示弧尾頂點(diǎn)在圖中的位置； 頭域頭域headvex：指示弧頭頂點(diǎn)在圖中的位置；：指示弧頭頂點(diǎn)在圖中的位置； 指針域指針域hlink：指向弧頭一樣的下一條??；：指向弧頭一樣的下一條??； 指針域指針域tlink：指向弧尾一

40、樣的下一條??；：指向弧尾一樣的下一條弧； Info域：指向該弧的相關(guān)信息；域：指向該弧的相關(guān)信息；V0V1V2V30 10 2 2 02 3 3 0 3 1 3 2 0213V0V1 V2V3圖圖7-13 有向圖的十字鏈表結(jié)構(gòu)有向圖的十字鏈表結(jié)構(gòu)有向圖的十字鏈表構(gòu)造構(gòu)造體定義，詳見P1657.2.4 鄰接多重表鄰接多重表 鄰接多重表鄰接多重表Adjacency Multilist是無向圖的另一種是無向圖的另一種鏈?zhǔn)酱鎯?gòu)造。鏈?zhǔn)酱鎯?gòu)造。 鄰接表是無向圖的一種有效的存儲構(gòu)造，在無向圖的鄰鄰接表是無向圖的一種有效的存儲構(gòu)造，在無向圖的鄰接表中，一條邊接表中，一條邊v,w的兩個表結(jié)點(diǎn)分別初選在以的

41、兩個表結(jié)點(diǎn)分別初選在以v和和w為為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會帶來不便。的操作會帶來不便。 鄰接多重表的構(gòu)造和十字鏈表類似，鄰接多重表的構(gòu)造和十字鏈表類似，每條邊用一個結(jié)點(diǎn)每條邊用一個結(jié)點(diǎn)表示表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)構(gòu)造與鄰接表中的完全一樣，；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)構(gòu)造與鄰接表中的完全一樣，而表結(jié)點(diǎn)包括六個域如圖而表結(jié)點(diǎn)包括六個域如圖7-14所示。所示。data firstedge頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)圖圖7-14 鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)表結(jié)點(diǎn)mark ivex ilink jvex

42、jlink info Data域：存儲和頂點(diǎn)相關(guān)的信息；域：存儲和頂點(diǎn)相關(guān)的信息； 指針域指針域firstedge：指向依附于該頂點(diǎn)的第一條邊：指向依附于該頂點(diǎn)的第一條邊所對應(yīng)的表結(jié)點(diǎn)；所對應(yīng)的表結(jié)點(diǎn)； 標(biāo)志域標(biāo)志域mark：用以標(biāo)識該條邊是否被訪問過；：用以標(biāo)識該條邊是否被訪問過； ivex和和jvex域：分別保存該邊所依附的兩個頂點(diǎn)域：分別保存該邊所依附的兩個頂點(diǎn)在圖中的位置；在圖中的位置； info域：保存該邊的相關(guān)信息；域：保存該邊的相關(guān)信息； 指針域指針域ilink：指向下一條依附于頂點(diǎn)：指向下一條依附于頂點(diǎn)ivex的邊；的邊； 指針域指針域jlink：指向下一條依附于頂點(diǎn)：指向下一

43、條依附于頂點(diǎn)jvex的邊；的邊； 鄰接多重表與鄰接表的區(qū)別鄰接多重表與鄰接表的區(qū)別： 后者的同一條邊用兩個表結(jié)點(diǎn)表示，而前者只用后者的同一條邊用兩個表結(jié)點(diǎn)表示，而前者只用一個表結(jié)點(diǎn)表示一個表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表與鄰接表除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是一樣的，因此，操作的實(shí)現(xiàn)也根本相似。表達(dá)的信息是一樣的，因此，操作的實(shí)現(xiàn)也根本相似。圖圖7-15 無向圖及其多重鄰接鏈表無向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v40123 0 1 0 2 2 1 2 3 0 3構(gòu)造體定義，詳見P166-1677.3 圖的遍歷圖的遍歷 圖的遍歷圖的遍歷Travering Graph：

44、從圖的某一頂點(diǎn)出發(fā)，訪：從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，且每個頂點(diǎn)僅被訪問一次。圖的遍歷算法是遍圖中的其余頂點(diǎn)，且每個頂點(diǎn)僅被訪問一次。圖的遍歷算法是各種圖的操作的根底。各種圖的操作的根底。 復(fù)雜性：復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問了某個頂點(diǎn)后，沿某條途徑搜索后又回到原頂點(diǎn)。在訪問了某個頂點(diǎn)后，沿某條途徑搜索后又回到原頂點(diǎn)。 解決方法：解決方法：在遍歷過程中記下已被訪問過的頂點(diǎn)。設(shè)置在遍歷過程中記下已被訪問過的頂點(diǎn)。設(shè)置一個輔助向量一個輔助向量Visited1nn為頂點(diǎn)數(shù)為頂點(diǎn)數(shù)，其初值為，其初值為0，一旦訪問了頂點(diǎn)一旦訪問

45、了頂點(diǎn)vi后，使后，使Visitedi為為1或?yàn)樵L問的次序號或?yàn)樵L問的次序號。 圖的遍歷算法有圖的遍歷算法有深度優(yōu)先搜索算法深度優(yōu)先搜索算法和和廣度優(yōu)先搜索廣度優(yōu)先搜索算法算法。采用的數(shù)據(jù)構(gòu)造是。采用的數(shù)據(jù)構(gòu)造是正正鄰接鏈表鄰接鏈表。7.3.1 深度優(yōu)先搜索算法深度優(yōu)先搜索算法 深度優(yōu)先搜索深度優(yōu)先搜索Depth First Search-DFS遍歷類似遍歷類似樹樹的先序遍歷的先序遍歷，是，是樹的先序遍歷的推廣樹的先序遍歷的推廣。1 算法思想算法思想 設(shè)初始狀態(tài)時圖中的所有頂點(diǎn)未被訪問，那么：設(shè)初始狀態(tài)時圖中的所有頂點(diǎn)未被訪問，那么： 從圖中某個頂點(diǎn)從圖中某個頂點(diǎn)vi出發(fā)出發(fā)，訪問，訪問vi；

46、然后找到；然后找到vi的的一個鄰一個鄰接頂點(diǎn)接頂點(diǎn)vi1 ； 從從vi1出發(fā)，深度優(yōu)先搜索訪問和出發(fā)，深度優(yōu)先搜索訪問和vi1相相鄰接且未被訪問鄰接且未被訪問的所有頂點(diǎn)；的所有頂點(diǎn)； 轉(zhuǎn)轉(zhuǎn) ，直到和，直到和vi相相鄰接的所有頂點(diǎn)都被訪問為止鄰接的所有頂點(diǎn)都被訪問為止 繼續(xù)選取圖中未被訪問頂點(diǎn)繼續(xù)選取圖中未被訪問頂點(diǎn)vj作為起始頂點(diǎn)，轉(zhuǎn)作為起始頂點(diǎn)，轉(zhuǎn)1 1，直到圖中所有頂點(diǎn)都被訪問為止。直到圖中所有頂點(diǎn)都被訪問為止。圖圖7-17 無向圖深度優(yōu)先搜索遍歷無向圖深度優(yōu)先搜索遍歷(a) 無向圖無向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234MAX_VEX-1v1 v2v3 v4

47、v5 21 20 01 4 3 無向圖的深度優(yōu)先搜索遍歷例如無向圖的深度優(yōu)先搜索遍歷例如紅色箭紅色箭頭頭。某種。某種DFS次序是次序是：v1 v3 v2 v4 v5 由算法思想知，這是一個遞歸過程。因此，先設(shè)由算法思想知，這是一個遞歸過程。因此，先設(shè)計(jì)一個從某個頂點(diǎn)計(jì)一個從某個頂點(diǎn)編號編號為為v0開場開場深度優(yōu)先深度優(yōu)先搜索的搜索的函數(shù)函數(shù)，便于調(diào)用。，便于調(diào)用。代碼詳見代碼詳見P169P1692 算法實(shí)現(xiàn)算法實(shí)現(xiàn)3 算法分析算法分析 遍歷時，對圖的每個頂點(diǎn)至多調(diào)用一次遍歷時，對圖的每個頂點(diǎn)至多調(diào)用一次DFS函函數(shù)。其本質(zhì)就是對每個頂點(diǎn)查找鄰接頂點(diǎn)的過程，取數(shù)。其本質(zhì)就是對每個頂點(diǎn)查找鄰接頂點(diǎn)

48、的過程，取決于存儲構(gòu)造。當(dāng)圖有決于存儲構(gòu)造。當(dāng)圖有e條邊，其時間復(fù)雜度為條邊，其時間復(fù)雜度為Oe，總時間復(fù)雜度為，總時間復(fù)雜度為On+e 。7.3.2 廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法 廣度優(yōu)先搜索廣度優(yōu)先搜索Breadth First Search-BFS遍歷類似遍歷類似樹樹的按層次遍歷的按層次遍歷的過程的過程。1 算法思想算法思想 設(shè)初始狀態(tài)時圖中的所有頂點(diǎn)未被訪問，那么：設(shè)初始狀態(tài)時圖中的所有頂點(diǎn)未被訪問，那么： 從圖中某個頂點(diǎn)從圖中某個頂點(diǎn)vi出發(fā)出發(fā)，訪問，訪問vi； 訪問訪問vi的所有相的所有相鄰接且未被訪問的所有頂點(diǎn)鄰接且未被訪問的所有頂點(diǎn)vi1，vi2，vim； 以以vi1，v

49、i2， ，vim的次序的次序，以，以vij1jm依此作依此作為為vi ，轉(zhuǎn)；，轉(zhuǎn)； 繼續(xù)選取圖中繼續(xù)選取圖中未被訪問未被訪問頂點(diǎn)頂點(diǎn)vk作為起始頂點(diǎn)作為起始頂點(diǎn)，轉(zhuǎn)，直，轉(zhuǎn)，直到圖中所有頂點(diǎn)都被訪問為止。到圖中所有頂點(diǎn)都被訪問為止。有向圖的廣度優(yōu)先搜索遍歷例如有向圖的廣度優(yōu)先搜索遍歷例如紅色箭頭紅色箭頭。上述圖的上述圖的BFS次序是次序是：v1 v2 v4 v3 v5(b) G的正鄰接鏈表的正鄰接鏈表13 014 2 3 01234MAX_VEX-1v1 2 v2 0 v3 3v4 1 v5 1 圖圖7-18 有向圖廣度優(yōu)先搜索遍歷有向圖廣度優(yōu)先搜索遍歷(a) 有向圖有向圖Gv1v2v3v4v

50、5 2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 為了標(biāo)記圖中頂點(diǎn)是否被訪問過，同樣需要一個為了標(biāo)記圖中頂點(diǎn)是否被訪問過，同樣需要一個訪問標(biāo)記數(shù)組；其次，為了依此訪問與訪問標(biāo)記數(shù)組；其次，為了依此訪問與vi相鄰接的各相鄰接的各個頂點(diǎn)個頂點(diǎn)，需要附加一個隊(duì)列來保存訪問，需要附加一個隊(duì)列來保存訪問vi的相鄰接的的相鄰接的頂點(diǎn)。頂點(diǎn)。代碼實(shí)現(xiàn)詳見代碼實(shí)現(xiàn)詳見P170P170。 3 算法分析算法分析 用用廣度優(yōu)先搜索算法廣度優(yōu)先搜索算法遍歷圖與遍歷圖與深度優(yōu)先搜索算法深度優(yōu)先搜索算法遍歷圖的遍歷圖的唯一區(qū)別唯一區(qū)別是是鄰接點(diǎn)搜索次序不同鄰接點(diǎn)搜索次序不同，因此，因此，廣廣度優(yōu)先搜索算法度優(yōu)先搜索算法遍歷圖的總時間復(fù)雜度為遍歷

51、圖的總時間復(fù)雜度為On+e 。7.4 圖的連通性問題圖的連通性問題 本節(jié)所討論的內(nèi)容是圖的遍歷算法的詳細(xì)應(yīng)用。本節(jié)所討論的內(nèi)容是圖的遍歷算法的詳細(xì)應(yīng)用。7.4.1 無向圖的連通分量與生成樹無向圖的連通分量與生成樹1 無向圖的連通分量和生成樹無向圖的連通分量和生成樹 對于無向圖，對其進(jìn)展遍歷時：對于無向圖，對其進(jìn)展遍歷時： 假設(shè)是假設(shè)是連通圖連通圖：僅需從圖中：僅需從圖中任一頂點(diǎn)出發(fā)任一頂點(diǎn)出發(fā)，就能訪問，就能訪問圖中的所有頂點(diǎn)；圖中的所有頂點(diǎn)； 假設(shè)是假設(shè)是非連通圖非連通圖：需從圖中：需從圖中多個頂點(diǎn)出發(fā)多個頂點(diǎn)出發(fā)。每次從一。每次從一個新頂點(diǎn)出發(fā)所訪問的頂點(diǎn)集序列個新頂點(diǎn)出發(fā)所訪問的頂點(diǎn)集序

52、列恰好是恰好是各個連通分量的各個連通分量的頂點(diǎn)集；頂點(diǎn)集；(a) 無向圖無向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234MAX_VEX-1v1 v2v3 v4 v5 21 20 01 4 3 圖圖7-19 無向圖及深度優(yōu)先生成森林無向圖及深度優(yōu)先生成森林(c) 深度優(yōu)先生成森林深度優(yōu)先生成森林v1v2v3v4v5無向非連通圖，按圖中給定的鄰接表進(jìn)展深度無向非連通圖，按圖中給定的鄰接表進(jìn)展深度優(yōu)先搜索遍歷，優(yōu)先搜索遍歷，2次調(diào)用次調(diào)用DFS所得到的頂點(diǎn)訪所得到的頂點(diǎn)訪問序列集是：問序列集是： v1 ,v3 ,v2和和 v4 ,v5 假設(shè)假設(shè)G=V,E是無向連通圖是無向連通圖，

53、 頂點(diǎn)集和邊集頂點(diǎn)集和邊集分別是分別是VG ，EG 。假設(shè)從。假設(shè)從G中中任意點(diǎn)出發(fā)遍任意點(diǎn)出發(fā)遍歷時，歷時， EG被分成兩個互不相交的集合：被分成兩個互不相交的集合：TG ：遍歷過程中所：遍歷過程中所經(jīng)過的邊經(jīng)過的邊的集合；的集合；BG ：遍歷過程中：遍歷過程中未經(jīng)過的邊未經(jīng)過的邊的集合；的集合； 顯然：顯然： EG=TGBG ，TGBG= 顯然，顯然，圖圖G=V, TG是是G的極小連通子圖的極小連通子圖，且且G是一棵樹是一棵樹。G稱為圖稱為圖G的一棵生成樹的一棵生成樹。 從任意點(diǎn)出發(fā)從任意點(diǎn)出發(fā)按按DFS算法算法得到生成樹得到生成樹G稱為稱為深度優(yōu)深度優(yōu)先生成樹先生成樹；按按BFS算法算法

54、得到的得到的G稱為稱為廣度優(yōu)先生成樹廣度優(yōu)先生成樹。 假設(shè)假設(shè)G=V,E是無向非連通圖是無向非連通圖，對圖進(jìn)展遍對圖進(jìn)展遍歷時得到假設(shè)干個連通分量的頂點(diǎn)集歷時得到假設(shè)干個連通分量的頂點(diǎn)集：V1G ,V2G ,VnG和相應(yīng)所經(jīng)過的邊集和相應(yīng)所經(jīng)過的邊集：T T1G ,T2G , ,TnG 那么對應(yīng)的頂點(diǎn)集和邊集的二元組：那么對應(yīng)的頂點(diǎn)集和邊集的二元組：Gi=ViG,TiG1in是對應(yīng)分量的生成樹是對應(yīng)分量的生成樹，所有這些，所有這些生成樹構(gòu)生成樹構(gòu)成了原來非連通圖的生成森林成了原來非連通圖的生成森林。說明說明：當(dāng)給定無向圖要求畫出其對應(yīng)的生成樹或生成當(dāng)給定無向圖要求畫出其對應(yīng)的生成樹或生成森林時

55、，森林時，必須先給出相應(yīng)的鄰接表，然后才能根據(jù)鄰必須先給出相應(yīng)的鄰接表，然后才能根據(jù)鄰接表畫出其對應(yīng)的生成樹或生成森林接表畫出其對應(yīng)的生成樹或生成森林。7.4.2 有向圖的強(qiáng)連通分量有向圖的強(qiáng)連通分量 對于有向圖，在其每一個對于有向圖，在其每一個強(qiáng)連通分量中強(qiáng)連通分量中，任何兩任何兩個頂點(diǎn)都是可達(dá)的個頂點(diǎn)都是可達(dá)的。 V G，與，與V可互相到達(dá)的所有可互相到達(dá)的所有頂點(diǎn)就是包含頂點(diǎn)就是包含V的強(qiáng)連通分量的所有頂點(diǎn)的強(qiáng)連通分量的所有頂點(diǎn)。 設(shè)從設(shè)從V可到達(dá)可到達(dá) 以以V為起點(diǎn)的所有有向途徑的終為起點(diǎn)的所有有向途徑的終點(diǎn)點(diǎn)的頂點(diǎn)集合為的頂點(diǎn)集合為T1G，而到達(dá)，而到達(dá)V 以以V為終點(diǎn)的為終點(diǎn)的所有

56、有向途徑的起點(diǎn)所有有向途徑的起點(diǎn)的頂點(diǎn)集合為的頂點(diǎn)集合為T2G，那么，那么包含包含V的強(qiáng)連通分量的頂點(diǎn)集合是的強(qiáng)連通分量的頂點(diǎn)集合是： T1GT2G 。 求有向圖求有向圖G的強(qiáng)連通分量的的強(qiáng)連通分量的根本步驟根本步驟是：是： 對對G進(jìn)展深度優(yōu)先遍歷，生成進(jìn)展深度優(yōu)先遍歷，生成G的深度優(yōu)先生成森的深度優(yōu)先生成森林林T。 對對森林森林T的頂點(diǎn)按的頂點(diǎn)按中序遍歷中序遍歷順序進(jìn)展編號。順序進(jìn)展編號。 改變改變G中每一條弧的方向中每一條弧的方向，構(gòu)成一個新的有向圖，構(gòu)成一個新的有向圖G。 按中標(biāo)出的頂點(diǎn)編號，從編號最大的頂點(diǎn)開場對按中標(biāo)出的頂點(diǎn)編號，從編號最大的頂點(diǎn)開場對G進(jìn)展深度優(yōu)先搜索，得到一棵深度

57、優(yōu)先生成樹。假進(jìn)展深度優(yōu)先搜索，得到一棵深度優(yōu)先生成樹。假設(shè)一次完好的搜索過程沒有遍歷設(shè)一次完好的搜索過程沒有遍歷G的所有頂點(diǎn)，那么的所有頂點(diǎn)，那么從未訪問的頂點(diǎn)中選擇一個編號最大的頂點(diǎn)，由它開從未訪問的頂點(diǎn)中選擇一個編號最大的頂點(diǎn)，由它開場再進(jìn)展深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成場再進(jìn)展深度優(yōu)先搜索，并得到另一棵深度優(yōu)先生成樹。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹。在該步驟中，每一次深度優(yōu)先搜索所得到的生成樹中的頂點(diǎn)就是樹中的頂點(diǎn)就是G的一個強(qiáng)連通分量的所有頂點(diǎn)。的一個強(qiáng)連通分量的所有頂點(diǎn)。 重復(fù)步驟重復(fù)步驟 ，直到，直到G中的所有頂點(diǎn)都被訪問。中的所有頂點(diǎn)都被訪問。dacfeb

58、(a) 有向圖有向圖G654321dacfeb(b) 執(zhí)行步驟執(zhí)行步驟(1)和和(2)acdfeb(c) 執(zhí)行步驟執(zhí)行步驟(3)adcbefd) 執(zhí)行步驟執(zhí)行步驟(4)和和(5)圖圖7-20 利用深度優(yōu)先搜索求有向圖的強(qiáng)連通分量利用深度優(yōu)先搜索求有向圖的強(qiáng)連通分量 在算法實(shí)現(xiàn)時，建立一個數(shù)組在算法實(shí)現(xiàn)時，建立一個數(shù)組in_ordern存放深存放深度優(yōu)先生成森林的中序遍歷序列。對每個頂點(diǎn)度優(yōu)先生成森林的中序遍歷序列。對每個頂點(diǎn)v，在調(diào)，在調(diào)用用DFS函數(shù)完畢時函數(shù)完畢時，將頂點(diǎn)依次存放在將頂點(diǎn)依次存放在數(shù)組數(shù)組in_ordern中中。圖采用十字鏈表作為存儲構(gòu)造最適宜。圖采用十字鏈表作為存儲構(gòu)造最

59、適宜。7.4.3 最小生成樹最小生成樹 假如假如連通圖連通圖是一個帶權(quán)圖，那么其生成樹中的邊也帶權(quán)，是一個帶權(quán)圖，那么其生成樹中的邊也帶權(quán)，生成樹中生成樹中所有邊的權(quán)值之和所有邊的權(quán)值之和稱為稱為生成樹的代價生成樹的代價。 最小生成樹最小生成樹Minimum Spanning Tree ：帶權(quán)帶權(quán)連通圖中代價最小的生成樹稱為最小生成樹連通圖中代價最小的生成樹稱為最小生成樹。 最小生成樹在實(shí)際中具有重要用處，如設(shè)計(jì)通信網(wǎng)。設(shè)最小生成樹在實(shí)際中具有重要用處，如設(shè)計(jì)通信網(wǎng)。設(shè)圖的頂點(diǎn)表示城市，邊表示兩個城市之間的通信線路，邊的圖的頂點(diǎn)表示城市，邊表示兩個城市之間的通信線路，邊的權(quán)值表示建造通信線路的

60、費(fèi)用。權(quán)值表示建造通信線路的費(fèi)用。n個城市之間最多可以建個城市之間最多可以建n n-1/2條線路條線路，如何選擇其中的，如何選擇其中的n-1條，使總的建造費(fèi)用最條，使總的建造費(fèi)用最低低? ?根本原那么是：根本原那么是： 盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路；盡可能選取權(quán)值最小的邊，但不能構(gòu)成回路； 選擇選擇n-1條邊構(gòu)成最小生成樹條邊構(gòu)成最小生成樹。 以上的根本原那么是基于以上的根本原那么是基于MST的如下性質(zhì)：的如下性質(zhì)： 設(shè)設(shè)G=V，E是一個帶權(quán)連通圖，是一個帶權(quán)連通圖，U是頂點(diǎn)集是頂點(diǎn)集V的的 一個非空子集。假設(shè)一個非空子集。假設(shè)uU ，vV-U，且，且u, v是是U中頂點(diǎn)到中頂點(diǎn)到V-U中頂點(diǎn)之間權(quán)值最小的邊，那