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

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

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

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

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

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

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

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

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

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

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

11、頂點設(shè)計結(jié)構(gòu)，則會浪費很多存儲單元，反之按每個頂點自己的度設(shè)計不同的結(jié)構(gòu)，又會影響操作。 圖的常用的存儲結(jié)構(gòu)有：鄰接矩陣、鄰接鏈表、十字鏈表、鄰接多重表和邊表。 1.二維數(shù)組鄰接矩陣存儲基本思想：對于有n個頂點的圖，用一維數(shù)組vexsn存儲頂點信息，用二維數(shù)組Ann存儲頂點之間關(guān)系的信息。該二維數(shù)組稱為鄰接矩陣。在鄰接矩陣中，以頂點在vexs數(shù)組中的下標(biāo)代表頂點，鄰接矩陣中的元素Aij存放的是頂點i到頂點j之間關(guān)系的信息。定義int G101101;Gij的值，表示從點i到點j的邊的權(quán)值，定義如下：上圖中的3個圖對應(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 另外有向圖是有講究的，要考另外有向圖是有講究的，要考慮入度和出度，頂點慮入度和出度，頂點V1的入度的入度為為1，正好是第，正好是第V1列的各數(shù)之列的各數(shù)之和，頂點和，頂點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; /讀入兩個頂點序號及權(quán)值讀入兩個頂點序號及權(quán)值 gij = w; / gij = w; /對于不帶權(quán)的圖對于不帶權(quán)的圖gij=

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

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

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

17、在圖結(jié)構(gòu)也適用，我們稱為鄰接表(AdjacencyList)。 基本思想：基本思想：對圖的每個頂點建立一個單鏈表，存儲該頂點所有鄰接頂點及其相關(guān)對圖的每個頂點建立一個單鏈表，存儲該頂點所有鄰接頂點及其相關(guān)信息。信息。每一個單鏈表設(shè)一個表頭結(jié)點。每一個單鏈表設(shè)一個表頭結(jié)點。第第i個單鏈表表示依附于頂點個單鏈表表示依附于頂點Vi的邊的邊(對有向圖是以頂點對有向圖是以頂點Vi為頭或尾的弧為頭或尾的弧)。圖的鄰接表存儲法，又叫鏈?zhǔn)酱鎯Ψā１緛硎且面湵韺崿F(xiàn)的，但大多數(shù)情況下圖的鄰接表存儲法，又叫鏈?zhǔn)酱鎯Ψ?。本來是要用鏈表實現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。只要用數(shù)組模擬即可。 鄰接表（有向圖）

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

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

20、：const int N=maxn； / maxn表示圖中最大頂表示圖中最大頂點數(shù)點數(shù)const int E=maxe ； / maxe圖中最大邊數(shù)圖中最大邊數(shù)struct Edgeint u,v; /邊所鄰接的兩個頂點邊所鄰接的兩個頂點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è)為

21、-1num= 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); /讀入點數(shù)和邊數(shù)for(int i=1;i=m;i+) scanf(%d %d %d,&a,&b,&x); /a、b之間有一條長度為x的邊 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍歷從點1開始的所有邊 /./.return 0;兩種方法各有

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

23、m_edge.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之間有一條長度為之間有一條長度為x的邊的邊 add_edge(a,b,x);for(int i=head1;i!=0;i=edgei.next) /遍歷從點遍歷從點1開始的所有邊開始的所有邊 【例題】求一個有向圖中指定頂點的出度【問題描述】如題【文件輸入】第1行：2個空格分開的整數(shù)n(2=n=200)和m(10=m=20

24、000)，分別表示圖的頂點數(shù)和邊數(shù)。第2.m+1行：每行2個空格分開的整數(shù)i，j，i表示一條邊的起點，j表示終點。第m2行：1個整數(shù)k(2=k=n),表示指定的頂點。【文件輸出】只有一行為1個整數(shù)，表示頂點k的出度。【樣例輸入】5835454323544142244【樣例輸出】4【參考代碼】 【方法1】鄰接矩陣存儲圖 #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+

25、)if(aki)ans+; coutansendl; 【方法2】鄰接表存儲圖#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;/讀入頂點數(shù)目和邊數(shù) for(i=1;ixy; AddEdge(x,y); /建圖 cink; for(int p=hk;p!=0;p=wp.next) ans+; cou

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

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

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

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

30、選取圖中未被訪問頂點vk作為起始頂點，轉(zhuǎ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ū)別是鄰接點搜索次序不同，因此，廣度優(yōu)先搜索算法遍歷圖的總時間復(fù)雜度為O(n+e) 。 圖的遍歷可以系統(tǒng)地訪問圖中的每個頂點，因此，圖的遍歷算法是圖的最基本

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

32、init() 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)隊列 couti ; fi=1; /標(biāo)志 while(openclosed) /隊列不空 open+;

33、k=qopen; /出隊 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)過一次且僅一次的路徑稱作歐拉路徑。如下圖中存在一條從頂點1到頂點6的歐拉路。一筆畫問題其實本質(zhì)上就是判斷一個圖是否存在歐拉路。無向圖歐拉路存在的充要條件：圖是連通的；圖中有且僅有0個或2個度數(shù)為奇數(shù)的點。若存在2個奇點，則歐拉路一定是從一個奇點出發(fā)，以另一個奇

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

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

36、 1; i x y; gyx = gxy = 1; dux+; /統(tǒng)計每個點的度 duy+; start = 1; /如果有奇點，就從奇點開始尋找，這樣找到的就是 for (i = 1; i = n; i+) /歐拉路。沒有奇點就從任意點開始， if (dui%2 = 1) /這樣找到的就是歐拉回路。(因為每一個點都是偶點) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = circuitpos; i+) cout circuiti ; cout endl; return 0; 注意以上程序具有一定的局限性，對于下面

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

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

39、ace std;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+)me

40、mset(visit,0,sizeof(visit);visiti=1;dfs(i,1);if(found=0)printf(%d,0);elseprintf(%d,sum);return0;使用簡單的深度優(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; co

41、utendl; void dfs(int last,int i) /void dfs(int last,int i) /圖用數(shù)組模擬鄰接表存儲，訪問點圖用數(shù)組模擬鄰接表存儲，訪問點i i，lastlast表表示上次訪問的點示上次訪問的點 visitedi = true; / visitedi = true; /標(biāo)記為已經(jīng)訪問過標(biāo)記為已經(jīng)訪問過 v1i = true; / v1i = true; /標(biāo)記為已在一張圖中出現(xiàn)過標(biāo)記為已在一張圖中出現(xiàn)過 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) /回到起點，構(gòu)成哈密爾頓環(huán)回到起點，構(gòu)成哈密爾頓環(huán) ans+length = gij; ans+length = gij; print(); / print(); /這里說明找到了一個環(huán)，則輸出這里說明找到了一個環(huán)，則輸出ansans數(shù)組。數(shù)組。length-;length-;break;break; if (!visitedgij) dfs(i,gij); / if (!visitedgij)