圖論算法(C++版)課件

1、第四章 圖論算法 一對(duì)一和一對(duì)多的結(jié)構(gòu)：一對(duì)一和一對(duì)多的結(jié)構(gòu)： 在前邊講解的線性表中，每個(gè)元素之間只有一個(gè)直接前驅(qū)在前邊講解的線性表中，每個(gè)元素之間只有一個(gè)直接前驅(qū)和一個(gè)直接后繼，在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間是層次關(guān)和一個(gè)直接后繼，在樹(shù)形結(jié)構(gòu)中，數(shù)據(jù)元素之間是層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素相系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個(gè)元素相關(guān)，但只能和上一層中一個(gè)元素相關(guān)。關(guān)，但只能和上一層中一個(gè)元素相關(guān)。 圖結(jié)構(gòu)：是研究數(shù)據(jù)元素之間的多對(duì)多的關(guān)系。在這種結(jié)構(gòu)中，任意兩個(gè)元素之間可能存在關(guān)系。即結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意元素之間都可能相關(guān)。 圖的應(yīng)用極為廣泛，已

2、滲入到諸如語(yǔ)言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊、計(jì)算機(jī)科學(xué)以及數(shù)學(xué)的其它分支。一、圖的定義及其術(shù)語(yǔ)一、圖的定義及其術(shù)語(yǔ) 圖（圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，通常表示為：組成，通常表示為：G(V,E)，其中，其中，G表示一個(gè)圖，表示一個(gè)圖，V是圖是圖G中頂點(diǎn)的集合，中頂點(diǎn)的集合，E是圖是圖G中邊的集合。中邊的集合。 對(duì)于圖的定義，我們需要明確幾個(gè)注意的地方： 線性表中我們把數(shù)據(jù)元素叫元素，樹(shù)中叫結(jié)點(diǎn)，在圖中數(shù)據(jù)元素我們則稱之為頂點(diǎn)(Vertex)。 線性表可以沒(méi)有數(shù)據(jù)元素，稱為空表，樹(shù)中可以沒(méi)有結(jié)點(diǎn)，叫做空樹(shù)，而圖結(jié)構(gòu)在國(guó)內(nèi)大部

3、分的教材中強(qiáng)調(diào)頂點(diǎn)集合V要有窮非空。 線性表中，相鄰的數(shù)據(jù)元素之間具有線性關(guān)系，樹(shù)結(jié)構(gòu)中，相鄰兩層的結(jié)點(diǎn)具有層次關(guān)系，而圖結(jié)構(gòu)中，任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系，頂點(diǎn)之間的邏輯關(guān)系用邊來(lái)表示，邊集可以是空的。圖的各種定義 無(wú)向邊：若頂點(diǎn)Vi到Vj之間的邊沒(méi)有方向，則稱這條邊為無(wú)向邊(Edge)，用無(wú)序偶數(shù)對(duì)(Vi,Vj)來(lái)表示。 無(wú)向圖：圖中所有頂點(diǎn)間的邊均是無(wú)向的。上圖上圖G1是一個(gè)無(wú)向圖，是一個(gè)無(wú)向圖，G1=V1,E1，其中，其中V1=A,B,C,D，E1=(A,B),(B,C),(C,D),(D,A),(A,C)無(wú)序?qū)o(wú)序?qū)?A,B) 表示表示A和和B之間的一條之間的一條邊邊(Edge)，

4、因此，因此(A,B) 和和(B,A)代表的是同一條邊。代表的是同一條邊。上圖上圖G2是一個(gè)無(wú)向圖，是一個(gè)無(wú)向圖，G2=V2,E2，其中，其中V2=A,B,C,D，E2=,有向邊：若從頂點(diǎn)有向邊：若從頂點(diǎn)Vi到到Vj的邊有方向，則稱這條邊為的邊有方向，則稱這條邊為有向邊，也稱為弧有向邊，也稱為弧(Arc)，用有序偶數(shù)對(duì)，用有序偶數(shù)對(duì)來(lái)表來(lái)表示，示，Vi稱為弧尾，稱為弧尾，Vj稱為弧頭。稱為弧頭。 有向圖：圖中所有頂點(diǎn)間的邊均是有向的。有向圖：圖中所有頂點(diǎn)間的邊均是有向的。簡(jiǎn)單圖：在圖結(jié)構(gòu)中，若不存在頂點(diǎn)到其自身的邊，且同一條邊不重復(fù)出現(xiàn)，則稱這樣的圖為簡(jiǎn)單圖。以下兩個(gè)則不屬于簡(jiǎn)單圖：稀疏圖、稠密

5、圖、權(quán)稀疏圖、稠密圖、權(quán)有很少邊或弧的圖（有很少邊或弧的圖（enn）的圖稱為稀疏圖，反之稱為稠密圖。）的圖稱為稀疏圖，反之稱為稠密圖。權(quán)權(quán)(Weight)：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個(gè)頂點(diǎn)到：與圖的邊和弧相關(guān)的數(shù)。權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。另一個(gè)頂點(diǎn)的距離或耗費(fèi)。帶權(quán)的圖通常稱為網(wǎng)帶權(quán)的圖通常稱為網(wǎng)(Network)。無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。含有n個(gè)頂點(diǎn)的無(wú)向完全圖有n*(n-1)/2條邊。有向完全圖：在有向圖中，如果有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向互任意兩個(gè)頂點(diǎn)之間都存在方向互為相反的兩條

6、弧，則稱該圖為有為相反的兩條弧，則稱該圖為有向完全圖。向完全圖。含有含有n個(gè)頂點(diǎn)的有向完全圖有個(gè)頂點(diǎn)的有向完全圖有n*(n-1)條邊。條邊。假設(shè)有兩個(gè)圖假設(shè)有兩個(gè)圖G1=(V1,E1)和和G2=(V2,E2)，如果，如果V2V1，E2E1，則稱，則稱G2為為G1的子圖的子圖(Subgraph)。圖的頂點(diǎn)與邊之間的關(guān)系 對(duì)于無(wú)向圖G=(V,E)，如果邊(V1,V2)E，則稱頂點(diǎn)V1和V2互為鄰接點(diǎn)(Adjacent)，即V1和V2相鄰接。 邊(V1,V2)依附(incident)于頂點(diǎn)V1和V2，或者說(shuō)邊(V1,V2)與頂點(diǎn)V1和V2相關(guān)聯(lián)。 頂點(diǎn)V的度(Degree)是和V相關(guān)聯(lián)的邊的數(shù)目，記

7、為TD(V)，如下圖，頂點(diǎn)A與B互為鄰接點(diǎn)，邊(A,B)依附于頂點(diǎn)A與B上，頂點(diǎn)A的度為3。對(duì)于有向圖G=(V,E)，如果有E，則稱頂點(diǎn)V1鄰接到頂點(diǎn)V2，頂點(diǎn)V2鄰接自頂點(diǎn)V1。以頂點(diǎn)V為頭的弧的數(shù)目稱為V的入度(InDegree)，記為ID(V)，以V為尾的弧的數(shù)目稱為V的出度(OutDegree)，記為OD(V)，因此頂點(diǎn)V的度為TD(V)=ID(V)+OD(V)。 下圖頂點(diǎn)A的入度是2，出度是1，所以頂點(diǎn)A的度是3。路徑(Path)、路徑長(zhǎng)度、回路(Cycle) ：對(duì)無(wú)向圖G=(V，E)，若從頂點(diǎn)vi經(jīng)過(guò)若干條邊能到達(dá)vj，稱頂點(diǎn)vi和vj是連通的，又稱頂點(diǎn)vi到vj有路徑。 對(duì)有向圖

8、G=(V，E)，從頂點(diǎn)vi到vj有有向路徑，指的是從頂點(diǎn)vi經(jīng)過(guò)若干條有向邊(弧)能到達(dá)vj。在一條路徑中，若沒(méi)有重復(fù)相同的頂點(diǎn)，該路徑稱為簡(jiǎn)單路徑；第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路(環(huán))；在一個(gè)回路中，若除第一個(gè)與最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路(簡(jiǎn)單環(huán))。如果G是有向圖，則路徑也是有向的。下圖用紅線列舉頂點(diǎn)B到頂點(diǎn)D的兩種路徑，而頂點(diǎn)A到頂點(diǎn)B就不存在路徑。路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。路徑的長(zhǎng)度是路徑上的邊或弧的數(shù)目。第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)第一個(gè)頂點(diǎn)到最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)(Cycle)。右圖用紅線列舉了從頂點(diǎn)右圖用紅

9、線列舉了從頂點(diǎn)B到頂?shù)巾旤c(diǎn)點(diǎn)D的四種不同路徑：的四種不同路徑：連通圖 在無(wú)向圖G中，如果從頂點(diǎn)V1到頂點(diǎn)V2有路徑，則稱V1和V2是連通的，如果對(duì)于圖中任意兩個(gè)頂點(diǎn)Vi和Vj都是連通的，則稱G是連通圖(ConnectedGraph)下圖左側(cè)不是連通圖，右側(cè)是連通圖：無(wú)向圖中的極大連通子圖稱為連通分量。無(wú)向圖中的極大連通子圖稱為連通分量。注意以下概念：注意以下概念：首先要是子圖，并且子圖是要連通的；首先要是子圖，并且子圖是要連通的；連通子圖含有極大頂點(diǎn)數(shù)；連通子圖含有極大頂點(diǎn)數(shù)；“極大極大”的含義：指的是對(duì)子的含義：指的是對(duì)子圖再增加圖圖再增加圖G中的其它頂點(diǎn)，子圖就不再連通。中的其它頂點(diǎn)，子圖

10、就不再連通。具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊。具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊。在有向圖G中，如果對(duì)于每一對(duì)Vi到Vj都存在路徑，則稱G是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量。下圖左側(cè)并不是強(qiáng)連通圖，右側(cè)是。并且右側(cè)是左側(cè)的極下圖左側(cè)并不是強(qiáng)連通圖，右側(cè)是。并且右側(cè)是左側(cè)的極大強(qiáng)連通子圖，也是左側(cè)的強(qiáng)連通分量。大強(qiáng)連通子圖，也是左側(cè)的強(qiáng)連通分量。二、圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜，其復(fù)雜性主要表現(xiàn)在： 任意頂點(diǎn)之間可能存在聯(lián)系，無(wú)法以數(shù)據(jù)元素在存儲(chǔ)區(qū)中的物理位置來(lái)表示元素之間的關(guān)系。 圖中頂點(diǎn)的度不一樣，有的可能相差很大，若按度數(shù)最大的

11、頂點(diǎn)設(shè)計(jì)結(jié)構(gòu)，則會(huì)浪費(fèi)很多存儲(chǔ)單元，反之按每個(gè)頂點(diǎn)自己的度設(shè)計(jì)不同的結(jié)構(gòu)，又會(huì)影響操作。 圖的常用的存儲(chǔ)結(jié)構(gòu)有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表和邊表。 1.二維數(shù)組鄰接矩陣存儲(chǔ)基本思想：對(duì)于有n個(gè)頂點(diǎn)的圖，用一維數(shù)組vexsn存儲(chǔ)頂點(diǎn)信息，用二維數(shù)組Ann存儲(chǔ)頂點(diǎn)之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)，鄰接矩陣中的元素Aij存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息。定義int G101101;Gij的值，表示從點(diǎn)i到點(diǎn)j的邊的權(quán)值，定義如下：上圖中的3個(gè)圖對(duì)應(yīng)的鄰接矩陣分別如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0

12、 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 另外有向圖是有講究的，要考另外有向圖是有講究的，要考慮入度和出度，頂點(diǎn)慮入度和出度，頂點(diǎn)V1的入度的入度為為1，正好是第，正好是第V1列的各數(shù)之列的各數(shù)之和，頂點(diǎn)和，頂點(diǎn)V1的出度為的出度為2，正好，正好是第是第V1行的各數(shù)之和。行的各數(shù)之和。 下面是建立圖的鄰接矩陣的參考程序段：#include#includeusing namespace std;using namespace std;int i,j,k,e,n;int i,j,k,e,n;

13、double g101101;double g101101;double w;double w;int main()int main() int i,j; int i,j; for (i = 1; i = n; i+) for (i = 1; i = n; i+) for (j = 1; j = n; j+) for (j = 1; j e; cin e; for (k = 1; k = e; k+) for (k = 1; k i j w; cin i j w; /讀入兩個(gè)頂點(diǎn)序號(hào)及權(quán)值讀入兩個(gè)頂點(diǎn)序號(hào)及權(quán)值 gij = w; gij = w; /對(duì)于不帶權(quán)的圖對(duì)于不帶權(quán)的圖gij=1gij

14、=1 gji = w; gji = w; /無(wú)向圖的對(duì)稱性無(wú)向圖的對(duì)稱性, ,如果是有向圖則不要有這句！如果是有向圖則不要有這句！ return 0; return 0; 建立鄰接矩陣時(shí)，有兩個(gè)小技巧: 初始化數(shù)組大可不必使用兩重初始化數(shù)組大可不必使用兩重forfor循環(huán)。循環(huán)。 1) 1) 如果是如果是intint數(shù)組，采用數(shù)組，采用memset(g, 0 x7f, sizeof(g)memset(g, 0 x7f, sizeof(g)可可全部初始化為一個(gè)很大的數(shù)全部初始化為一個(gè)很大的數(shù)( (略小于略小于0 x7fffffff)0 x7fffffff)， 使用使用memset(g, 0, s

15、izeof(g)memset(g, 0, sizeof(g)，全部清為，全部清為0 0， 使用使用memset(g, 0 xaf, sizeof(g)memset(g, 0 xaf, sizeof(g)，全部初始化為一個(gè)很，全部初始化為一個(gè)很小的數(shù)。小的數(shù)。 2)2)如果是如果是doubledouble數(shù)組，采用數(shù)組，采用memset(g,127,sizeof(g);memset(g,127,sizeof(g);可可全部初始化為一個(gè)很大的數(shù)全部初始化為一個(gè)很大的數(shù)1.381.38* *1030610306， 使用使用memset(g, 0, sizeof(g)memset(g, 0, size

16、of(g)全部清為全部清為0.0.2.數(shù)組模擬鄰接表存儲(chǔ)數(shù)組模擬鄰接表存儲(chǔ)鄰接矩陣看上去是個(gè)不錯(cuò)的選擇，首先是容易理解，第二是索引和編排都很舒服鄰接矩陣看上去是個(gè)不錯(cuò)的選擇，首先是容易理解，第二是索引和編排都很舒服但是我們也發(fā)現(xiàn)，鄰接矩陣適合于結(jié)點(diǎn)數(shù)較少的稠密圖。如果用來(lái)表示稀疏圖，但是我們也發(fā)現(xiàn)，鄰接矩陣適合于結(jié)點(diǎn)數(shù)較少的稠密圖。如果用來(lái)表示稀疏圖，則會(huì)造成很大的空間浪費(fèi)。則會(huì)造成很大的空間浪費(fèi)。因此我們可以考慮另外一種存儲(chǔ)結(jié)構(gòu)方式，例如把數(shù)組與鏈表結(jié)合一起來(lái)存儲(chǔ)，因此我們可以考慮另外一種存儲(chǔ)結(jié)構(gòu)方式，例如把數(shù)組與鏈表結(jié)合一起來(lái)存儲(chǔ)，這種方式在圖結(jié)構(gòu)也適用，我們稱為鄰接表這種方式在圖結(jié)構(gòu)也適

17、用，我們稱為鄰接表(AdjacencyList)。 基本思想：基本思想：對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，存儲(chǔ)該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息。信息。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)。第第i個(gè)單鏈表表示依附于頂點(diǎn)個(gè)單鏈表表示依附于頂點(diǎn)Vi的邊的邊(對(duì)有向圖是以頂點(diǎn)對(duì)有向圖是以頂點(diǎn)Vi為頭或尾的弧為頭或尾的弧)。圖的鄰接表存儲(chǔ)法，又叫鏈?zhǔn)酱鎯?chǔ)法。本來(lái)是要用鏈表實(shí)現(xiàn)的，但大多數(shù)情況下圖的鄰接表存儲(chǔ)法，又叫鏈?zhǔn)酱鎯?chǔ)法。本來(lái)是要用鏈表實(shí)現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。只要用數(shù)組模擬即可。 鄰接表（有向圖） 鄰接表的處理

18、方法是這樣： 圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)，當(dāng)然，頂點(diǎn)也可以用單鏈表來(lái)存儲(chǔ)，不過(guò)數(shù)組可以較容易地讀取頂點(diǎn)信息，更加方便。 圖中每個(gè)頂點(diǎn)Vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，由于鄰接點(diǎn)的個(gè)數(shù)不確定，所以我們選擇用單鏈表來(lái)存儲(chǔ)。若是有向圖，鄰接若是有向圖，鄰接表結(jié)構(gòu)就是這樣定表結(jié)構(gòu)就是這樣定義的。義的。有向圖的鄰接表：我們先來(lái)看下把頂點(diǎn)當(dāng)弧尾建立的鄰接表，這樣很容易就可以得到每個(gè)頂點(diǎn)的出度： 但也有時(shí)為了便于確定頂點(diǎn)的入度或以頂點(diǎn)為弧頭的弧，我們可以建立一個(gè)有向圖但也有時(shí)為了便于確定頂點(diǎn)的入度或以頂點(diǎn)為弧頭的弧，我們可以建立一個(gè)有向圖的逆鄰接表：的逆鄰接表：此時(shí)我們很容易就可以算此時(shí)我們很容易就可以算出某

19、個(gè)頂點(diǎn)的入度或出度出某個(gè)頂點(diǎn)的入度或出度是多少，判斷兩頂點(diǎn)是否是多少，判斷兩頂點(diǎn)是否存在弧也很容易實(shí)現(xiàn)。存在弧也很容易實(shí)現(xiàn)。對(duì)于帶權(quán)值的網(wǎng)圖，可以在邊表結(jié)點(diǎn)定義中再對(duì)于帶權(quán)值的網(wǎng)圖，可以在邊表結(jié)點(diǎn)定義中再增加一個(gè)數(shù)據(jù)域來(lái)存儲(chǔ)權(quán)值即可：增加一個(gè)數(shù)據(jù)域來(lái)存儲(chǔ)權(quán)值即可：鄰接表（網(wǎng)）鄰接表（網(wǎng)）在進(jìn)行鄰接表的輸入時(shí)，可以直接使用鄰接表的定義方式直接輸入；在進(jìn)行鄰接表的輸入時(shí)，可以直接使用鄰接表的定義方式直接輸入；也可由別的輸入方式進(jìn)行演變，課本上的就是利用邊的頂點(diǎn)及其權(quán)值進(jìn)行輸入的也可由別的輸入方式進(jìn)行演變，課本上的就是利用邊的頂點(diǎn)及其權(quán)值進(jìn)行輸入的 以下是用數(shù)組模擬鄰接表存儲(chǔ)的參考程序段：const

20、 int N=maxn； / maxn表示圖中最大頂表示圖中最大頂點(diǎn)數(shù)點(diǎn)數(shù)const int E=maxe ； / maxe圖中最大邊數(shù)圖中最大邊數(shù)struct Edgeint u,v; /邊所鄰接的兩個(gè)頂點(diǎn)邊所鄰接的兩個(gè)頂點(diǎn)int w; /邊的權(quán)值邊的權(quán)值int next; /邊指針，指向下一條邊的內(nèi)存地址邊指針，指向下一條邊的內(nèi)存地址edgeE; / 靜態(tài)內(nèi)存，用于分配邊靜態(tài)內(nèi)存，用于分配邊int headN; / 表頭表頭int num; / 內(nèi)存的指針內(nèi)存的指針void init()for(int i=0;iE;i+) headi=-1; /這里為什么這里為什么要設(shè)為要設(shè)為-1num=

21、 0;void addedge(int b,int e,int w)edgenum.u=b;edgenum.v=e;edgenum.w=w;edgenum.next=headb;headb=num+;int main()num_edge=0;scanf(%d %d,&n,&m); /讀入點(diǎn)數(shù)和邊數(shù)for(int i=1;i=m;i+) scanf(%d %d %d,&a,&b,&x); /a、b之間有一條長(zhǎng)度為x的邊 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍歷從點(diǎn)1開(kāi)始的所有邊 /./.return 0;兩種方法各有用武之地，需

22、按具體情況，具體選用。課本上的程序段課本上的程序段#include using namespace std;const int maxn=1001,maxm=100001;struct Edgeint next; /下一條邊的編號(hào)下一條邊的編號(hào) int to; /這條邊到達(dá)的點(diǎn)這條邊到達(dá)的點(diǎn) int dis; /這條邊的長(zhǎng)度這條邊的長(zhǎng)度 edgemaxm;int headmaxn,num_edge,n,m,u,v,d;void add_edge(int from,int to,int dis) /加入一條從加入一條從from到到to距離為距離為dis的單向邊的單向邊 edge+num_edge

23、.next=headfrom;edgenum_edge.to=to;edgenum_edge.dis=dis;headfrom=num_edge;int main()for(int i=1;i=m;i+) scanf(%d %d %d,&a,&b,&x); /a、b之間有一條長(zhǎng)度為之間有一條長(zhǎng)度為x的邊的邊 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍歷從點(diǎn)遍歷從點(diǎn)1開(kāi)始的所有邊開(kāi)始的所有邊 【例題】求一個(gè)有向圖中指定頂點(diǎn)的出度【問(wèn)題描述】如題【文件輸入】第1行：2個(gè)空格分開(kāi)的整數(shù)n(2=n=200)和m(10=m=20000)，分

24、別表示圖的頂點(diǎn)數(shù)和邊數(shù)。第2.m+1行：每行2個(gè)空格分開(kāi)的整數(shù)i，j，i表示一條邊的起點(diǎn)，j表示終點(diǎn)。第m2行：1個(gè)整數(shù)k(2=k=n),表示指定的頂點(diǎn)?！疚募敵觥恐挥幸恍袨?個(gè)整數(shù)，表示頂點(diǎn)k的出度?！緲永斎搿?835454323544142244【樣例輸出】4【參考代碼】 【方法1】鄰接矩陣存儲(chǔ)圖 #include usingnamespacestd; inta201201,n,m,ans=0,x; voidinit() inti,j,k; cinnm; for(i=1;ijk;ajk=1; intmain() init(); cink; for(inti=1;i=n;i+)if(ak

25、i)ans+; coutansendl; 【方法2】鄰接表存儲(chǔ)圖#includeusing namespace std;struct Edge int to,next;w20005;int hMaxn=0,i,x,y,z,n,e,k,cnt,ans=0;void AddEdge(int x,int y) cnt+; wcnt.to=y; wcnt.next=hx; hx=cnt;int main() cinne;/讀入頂點(diǎn)數(shù)目和邊數(shù) for(i=1;ixy; AddEdge(x,y); /建圖 cink; for(int p=hk;p!=0;p=wp.next) ans+; coutansen

26、dl;第二節(jié) 圖的遍歷 一、深度優(yōu)先與廣度優(yōu)先遍歷 從圖中某一頂點(diǎn)出發(fā)系統(tǒng)地訪問(wèn)圖中所有頂點(diǎn)，使每個(gè)頂點(diǎn)恰好被訪問(wèn)一次，這種運(yùn)算操作被稱為圖的遍歷。為了避免重復(fù)訪問(wèn)某個(gè)頂點(diǎn)，可以設(shè)一個(gè)標(biāo)志數(shù)組visitedi，未訪問(wèn)時(shí)值為false，訪問(wèn)一次后就改為true。 圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時(shí)間效率都是O(n*n)。 1.深度優(yōu)先遍歷深度優(yōu)先搜索深度優(yōu)先搜索(Depth First Search-DFS)遍歷類似樹(shù)的先序遍歷，是樹(shù)遍歷類似樹(shù)的先序遍歷，是樹(shù)的先序遍歷的推廣。的先序遍歷的推廣。1 算法思想算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則：設(shè)初始狀態(tài)時(shí)圖中的所

27、有頂點(diǎn)未被訪問(wèn)，則： ：從圖中某個(gè)頂點(diǎn)：從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)出發(fā)，訪問(wèn)vi；然后找到；然后找到vi的一個(gè)鄰接頂點(diǎn)的一個(gè)鄰接頂點(diǎn)vi1 ；：從：從vi1出發(fā)，深度優(yōu)先搜索訪問(wèn)和出發(fā)，深度優(yōu)先搜索訪問(wèn)和vi1相鄰接且未被訪問(wèn)的所有頂相鄰接且未被訪問(wèn)的所有頂點(diǎn)；點(diǎn)；：轉(zhuǎn)：轉(zhuǎn) ，直到和，直到和vi相鄰接的所有頂點(diǎn)都被訪問(wèn)為止相鄰接的所有頂點(diǎn)都被訪問(wèn)為止 ：繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)：繼續(xù)選取圖中未被訪問(wèn)頂點(diǎn)vj作為起始頂點(diǎn)，轉(zhuǎn)作為起始頂點(diǎn)，轉(zhuǎn)(1)，直到圖中，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。所有頂點(diǎn)都被訪問(wèn)為止。例如對(duì)右邊的這個(gè)無(wú)向圖深度優(yōu)先遍歷，假定先從1出發(fā)程序以如下順序遍歷：125，然后退回

28、到2，退回到1。從1開(kāi)始再訪問(wèn)未被訪問(wèn)過(guò)的點(diǎn)3，3沒(méi)有未訪問(wèn)的鄰接點(diǎn)，退回1。再?gòu)?開(kāi)始訪問(wèn)未被訪問(wèn)過(guò)的點(diǎn)4，再退回1。起點(diǎn)1的所有鄰接點(diǎn)都已訪問(wèn)，遍歷結(jié)束。12345下面給出的深度優(yōu)先遍歷的參考程序，假設(shè)圖以鄰接表存儲(chǔ)voiddfs(inti)/圖用數(shù)組模擬鄰接表存儲(chǔ)，訪問(wèn)點(diǎn)ivisitedi=true;/標(biāo)記為已經(jīng)訪問(wèn)過(guò)for(intj=1;j=numi;j+)/遍歷與i相關(guān)聯(lián)的所有未訪問(wèn)過(guò)的頂點(diǎn)if(!visitedgij)dfs(gij);主程序如下:intmain()memset(visited,false,sizeof(visited);for(inti=1;i=n;i+)/每一個(gè)

29、點(diǎn)都作為起點(diǎn)嘗試訪問(wèn)，因?yàn)椴皇菑娜魏?一點(diǎn)開(kāi)始都能遍歷整個(gè)圖的，例如下面的兩個(gè)圖。if(!visitedi)dfs(i);return0;12345以3為起點(diǎn)根本不能遍歷整個(gè)圖這個(gè)非連通無(wú)向圖任何一個(gè)點(diǎn)為起點(diǎn)都不能遍歷整個(gè)圖14523廣度優(yōu)先搜索BFS廣度優(yōu)先搜索(Breadth First Search-BFS)遍歷類似樹(shù)的按層次遍歷的過(guò)程。1 算法思想 設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問(wèn)，則： ：從圖中某個(gè)頂點(diǎn)vi出發(fā)，訪問(wèn)vi；：訪問(wèn)vi的所有相鄰接且未被訪問(wèn)的所有頂點(diǎn)vi1，vi2，vim；：以vi1，vi2， ，vim的次序，以vij(1jm)依此作為vi ，轉(zhuǎn)； ：繼續(xù)選取圖中未被

30、訪問(wèn)頂點(diǎn)vk作為起始頂點(diǎn)，轉(zhuǎn)，直到圖中所有頂點(diǎn)都被訪問(wèn)為止。下圖是有向圖的廣度優(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 有向圖廣度優(yōu)先搜索遍歷有向圖廣度優(yōu)先搜索遍歷(a) 有向圖有向圖Gv1v2v3v4v5 用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點(diǎn)搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時(shí)間復(fù)雜度為O(n+e) 。 圖的遍歷可以系統(tǒng)地訪問(wèn)圖中的每個(gè)頂點(diǎn)，因此，圖的遍歷算法是圖的最基本、最重要的算

31、法，許多有關(guān)圖的操作都是在圖的遍歷基礎(chǔ)之上加以變化來(lái)實(shí)現(xiàn)的?！纠}】無(wú)向圖的BFS【問(wèn)題描述】一個(gè)無(wú)向圖，從指定頂點(diǎn)出發(fā)進(jìn)行BFS，求遍歷得到的頂點(diǎn)序?！疚募斎搿康?行：2個(gè)空格分開(kāi)的整數(shù)n(2=n=200)和m(10=m=20000)，分別表示圖的頂點(diǎn)數(shù)和邊數(shù)。第2.m+1行：每行2個(gè)空格分開(kāi)的整數(shù)i，j，i表示一條邊的起點(diǎn)，j表示終點(diǎn)。第m2行：1個(gè)整數(shù)k(1=k=n),表示指定的頂點(diǎn)?！疚募敵觥恐灰恍许旤c(diǎn)序。要求在同一層上，頂點(diǎn)序號(hào)從小到大輸出。#includeusing namespace std;int a101101,f101,q101,n,m,i,st;void init()

32、 int i,j,x,y; cinnm; memset(f,0,sizeof(f); for(i=1;ixy;axy=1;ayx=1; cinst;void dfs(int i)/深搜DFS int j; couti ;fi=1; for(j=1;j=n;j+)if(fj=0)&(aij=1)dfs(j);void bfs(int i)/廣搜BFS int j,k,open,closed; memset(q,0,sizeof(q); open=0;closed=1;q1=i;/i進(jìn)隊(duì)列 couti ; fi=1; /標(biāo)志 while(openclosed) /隊(duì)列不空 open+;k=qope

33、n; /出隊(duì) for(j=1;j=n;j+) if(akj=1)&(fj=0) coutj ; fj=1;closed+;qclosed=j; int main() init(); /dfs(st);coutendl;memset(f,0,sizeof(f); bfs(st);二、歐拉圖 1、歐拉路： 歐拉路徑：圖G中每條邊經(jīng)過(guò)一次且僅一次的路徑稱作歐拉路徑。如下圖中存在一條從頂點(diǎn)1到頂點(diǎn)6的歐拉路。一筆畫(huà)問(wèn)題其實(shí)本質(zhì)上就是判斷一個(gè)圖是否存在歐拉路。無(wú)向圖歐拉路存在的充要條件：圖是連通的；圖中有且僅有0個(gè)或2個(gè)度數(shù)為奇數(shù)的點(diǎn)。若存在2個(gè)奇點(diǎn)，則歐拉路一定是從一個(gè)奇點(diǎn)出發(fā)，以另一個(gè)奇點(diǎn)結(jié)束。 2

34、、歐拉回路：圖G中每條邊經(jīng)過(guò)一次且僅一次的回路稱作歐拉回路。著名的柯尼斯堡七橋問(wèn)題(圖論起源),本質(zhì)上就是討論一個(gè)圖的歐拉回路問(wèn)題。 一個(gè)無(wú)向圖有歐拉回路的必要條件是：一個(gè)無(wú)向圖有歐拉回路的必要條件是：圖是連通的；圖中所有點(diǎn)的度均為偶數(shù)。圖是連通的；圖中所有點(diǎn)的度均為偶數(shù)。 求歐拉路的算法很簡(jiǎn)單，使用深度優(yōu)先遍歷即可。 根據(jù)一筆畫(huà)的兩個(gè)定理，如果尋找歐拉回路，對(duì)任意一個(gè)點(diǎn)執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對(duì)一個(gè)奇點(diǎn)執(zhí)行DFS，時(shí)間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點(diǎn)數(shù)。 以下是尋找一個(gè)圖的歐拉路的算法實(shí)現(xiàn)： 樣例輸入:第一行n，m，有n個(gè)點(diǎn)，m條邊，以下m行描述每條邊連接的兩點(diǎn)。 55 12 2

35、3 34 45 51 樣例輸出:歐拉路或歐拉回路 154321【參考程序】Euler.cpp#include#includeusing namespace std;#define maxn 101int gmaxnmaxn; /此圖用鄰接矩陣存儲(chǔ)int dumaxn; /記錄每個(gè)點(diǎn)的度，就是相連的邊的數(shù)目int circuitmaxn; /用來(lái)記錄找到的歐拉路的路徑int n,e,circuitpos,i,j,x,y,start;void find_circuit(int i) /這個(gè)點(diǎn)深度優(yōu)先遍歷過(guò)程尋找歐拉路 int j; for (j = 1; j n e; for (i = 1; i

36、x y; gyx = gxy = 1; dux+; /統(tǒng)計(jì)每個(gè)點(diǎn)的度 duy+; start = 1; /如果有奇點(diǎn)，就從奇點(diǎn)開(kāi)始尋找，這樣找到的就是 for (i = 1; i = n; i+) /歐拉路。沒(méi)有奇點(diǎn)就從任意點(diǎn)開(kāi)始， if (dui%2 = 1) /這樣找到的就是歐拉回路。(因?yàn)槊恳粋€(gè)點(diǎn)都是偶點(diǎn)) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = circuitpos; i+) cout circuiti ; cout endl; return 0; 注意以上程序具有一定的局限性，對(duì)于下面這種情況它不

37、能很好地處理： 上圖具有多個(gè)歐拉回路，而本程序只能找到一個(gè)回路。讀者在遇到具體問(wèn)題時(shí)，還應(yīng)對(duì)程序作出相應(yīng)的修改。 三、哈密爾頓環(huán) 歐拉回路是指不重復(fù)地走過(guò)所有路徑的回路，而哈密爾頓環(huán)是指不重復(fù)地走過(guò)所有的點(diǎn)，并且最后還能回到起點(diǎn)的回路。 哈密頓通路（回路）與哈密頓圖（Hamilton圖）通過(guò)圖G的每個(gè)結(jié)點(diǎn)一次，且僅一次的通路（回路），就是哈密頓通路（回路）.存在哈密頓回路的圖就是哈密頓圖 美國(guó)圖論數(shù)學(xué)家?jiàn)W勒在1960年給出了一個(gè)圖是哈密爾頓圖的充分條件：對(duì)于頂點(diǎn)個(gè)數(shù)大于2的圖，如果圖中任意兩點(diǎn)度的和大于或等于頂點(diǎn)總數(shù)，那這個(gè)圖一定是哈密頓圖。閉合的哈密頓路徑稱作哈密頓圈，含有圖中所有頂點(diǎn)的路徑

38、稱作哈密頓路徑。 【例題1】哈密頓路問(wèn)題【問(wèn)題描述】郵遞員在送信時(shí)，為了節(jié)省路途，自己規(guī)定：每次總是從n個(gè)村子中選擇其中一個(gè)合適的村子出發(fā)，途經(jīng)每個(gè)村子僅且經(jīng)過(guò)一次，送完所有的信。 已知各個(gè)村子的道路連通情況。請(qǐng)你幫郵遞員選擇一條合適的路線。【文件輸入】第1行：整數(shù)n(2=n=200)：村子的個(gè)數(shù)。接下來(lái)是一個(gè)n*n的0、1矩陣（每2個(gè)數(shù)之間有1個(gè)空格），表示n個(gè)村子的連通情況，如：ai,j=1 ，表示第i和第j個(gè)村子之間有路可走，如果ai,j=0，表示他們之間無(wú)路可走。 【文件輸出】只有一行為1個(gè)整數(shù)表示可行的方案總數(shù)。 #include#include using namespace st

39、d;int a201201,visit201,found,n,sum;void init() int i,j; scanf(%d,&n); for(i=1;i=n;i+) for(j=1;j=n;j+)scanf(%d,&aij);void dfs(int i,int k) int j; if(k=n)found=1;sum+;return; for(j=1;j=n;j+) if(aij=1)&(visitj=0) visitj=1; dfs(j,k+1); visitj=0; intmain()inti;init();found=0;sum=0;for(i=1;i=n;i+)memset(v

40、isit,0,sizeof(visit);visiti=1;dfs(i,1);if(found=0)printf(%d,0);elseprintf(%d,sum);return0;使用簡(jiǎn)單的深度優(yōu)先搜索，就能求出一張圖中所有的哈密爾頓環(huán)。下面給出一段參考程序： #include #include usingnamespacestd; intstart,length,x,n; boolvisited101,v1101; intans101,num101; intg101101; voidprint() inti; for(i=1;i=length;i+) cout“”ansi; coutendl

41、; void dfs(int last,int i) void dfs(int last,int i) /圖用數(shù)組模擬鄰接表存儲(chǔ)，訪問(wèn)點(diǎn)圖用數(shù)組模擬鄰接表存儲(chǔ)，訪問(wèn)點(diǎn)i i，lastlast表表示上次訪問(wèn)的點(diǎn)示上次訪問(wèn)的點(diǎn) visitedi = true; visitedi = true; / /標(biāo)記為已經(jīng)訪問(wèn)過(guò)標(biāo)記為已經(jīng)訪問(wèn)過(guò) v1i = true; v1i = true; / /標(biāo)記為已在一張圖中出現(xiàn)過(guò)標(biāo)記為已在一張圖中出現(xiàn)過(guò) ans+length = i; ans+length = i; / /記錄下答案記錄下答案 for (int j = 1; j = numi; j+) for (int j = 1; j = numi; j+) if (gij=x&gij!=last) if (gij=x&gij!=last) / /回到起點(diǎn)，構(gòu)成哈密爾頓環(huán)回到起點(diǎn)，構(gòu)成哈密爾頓環(huán) ans+length = gij; ans+length = gij; print(); print(); / /這里說(shuō)明找到了一個(gè)環(huán)，則輸出這里說(shuō)明找到了一個(gè)環(huán)，則輸出ansans數(shù)組。數(shù)組。length-;length-;break;break; if (!visitedgij) dfs(i,gij); if (!visitedgij)