圖的概念、存儲(chǔ)、遍歷-v2014

2014/7/9圖的概念、存儲(chǔ)、遍歷一、圖的基本概念1.圖的定義：圖是由頂點(diǎn)的集合V和邊的集合E組成的二元組：G=（V，E）頂點(diǎn)集V={V1,V2,V3,V4,V5}邊集E={(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(4,5)}

2.無(wú)向圖和有向圖

⑴無(wú)向圖：在圖G=（V，E）中，如果任何邊都沒(méi)有方向性，則稱為無(wú)向圖。在無(wú)向圖中用不帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的頂點(diǎn)。常用小括號(hào)包圍的一對(duì)頂點(diǎn)表示一條無(wú)向邊。無(wú)向圖中任一條邊的兩個(gè)端點(diǎn)可以通過(guò)該邊相互到達(dá)。

V={V1,V2,V3,V4,V5}

E={(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)}2.無(wú)向圖和有向圖⑵有向圖：如果對(duì)于任意的a，b∈V，當(dāng)(a，b)∈E時(shí)，(b，a)∈E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。常用一對(duì)尖括號(hào)包圍的一對(duì)頂點(diǎn)表示一條有向邊。V={V1,V2,V3,V4}E={<V1,V2>,<V2,V4>,<V1,V3>,<V3,V4>,<V4,V1>}在有向圖中，邊<V1,V2>和<V2,V1>可同時(shí)存在。3.頂點(diǎn)的度無(wú)向圖頂點(diǎn)的度：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。有向圖：等于該頂點(diǎn)的入度與出度之和。

入度——以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和

出度——以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和

度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。

無(wú)向圖中，V1的度為3，V3的度為2有向圖中，V1的入度為1，出席為2思考題1.假設(shè)我們用d=(a1,a2,...,a5),表示無(wú)向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪組d值合理（）。

A）{5，4，4，3，1}B）{4，2，2，1，1}C）{3，3，3，2，2}D）{5，4，3，2，1}E）{2，2，2，2，2}2.無(wú)向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，則G至少_______個(gè)頂點(diǎn)。4.路徑和連通集在圖G=（V，E）中，如果對(duì)于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1……xk(k>1)⑴x1=a，xk=b⑵(xi，xi+1)∈Ei=1‥k-1則稱結(jié)點(diǎn)序列x1=a，x2，…，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條路徑，而路徑上邊的數(shù)目k-1（或者沿路徑各邊權(quán)值之和）稱為該路徑的長(zhǎng)度，并稱結(jié)點(diǎn)集合{x1，…，xk}為連通集。V1到V5有多條路徑，其中有：{v1,v2,v5}{v1,v3,v4,v5}{v1,v2,v3,v4,v5}5.簡(jiǎn)單路徑和回路如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。圖(a)中v1→v2→v3是一條簡(jiǎn)單路徑，v1→v3→v4→v1→v3不是簡(jiǎn)單路徑。x1=xk的簡(jiǎn)單路徑稱為回路（也稱為環(huán)）。例如圖(b)中，v1→v2→v1為一條回路。例157324G26例245136G1路徑：1，2，3，5，6，3路徑長(zhǎng)度：5簡(jiǎn)單路徑：1，2，3，5回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長(zhǎng)度：7簡(jiǎn)單路徑：1，2，5，7，6回路：1，2，3，1二、圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接矩陣表示法鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n1(或權(quán)值)

表示頂點(diǎn)i和頂點(diǎn)j有邊(或表示i和j的路徑長(zhǎng)度)A[i][j]=

0（或∞）表示頂點(diǎn)i和頂點(diǎn)j無(wú)邊二維數(shù)組的行、列號(hào)表示頂點(diǎn)編號(hào)上圖中的圖G1和圖G2對(duì)應(yīng)的相鄰矩陣分別為：無(wú)向帶權(quán)圖的鄰接(代價(jià))矩陣表示有向無(wú)權(quán)圖的鄰接矩陣表示鄰接矩陣的特點(diǎn)無(wú)向圖的鄰接矩陣是對(duì)稱的，而有向圖則不是。鄰接矩陣方便度數(shù)的計(jì)算。用鄰接矩陣表示圖:容易判定任意兩個(gè)結(jié)點(diǎn)之間是否有邊相連，O(1)容易求得各個(gè)結(jié)點(diǎn)的度數(shù)對(duì)于無(wú)權(quán)無(wú)向圖的鄰接矩陣，第i行元素值的和就是Vi的度數(shù)，O(n)對(duì)于無(wú)權(quán)有向圖的鄰接矩陣，第i行元素值的和就是Vi的出度，O(n)。第i列元素值的和就是Vi的入度，O(n)。對(duì)于有權(quán)無(wú)向圖的鄰接矩陣，第i行（或第i列）中元素值不為0的元素個(gè)數(shù)就是Vi的度數(shù)，O(n)；對(duì)于有權(quán)有向圖的鄰接矩陣，第i行中元素值不為0的元素個(gè)數(shù)就是Vi的出度，O(n)。第i列元素值<>0的元素個(gè)數(shù)就是Vi的入度，O(n)。各頂點(diǎn)的度是多少？1452375318642úúúúúúú?ùêêêêêêê?é0618360240120078400530750讀入數(shù)據(jù)構(gòu)造鄰接矩陣競(jìng)賽題中圖的數(shù)據(jù)是以這種方式給出的：題中會(huì)指定頂點(diǎn)數(shù)的最大值，以便于定義一個(gè)全局二維數(shù)組作為鄰接矩陣數(shù)據(jù)文件的第1行一般是圖的頂點(diǎn)個(gè)數(shù)N以及邊數(shù)M接下來(lái)一般有M行，每行有2個(gè)或3個(gè)整數(shù)，描述了每條邊的信息：如果是2個(gè)整數(shù)i，j，則一般表示頂點(diǎn)i和頂點(diǎn)j有一條邊相連如果是3個(gè)整數(shù)i，j，k，則一般表示頂點(diǎn)i和頂點(diǎn)j相連的權(quán)值為k針對(duì)圖數(shù)據(jù)的這種結(jié)構(gòu)，我們會(huì)用如下的代碼來(lái)構(gòu)造鄰接矩陣#defineMAXN200//最大頂點(diǎn)數(shù)inta[MAXN+10][MAXN+10],n,m,i,j,k,x;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){//讀入m條邊

scanf("%d%d",&j,&k); a[j][k]=1;//若是有向圖，則只賦值a[j][k] a[k][j]=1;//若是無(wú)向圖，則一定要賦值a[k][j]}如果是構(gòu)造帶權(quán)圖，則上述for語(yǔ)句中的代碼改為：

scanf("%d%d",&j,&k,&x); a[j][k]=x;//若是有向圖，則只賦值a[j][k] a[k][jl=x;//若是無(wú)向圖，則一定要賦值a[k][j]鄰接矩陣主對(duì)角線元素的處理在競(jìng)賽中很少有題的數(shù)據(jù)是頂點(diǎn)帶自環(huán)邊的，因此鄰接矩陣的主對(duì)角線元素a[i][i](1<=i<=n)一般都是0。在前面講的鄰接矩陣的構(gòu)造方法中，如果頂點(diǎn)i，j之間沒(méi)有邊，則a[i][j]也表示為0。在大多數(shù)圖的算法中，不區(qū)別這兩種值為0的情況是可以的。鄰接矩陣一般是全局?jǐn)?shù)組，初始默認(rèn)值均為0，所以一般不用特別處理主對(duì)角線元素。而在某些圖算法中，必須要區(qū)別主對(duì)角線元素和其它非主對(duì)角線元素，這時(shí)就用另外的特殊值來(lái)表示無(wú)邊相連的情況。特殊值一般取一個(gè)很大的正數(shù)（或負(fù)數(shù)），實(shí)現(xiàn)實(shí)現(xiàn)代碼如下：主對(duì)角線元素設(shè)為無(wú)窮大constintINF=99999999;//表示無(wú)窮大for(i=1;i<=n;i++)//初始化a[i][i]=INF;for(i=1;i<=m;i++){//讀入邊數(shù)據(jù)

scanf("%d%d%d",&j,&k,&x); a[j][k]=x; a[k][j]=x;//無(wú)向圖要這句，有向圖不要}鄰接矩陣的時(shí)間、空間分析：判斷i，j有無(wú)邊相連：O(1)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(n)空間復(fù)雜性高：O(n^2)邊集數(shù)組表示法用一個(gè)一維的結(jié)構(gòu)體數(shù)組存儲(chǔ)圖每個(gè)元素表示一條邊：起點(diǎn)、終點(diǎn)、權(quán)值（如果有的話）對(duì)數(shù)組按起點(diǎn)為關(guān)鍵字排序后，則一個(gè)結(jié)點(diǎn)的相鄰邊聚在一起，可以連續(xù)訪問(wèn)。適用于：對(duì)邊進(jìn)行依次處理的算法，適合存儲(chǔ)頂點(diǎn)多但邊很少的稀疏圖缺點(diǎn)：判斷i，j有無(wú)邊相連：O(e)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(e)，預(yù)處理后復(fù)雜度降低。優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單邊集數(shù)組表示法的實(shí)現(xiàn)#defineMAXEDGE2000structnode{ intu,v;//邊的起點(diǎn)和終點(diǎn)

intwt;//邊的權(quán)值};nodeedge[MAXEDGE+10];intn,m,i,j,k,x;scanf("%d%d",&n,&m);for(i=1;i<=m;i++){ scanf("%d%d%d",&j,&k,&x); edge[i].u=j; edge[i].v=k; edge[i].wt=x;}鄰接表表示法鄰接表表示法是對(duì)圖中的每個(gè)頂點(diǎn)Vi(1<=i<=n)，把和它直接相連的邊串起來(lái)，建成一個(gè)單鏈表，并把所有頂點(diǎn)的表頭指針用一維數(shù)組存儲(chǔ)起來(lái)的一種表示方法。每個(gè)頂點(diǎn)Vi建立的單鏈表，記錄了與Vi相鄰的所有頂點(diǎn)，不含多余的頂點(diǎn)。每個(gè)頂點(diǎn)Vi建立的單鏈表，記錄了以該頂點(diǎn)為一個(gè)端點(diǎn)的所有邊的信息。以下圖為例，頂點(diǎn)v1與v2、v3、v5相鄰，因此在v1的單鏈表里就包含3條邊的信息。v1v2v3v4v5524101183253853^頂點(diǎn)v1的單鏈表有3個(gè)結(jié)點(diǎn)，表示有3條邊與v1相接，有3個(gè)頂點(diǎn)（v2、v3、v5）是v1的鄰接點(diǎn)不表示v2與v3相鄰，v3與v5相鄰鄰接表表示法一維指針數(shù)組存儲(chǔ)了每個(gè)頂點(diǎn)的單鏈表的頭指針。一般就用數(shù)組下標(biāo)表示了頂點(diǎn)編號(hào)。例如v1單鏈表的頭指針就存儲(chǔ)在adj[1]中。下圖的完整鄰接表如下所示：v1v2v3v4v5524101183253853^153256^182254^310511^1326511^4103412345鄰接表的數(shù)據(jù)結(jié)構(gòu)#defineMAXN200//最大頂點(diǎn)數(shù)structnode{intv; //鄰接點(diǎn)編號(hào)

intwt;//權(quán)值，如果是帶權(quán)圖的話

node*next;//鄰接單鏈表指針};node*adj[MAXN+10];/每個(gè)頂點(diǎn)建一個(gè)單鏈表構(gòu)造鄰接表intn,m;//n表示讀入的頂點(diǎn)個(gè)數(shù)，m表示讀入的邊條數(shù)創(chuàng)建鄰接表voidaddedge(intu,intv,intwt) { node*p; p=newnode; //申請(qǐng)一個(gè)結(jié)點(diǎn)

p->v=v; p->wt=wt; p->next=adj[u];adj[u]=p; //前插結(jié)點(diǎn)}voidinit()//創(chuàng)建鄰接表{inti,j,k,x;node*p;scanf("%d%d",&n,&m);//讀入頂點(diǎn)數(shù)和邊數(shù)

for(i=1;i<=n;i++)adj[i]=NULL;//初始化每個(gè)頂點(diǎn)的邊表為NULLfor(i=1;i<=m;i++){

//讀入邊信息，構(gòu)造鄰接表

scanf("%d%d%d",&j,&k,&x);//讀入一條邊的起點(diǎn)，終點(diǎn)和權(quán)值addedge(j,k,x);addedge(k,j,x); //無(wú)向圖要加這條語(yǔ)句}}鄰接表的優(yōu)缺點(diǎn)便于查找后繼頂點(diǎn)、以該點(diǎn)為起點(diǎn)的邊、出度。不便于查找前趨頂點(diǎn)、以該點(diǎn)為終點(diǎn)的邊、入度。解決辦法：建立逆鄰接表，即把以某頂點(diǎn)為終點(diǎn)的頂點(diǎn)放在一個(gè)單鏈表中和鄰接矩陣相比，構(gòu)造鄰接表的編程復(fù)雜性要高一些，但是查找后繼頂點(diǎn)的效率要高。如果邊比較稀疏，顯然用鄰接表存儲(chǔ)圖比較好。鄰接表是圖論題目首選的存儲(chǔ)方式。一種更快的鄰接表實(shí)現(xiàn)在之前的鄰接表實(shí)現(xiàn)中，每次添加新邊時(shí)都要調(diào)用new運(yùn)算符申請(qǐng)新的空間。頻繁調(diào)用new運(yùn)算導(dǎo)致時(shí)間效率低下。常用的解決之道是用“結(jié)構(gòu)體數(shù)組+指針”的方式來(lái)模擬申請(qǐng)新空間的操作。具體實(shí)現(xiàn)非常簡(jiǎn)單，所作的改變有：定義一個(gè)全局的結(jié)構(gòu)體數(shù)組nodeedge[MAXM]，node類型與之前相同，MAXM為最大的邊數(shù)(無(wú)向圖*2)定義一個(gè)全局指針變量cnt，初值為&edge[0]。每次分配新空間前，令++cnt，再返回新的cnt的值作為存儲(chǔ)新結(jié)點(diǎn)的地址。作為新手，建議像LRJ教材P105所示的方法，把申請(qǐng)新空間單獨(dú)寫(xiě)成一個(gè)函數(shù)。在之前代碼上所作的改動(dòng)#defineMAXM=10000 nodeedge[MAXM+10];node*cnt=&edge[0];inlinenode*newnode()//這個(gè)函數(shù)最好加上inline{node*p=++cnt;returnp;}voidaddedge(intu,intv,intwt){ node*p=newnode();//這個(gè)函數(shù)只改了這一點(diǎn) p->v=v; p->wt=wt; p->next=adj[u];adj[u]=p;}三、圖的遍歷給出一個(gè)圖G和其中任意一個(gè)結(jié)點(diǎn)V，從V出發(fā)訪問(wèn)G中所有結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)被訪問(wèn)一次（不是只經(jīng)過(guò)一次），這就叫圖的遍歷。通常有兩種遍歷方法：⑴深度優(yōu)先遍歷DFS⑵寬度優(yōu)先遍歷BFS1.深度優(yōu)先遍歷DFS方法：從圖的某一頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)；然后依次從V的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止。為了避免重復(fù)訪問(wèn)某個(gè)頂點(diǎn)，設(shè)一個(gè)標(biāo)志數(shù)組visit，頂點(diǎn)i未訪問(wèn)時(shí)，visit[i]的值為false，訪問(wèn)后就改為true。V1V2V4V5V3V7V6V8例V1開(kāi)始的一種DFS序：V1V2V4V8V5V3V6V7從V1開(kāi)始的DFS序不唯一，有許多種可以從任一頂點(diǎn)開(kāi)始進(jìn)行DFS練習(xí)：無(wú)向圖與有向圖的DFS例V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8例分別找出從V1，V5開(kāi)始的一種DFS序列V1開(kāi)始：V1V2V4V8V5V6V3V7V5開(kāi)始：V5V2V1V3V6V8V4V7V1開(kāi)始：V1V2V4V8V3V6V7V5V5開(kāi)始：V5V2V4V8V1V3V6V7由于選擇鄰接點(diǎn)的順序不同，從同一頂點(diǎn)開(kāi)始的DFS序也會(huì)不同。深度優(yōu)先遍歷的實(shí)現(xiàn)圖可用鄰接矩陣或者鄰接表存儲(chǔ)算法過(guò)程利用遞歸實(shí)現(xiàn)為防止頂點(diǎn)被多次訪問(wèn)，設(shè)置一個(gè)visit[MAXN]數(shù)組，初值為false，將每個(gè)訪問(wèn)過(guò)的頂點(diǎn)設(shè)為true。在選擇要遍歷的下一個(gè)頂點(diǎn)時(shí)，要同時(shí)檢查新頂點(diǎn)是否未被訪問(wèn)過(guò)。如果從當(dāng)前訪問(wèn)點(diǎn)x可經(jīng)過(guò)一條邊到達(dá)頂點(diǎn)y，并且y未訪問(wèn)，則可遞歸地對(duì)y進(jìn)行DFS。此時(shí)，稱邊(x,y)為樹(shù)邊，并且稱x是y的父親。對(duì)圖DFS后，所有的樹(shù)邊形成一棵深度優(yōu)先遍歷樹(shù)(或森林)。abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg訪問(wèn)標(biāo)志:訪問(wèn)次序:例如:achdkfe//從頂點(diǎn)i出發(fā)進(jìn)行深度優(yōu)先搜索,鄰接表實(shí)現(xiàn)//適用于有向圖和無(wú)向圖voiddfs(inti){printf("%d",i);//輸出，最簡(jiǎn)單的訪問(wèn)

visit[i]=true;//置訪問(wèn)標(biāo)志

for(node*p=adj[i];p!=NULL;p=p->next)//依次對(duì)i的鄰接點(diǎn)進(jìn)行DFS{intj;j=p->v;if(visit[j]==false)//如果鄰接點(diǎn)未訪問(wèn)

{ father[j]=i; //j的父親是i dfs(j); //則對(duì)其遞歸DFS}}}對(duì)圖進(jìn)行深度優(yōu)先遍歷如果圖不連通，則一次DFS只能訪問(wèn)所有與起始點(diǎn)V連通的頂點(diǎn)。要對(duì)整個(gè)圖進(jìn)行遍歷，則需要再任找一個(gè)尚未訪問(wèn)的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問(wèn)為止。voiddfstravel()//對(duì)圖進(jìn)行深度優(yōu)先遍歷{inti;memset(visit,0,sizeof(visit));//清訪問(wèn)標(biāo)志

for(i=1;i<=n;i++)if(!visit[i])dfs(i);}深度優(yōu)先遍歷的時(shí)間分析若采用鄰接矩陣存儲(chǔ)圖，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)時(shí)要花O(n)的時(shí)間，總共要對(duì)n個(gè)頂點(diǎn)進(jìn)行訪問(wèn)，所以總的時(shí)間為O(n^2)。若采用鄰接表存儲(chǔ)圖，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)花費(fèi)的時(shí)間不固定，有的多，有的少。但從總體看，每條邊只會(huì)被查看一次，每個(gè)頂點(diǎn)只會(huì)被訪問(wèn)一次，因此總時(shí)間O(n+e)。對(duì)于稠密圖，e≈n^2，因此采用鄰接表的性能相當(dāng)于采用鄰接矩陣。對(duì)于稀疏圖，e≈n，因此采用鄰接表的性能好于采用鄰接矩陣。一般來(lái)講，采用鄰接表存儲(chǔ)圖的DFS效率總會(huì)高于采用鄰接矩陣。因此，首選鄰接表存儲(chǔ)圖。例1哈密頓路[問(wèn)題描述]郵遞員在送信時(shí)，為了節(jié)省路途，自己規(guī)定：每次總是從n個(gè)村子中選擇其中一個(gè)合適的村子出發(fā)，途經(jīng)每個(gè)村子僅且經(jīng)過(guò)一次，送完所有的信。已知各個(gè)村子的道路連通情況。請(qǐng)你幫郵遞員選擇一條合適的路線。[輸入格式]第1行：1個(gè)整數(shù)n(2<=n<=200)：村子的個(gè)數(shù)。接下來(lái)是一個(gè)n*n的0、1矩陣，表示n個(gè)村子的連通情況[輸出格式]第1行：一條可行的路線[輸入樣例]7

0101100

1010100

0100001

1000000

1100010

0000101

0010010[輸出樣例]23765141235467分析題目的限制條件：“途經(jīng)每個(gè)村子僅且經(jīng)過(guò)一次”，表明在深搜的過(guò)程中，Vi的鄰接點(diǎn)中必須要有至少一個(gè)頂點(diǎn)是沒(méi)有被訪問(wèn)過(guò)的。這樣才能沿著該點(diǎn)繼續(xù)DFS下去。設(shè)置一個(gè)參數(shù)i表示當(dāng)前走到第幾個(gè)結(jié)點(diǎn)了，方便判斷邊界。如果恰能遍歷全部結(jié)點(diǎn)，則找到一條路徑，輸出這條路徑即可。怎樣在DFS的過(guò)程中保存路徑？用一個(gè)數(shù)組記錄每一步所選的結(jié)點(diǎn)。如果在DFS的某一步出現(xiàn)了所有鄰接點(diǎn)都被訪問(wèn)過(guò)了，則說(shuō)明在上一步所選的結(jié)點(diǎn)不正確，這時(shí)就要回溯到上層，換一個(gè)未被訪問(wèn)的結(jié)點(diǎn)，再次進(jìn)行DFS，看能否走通。在換結(jié)點(diǎn)的時(shí)候，一定要清除前一個(gè)結(jié)點(diǎn)被訪問(wèn)過(guò)的標(biāo)志信息，這就是所謂的“清理現(xiàn)場(chǎng)”的工作。voiddfs(intv,intdep)//深搜，查找一條哈密頓路{ if(dep==n){ for(intj=1;j<n;j++) printf("%d",path[j]); printf("%d\n",path[n]); exit(0);//找到一條路徑，直到終止程序

} for(node*p=adj[v];p!=NULL;p=p->next) if(!visit[p->v]){ visit[p->v]=true; path[dep+1]=p->v; dfs(p->v,dep+1); visit[p->v]=false;//清理現(xiàn)場(chǎng)

}}分析主函數(shù)中該如何調(diào)用dfs函數(shù)？本問(wèn)題的時(shí)間復(fù)雜度如何？就本題而言，由于只需要找出一條哈密頓路，若采用鄰接表，每條邊只訪問(wèn)一次，所以可認(rèn)為是O(n+m)。若采用鄰接矩陣，則是O(n^2)若要找出所有的可行的哈密頓路，程序該怎樣修改？若要找出所有的可行的哈密頓路，若采用鄰接表，則是O(n!)。若采用鄰接矩陣，則是O(n^n)，時(shí)間復(fù)雜度都非常高。例2黑白圖像[問(wèn)題描述]輸入一個(gè)n*n的黑白圖像(1表示黑色，0表示白色)，統(tǒng)計(jì)其中八連塊的個(gè)數(shù)。如果兩個(gè)黑格子有公共邊或者公共頂點(diǎn)，就說(shuō)它們屬于一個(gè)八連塊。[輸入格式]第1行：1個(gè)整數(shù)n(1<=n<=?)接下來(lái)n行，每行n個(gè)整數(shù)，描述一行[輸出格式]第1行:1個(gè)整數(shù)，表示八連塊的數(shù)量[樣例輸入]41100000000100001[樣例輸出]2分析二維平面是最常見(jiàn)的圖論模型之一。但平面圖與圖論所指的“圖”有時(shí)并不直接等同。為了適用圖論算法，常要把平面圖進(jìn)行重新建模。本題中，一個(gè)格子對(duì)應(yīng)于圖論“圖”的頂點(diǎn)，而邊則隱含地表示為八個(gè)方向的相鄰關(guān)系。只要八個(gè)方向的相鄰格子位置合法，就是當(dāng)前頂點(diǎn)的鄰接點(diǎn)。依次枚舉并檢驗(yàn)鄰接點(diǎn)的合法性，然后遞歸深度遍歷。為了確定每個(gè)頂點(diǎn)只訪問(wèn)一次，需要開(kāi)一個(gè)n*n的visit數(shù)組來(lái)打訪問(wèn)標(biāo)記。為了方便判斷格子是否“出界”，在迷宮的外面加上一圈虛擬的白格子，即所謂“砌墻”。有時(shí)，分析輸入數(shù)據(jù)的特點(diǎn)會(huì)發(fā)現(xiàn)，砌墻不需要額外寫(xiě)代碼。對(duì)本題，把存儲(chǔ)圖的二維數(shù)組清0，就相當(dāng)于砌墻了。需要另外用鄰接表或者鄰接矩陣來(lái)存儲(chǔ)圖嗎？就本題而言，不需要。因?yàn)猷徑狱c(diǎn)分布有規(guī)律，可以很容易按統(tǒng)一的規(guī)則枚舉鄰接點(diǎn)。建一個(gè)有8個(gè)方向的方向數(shù)組即可枚舉當(dāng)前格子的所有相鄰格子。如果另用鄰接表或鄰接矩陣存儲(chǔ)圖，不但增加額外的存儲(chǔ)空間和運(yùn)行時(shí)間，也浪費(fèi)編碼時(shí)間。而絲毫不能降低圖遍歷的時(shí)間。測(cè)試數(shù)據(jù)的生成手工生成小規(guī)模數(shù)據(jù)，包含各種規(guī)律的數(shù)據(jù)，確保程序?qū)π∫?guī)模數(shù)據(jù)的正確性根據(jù)時(shí)間限制估計(jì)數(shù)據(jù)規(guī)模的上限根據(jù)空間限制估計(jì)數(shù)據(jù)規(guī)模的上限隨機(jī)生成大規(guī)模數(shù)據(jù)，驗(yàn)證算法的時(shí)間效率#include<ctime>//time()頭文件#include<cstdlib>//srand(),rand()頭文件intGetRand(intL,intR){returnrand()*rand()%(R-L+1)+L;}intmain(){srand(time(NULL));intn=5;//n=5,10,20,100,500,1000for(inti=1;i<=n;i++)for(intj=1;j<=n;j++)printf("%d",GetRand(0,1));}例3犯罪團(tuán)伙[問(wèn)題描述]警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過(guò)警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)。有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n。[輸入格式]第1行：n（<=5000,罪犯數(shù)量），m（<50000，關(guān)系數(shù)量）以下m行：每行兩個(gè)數(shù)：i和j，中間一個(gè)空格隔開(kāi)，表示罪犯i和罪犯j相互認(rèn)識(shí)。[輸出格式]第1行：一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。[樣例輸入]118124354135671051089[樣例輸出]3分析把人處理成頂點(diǎn)，把認(rèn)識(shí)關(guān)系處理成邊，犯罪團(tuán)伙構(gòu)成一個(gè)圖（有向還是無(wú)向？）則根據(jù)輸入數(shù)據(jù)可以構(gòu)造一個(gè)鄰接表（可以用鄰接矩陣嗎？如果不能請(qǐng)說(shuō)明原因）。從1到n枚舉頂點(diǎn)Vi，從Vi進(jìn)行DFS，則能找到一個(gè)團(tuán)伙。然后再另選一個(gè)未訪問(wèn)的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問(wèn)。最后，調(diào)用DFS的次數(shù)就是團(tuán)伙的個(gè)數(shù)。寬度優(yōu)先遍歷BFS寬度優(yōu)先遍歷是按層次方式遍歷圖的過(guò)程，其步驟如下：從圖的某一頂點(diǎn)V出發(fā)，訪問(wèn)此頂點(diǎn)后，依次訪問(wèn)V的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)；然后再分別從這些鄰接點(diǎn)出發(fā)，寬度優(yōu)先遍歷圖，直至圖中所有與V連通的頂點(diǎn)被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選一個(gè)未被訪問(wèn)的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)為止。V1V2V4V5V3V7V6V8例一個(gè)可行的BFS順序：V1V2V3V4V5V6V7V8有向圖的BFSV1V2V4V5V3V7V6V8例一個(gè)可行的BFS順序：V1V2V3V4V6V7V8V5寬度優(yōu)先遍歷的實(shí)現(xiàn)與隱式圖的搜索樣，在實(shí)現(xiàn)圖的寬度優(yōu)先遍歷時(shí)，需要借助一個(gè)隊(duì)列，來(lái)“先入先出”地層次化訪問(wèn)圖中的結(jié)點(diǎn)。為了讓隊(duì)首結(jié)點(diǎn)能方便地找到鄰接點(diǎn)，在隊(duì)列里存放結(jié)點(diǎn)的指針比較好。使用STL的queue類模板可以節(jié)省編碼量，也不用擔(dān)心隊(duì)列空間不足，推薦使用。由于圖的結(jié)點(diǎn)之間的連邊是網(wǎng)狀關(guān)系，所以從后代結(jié)點(diǎn)可能有邊連到祖先結(jié)點(diǎn)。這樣，在圖的BFS中，必須要處理“判重”問(wèn)題。對(duì)顯式圖，頂點(diǎn)用整數(shù)編號(hào)，一般用visit數(shù)組即可以判重。而對(duì)隱式圖，頂點(diǎn)的狀態(tài)可能對(duì)應(yīng)多個(gè)變量，一般要用HASH表判重。為避免重復(fù)記錄狀態(tài)（隊(duì)列中肯定記錄著狀態(tài)），HASH表只記錄狀態(tài)在隊(duì)列中的下標(biāo)。此時(shí)用STL的queue就不行了，因?yàn)樗鼰o(wú)法以下標(biāo)方式直接訪問(wèn)隊(duì)列，而需要改用數(shù)組來(lái)模擬隊(duì)列操作。隊(duì)首元素x生成的新結(jié)點(diǎn)y檢驗(yàn)“合格”后，插入隊(duì)尾。此時(shí)x可認(rèn)為是y的父親，即father[y]=x。BFS完成后，結(jié)點(diǎn)間構(gòu)成一棵BFS樹(shù)（或者BFS森林）。例4走迷宮[問(wèn)題描述]一個(gè)網(wǎng)格迷宮由n行m列的單