高中信息競賽-數(shù)據(jù)結(jié)構(gòu)-圖基本概念及搜索遍歷

圖的基本概念及遍歷高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第1頁!圖的運算

如果數(shù)據(jù)元素集合D中的各元素之間存在任意的前后件關(guān)系R,則此數(shù)據(jù)結(jié)構(gòu)G=(D,R)稱為圖。

奧林匹克信息學(xué)聯(lián)賽的許多試題,需要用圖來描述數(shù)據(jù)元素間的聯(lián)系,需要用圖的經(jīng)典算法來解題,例如:用結(jié)點代表城市,每條邊代表連接兩個城市間的公路,邊長的權(quán)表示公路長度。這種公路網(wǎng)的表現(xiàn)形式就是屬于圖的數(shù)據(jù)結(jié)構(gòu)。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第2頁!圖的基本概念圖的的定義

如果數(shù)據(jù)元素集合D中的各元素之間存在任意的前后件關(guān)系R，則此數(shù)據(jù)結(jié)構(gòu)G=（D，R）稱為圖。如果將數(shù)據(jù)元素抽象為結(jié)點，元素之間的前后件關(guān)系用邊表示，則圖亦可以表示為G=（V，E），其中V是結(jié)點的有窮（非空）集合，E為邊的集合。如果元素a是元素b的前件，這種前后件關(guān)系對應(yīng)的邊用(a，b)表示，即(a，b)∈E。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第3頁!⑵有向圖：如果對于任意的a,b∈V,當(dāng)(a,b)∈E時,(b,a)∈E未必成立，則稱此圖為有向圖。在有向圖中,通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點(方向由前件指向后件)。有向圖中一個結(jié)點的后件個數(shù)稱為該結(jié)點的出度,其前件個數(shù)稱為該結(jié)點的入度。有向圖結(jié)點1的出度和入度分別為1，結(jié)點1和結(jié)點1度都為2高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第4頁!簡單路徑和回路如果一條路徑上的結(jié)點除起點x1和終點xk可以相同外，其它結(jié)點均不相同，則稱此路徑為一條簡單路徑。x1=xk的簡單路徑稱為回路（也稱為環(huán)）。v1→v2→v3是一條簡單路徑，v1→v3→v4→v1→v3不是簡單路徑v1→v2→v1為一條回路高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第5頁!連通圖和最大連通子圖對于無向圖而言，若其中任兩個結(jié)點之間的連通，則稱該圖為連通圖。一個無向圖的連通分支定義為此圖的最大連通子圖。上圖所示的圖是連通的，它的最大連通子圖即為其本身。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第6頁!圖的存儲結(jié)構(gòu)圖的相鄰矩陣表示法相鄰矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若G=（V，E）是一個具有n個結(jié)點的圖，則G的相鄰矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n;a[n+1][n+1]1(或權(quán)值)

表示頂點i和頂點j有邊(i和j的路程)a[i][j]=

0表示頂點i和頂點j無邊

inta[maxn+1][maxn+1]；boolf[maxn+1]；{頂點的訪問標(biāo)志序列}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第7頁!相鄰矩陣的特點

⑴無向圖的相鄰矩陣是對稱的,而有向圖則不是。無向圖的相鄰矩陣a1[i][j]=a1[j][i](1≤I,j≤n)且對角線上的a[i][i]均為0（或±∝）。正因為如此，在實際存儲相鄰矩陣時只需存儲其上三角(或下三角)的元素。因此具有n個結(jié)點的無向圖，其相鄰矩陣的存儲容量可節(jié)約至n(n-1)/2。而有向圖的相鄰矩陣中a2[i][j]不一定與a2[j][i](1≤i，j≤n)相同，且圖中出現(xiàn)自反邊時其對角線上的a2[i][i]也不一定是0（或±∝）。占用的存儲單元數(shù)只與結(jié)點數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝）當(dāng)然是無端浪費。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第8頁!⑶容易計算路徑的存在性。在無權(quán)有向圖或無向圖中，判定兩個結(jié)點Vi、Vj之間是否存在長度為m的路徑，只要考慮am=a*a*……*a（m個a矩陣相乘后的乘積矩陣）中（i，j）的元素值是否為0就行了。(4)占用的存儲單元數(shù)只與結(jié)點數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝

）當(dāng)然是無端浪費。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第9頁!深度優(yōu)先搜索深度優(yōu)先搜索類似于樹的前序遍歷，是樹的前序遍歷的推廣。其搜索過程如下：假設(shè)初始時所有結(jié)點未曾被訪問。深度優(yōu)先搜索從某個結(jié)點V0出發(fā)，訪問此結(jié)點。然后依次從V0的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V0有路徑相連的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未被訪問，則另選一個未曾訪問的結(jié)點作起始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問為止。換句話說，深度優(yōu)先搜索遍歷圖的過程是以V0為起始點，由左而右，依次訪問由V0出發(fā)的每條路徑。從v3出發(fā)，按深度優(yōu)先搜索的順序遍歷，得到的結(jié)點序列是v3→v2→v1→v5→v4。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第10頁!廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的按層次遍歷的過程，其搜索過程如下：假設(shè)從圖中某結(jié)點v0出發(fā)，在訪問了v0之后依次訪問v0的各個未曾訪問的鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點都被訪問到。若此時圖中尚有結(jié)點未被訪問，則任選其中的一個作起始點，重復(fù)上述過程，直至圖中所有結(jié)點都被訪問到為止。換句話說，按廣度優(yōu)先順序搜索遍歷圖的過程是以v0為起始點，由近及遠，依次訪問和v0有路徑相連且路徑長度為1，2，3……的結(jié)點。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第11頁!

memset(f,0,sizeof(f));//訪問標(biāo)志初始化f[s]=true;q[1]=s;//訪問源點，源點入隊open=1;closed=1;//隊列的首尾指針初始化while(open<=closed)//若隊列非空,則訪問與隊首元素相連的未訪問點,計算其路徑長度,并將它們送入隊列{for(i=1;i<=n;i++)if((f[i]==false)&&(a[q[open]][i]!=0)){訪問頂點i;f[i]=true;closed++;q[closed]=i;}open++;//出隊}}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第12頁!14356782輸入：81014151626273534375758編程實現(xiàn)：輸入下圖,按深度優(yōu)先遍歷和廣度優(yōu)先遍歷輸出圖的結(jié)點。145Cin>>x>>y>>z;A[x][y]=z;高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第13頁!犯罪團伙1703警察抓到了n個罪犯,警察根據(jù)經(jīng)驗知道他們屬于不同的犯罪團伙,卻不能判斷有多少個團伙,但通過警察的審訊,知道其中的一些罪犯之間相互認識,已知同一犯罪團伙的成員之間直接或間接認識。有可能一個犯罪團伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系,確定犯罪團伙的數(shù)量。已知罪犯的編號從1至n。輸入：行：n(<=1000,罪犯數(shù)量),第二行：m(<5000,關(guān)系數(shù)量)以下若干行：每行兩個數(shù)：I和j,中間一個空格隔開,表示罪犯i和罪犯j相互認識。輸出：一個整數(shù),犯罪團伙的數(shù)量。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第14頁!#include<iostream>usingnamespacestd;inta[1001][1001],visited[1001],n,m,i,s=0;voiddfs(inti){intj;visited[i]=1;for(j=1;j<=n;j++)if((a[i][j]==1)&&(visited[j]==0))dfs(j);}intmain(){inti,x,y;

cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y;a[x][y]=1;a[y][x]=1;}for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0){dfs(i);s++;}cout<<s<<endl;return0;}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第15頁!【培訓(xùn)試題】位圖1866#include<iostream>usingnamespacestd;intdx[4]={-1,0,1,0},dy[4]={0,1,0,-1};chara[200][200];intf[200][200],p[400][4],i,j,k,m,n,ans;boolused[200][200];voidbfs(intx,inty){inti,x1,y1,open,closed;p[1][1]=x;p[1][2]=y;p[1][3]=0;open=1;closed=1;memset(used,0,sizeof(used));if(a[x][y]=='1')return;while(open<=closed){for(i=0;i<4;i++){x1=p[open][1]+dx[i];y1=p[open][2]+dy[i];if(x1>0&&x1<=n&&y1>0&&y1<=m&&!used[x1][y1]){closed++;p[closed][1]=x1;p[closed][2]=y1;p[closed][3]=p[open][3]+1;used[x1][y1]=true;if(a[x1][y1]=='1'){ans=p[closed][3];return;}}}open++;}}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第16頁!無向圖和有向圖

⑴無向圖：在圖G=（V，E）中，如果對于任意的a，b∈V，當(dāng)(a，b)∈E時，必有（b，a）∈E（即關(guān)系R對稱），對稱此圖為無向圖。在一無向圖中用不帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點。在具有n個結(jié)點的無向圖中，邊的最大數(shù)目為n*(n-1)/2。而邊數(shù)達到最大值的圖稱為無向完全圖。在無向圖中一個結(jié)點相連的邊數(shù)稱為該結(jié)點的度，無向完全圖中，每一個頂點的度為n-1。無向完全圖。結(jié)點1、結(jié)點2、結(jié)點3、結(jié)點4的度分別為3高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第17頁!路徑和連通集

在圖G=（V，E）中，如果對于結(jié)點a，b，存在滿足下述條件的結(jié)點序列x1……xk(k>1)

⑴x1=a，xk=b

⑵(xi，xi+1)∈Ei=1‥k-1則稱結(jié)點序列x1=a，x2，…，xk=b為結(jié)點a到結(jié)點b的一條路徑，而路徑上邊的數(shù)目k-1稱為該路徑的長度，并稱結(jié)點集合{x1，…，xk}為連通集。x1=ax2…xk=b高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第18頁!有根圖

在一個有向圖或無向圖中，若存在一個結(jié)點w，它與其他結(jié)點都是連通的，則稱此圖為有根圖，結(jié)點w即為它的根。有根圖，v1、v2、v3、v4都可以作為根有根圖，v1或v2為它的根。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第19頁!強連通圖和強連通分支

若對于有向圖的任意兩個結(jié)點vi、vj間（vi≠vj），都有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱該有向圖是強連通的。有向圖中強連通的最大子圖稱為該圖的強連通分支。上圖不是強連通的,因為v3到v2不存在路徑.它含有兩個強連通分支高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第20頁!

有向圖的相鄰矩陣中[i][j]不一定與[j][i](1≤I,j≤n)相同,且圖中出現(xiàn)自反邊時其對角線上的[i][i]也不一定是0（或±∝）。無向圖的相鄰矩陣[i][j]=[j][i](1≤I,j≤n)且對角線上的[i][i]均為0（或±∝）。正因為如此，在實際存儲相鄰矩陣時只需存儲其上三角(或下三角)的元素。因此具有n個結(jié)點的無向圖，其相鄰矩陣的存儲容量可節(jié)約至(n-1)n/2。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第21頁!⑵相鄰矩陣方便度數(shù)的計算。用相鄰矩陣表示圖，容易判定任意兩個結(jié)點之間是否有邊相聯(lián)，并容易求得各個結(jié)點的度數(shù)。對于無權(quán)無向圖的相鄰矩陣，第i行元素值的和就是Vi的度數(shù)；對于有權(quán)無向圖的相鄰矩陣，第i行（或第i列）中元素值<>±∝的元素個數(shù)就是Vi的度數(shù)；對于無權(quán)有向圖的相鄰矩陣，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度；對于有權(quán)有向圖的相鄰矩陣，第i行中元素值<>±∝的元素個數(shù)就是Vi的出度；第i列元素值<>±∝的元素個數(shù)就是Vi的入度。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第22頁!

圖的遍歷給出一個圖G和其中任意一個結(jié)點V0,從V0出發(fā)系統(tǒng)地訪問G中所有結(jié)點,每一個結(jié)點被訪問一次,這就叫圖的遍歷。遍歷圖的結(jié)果是按訪問順序?qū)⒔Y(jié)點排成一個線性序列。遍歷圖的算法是求解圖的連通性問題、拓樸排序和求關(guān)鍵路徑等算法的基礎(chǔ)。通常有兩種遍歷方法：⑴深度優(yōu)先搜索(dfs)⑵廣度優(yōu)先搜索(bfs)它們對無向圖和有向圖都適用。我們以相鄰矩陣存儲結(jié)構(gòu)給出深度優(yōu)先搜索和廣度優(yōu)先搜索的程序。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第23頁!深度優(yōu)先搜索相鄰矩陣初始化；voiddfs(inti)//深搜{intj;訪問處理結(jié)點i;f[i]=true;//置結(jié)點i為已訪問標(biāo)記for(j=1;j<=n;j++)//按深度優(yōu)先搜索的順序遍歷vi所有子樹if(!f[j]&&a[i][j]==1)dfs(j);}調(diào)用一次dfs(i),可按深度優(yōu)先搜索的順序訪問處理結(jié)點i所在的連通分支(或強連通分支)。整個圖按深度優(yōu)先搜索順序遍歷的過程如下：voidtravel(){memset(f,0,sizeof(f));//置所有結(jié)點未訪問標(biāo)志for(i=1;i<=n;i++)if(!f[i])dfs(i);//深度優(yōu)先搜索每一個未訪問的結(jié)點}深度優(yōu)先搜索高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第24頁!從v3出發(fā)按廣度優(yōu)先搜索的順序遍歷，得到的結(jié)點序列是v3→v2→v4→v1→v5由于隊列“先進先出”的存取規(guī)則與廣度優(yōu)先搜索的遍歷順序相吻合，因此使用了一個工作隊列q，按訪問的先后順序存儲被訪問過的結(jié)點序號。高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第25頁!調(diào)用一次bfs(i)可按廣度優(yōu)先搜索的順序訪問處理結(jié)點i所在的連通分支(或強連通分支)。整個圖按廣度優(yōu)先搜索順序遍歷的過程如下：

voidtravel(){memset(f,0,sizeof(f));//置所有結(jié)點未訪問標(biāo)志

for(i=1;i<=n;i++)

if(!f[i])bfs(i);//廣度優(yōu)先搜索每一個未訪問的結(jié)點}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第26頁!#include<iostream>usingnamespacestd;inta[101][101]={0},f[101],q[101],n,m,i;voidinit(){inti,j,x,y;cin>>n>>m;memset(f,0,sizeof(f));for(i=1;i<=m;i++){cin>>x>>y;a[x][y]=1;a[y][x]=1;}}voiddfs(inti)//深搜{intj;cout<<i<<"";f[i]=1;for(j=1;j<=n;j++)if((f[j]==0)&&(a[i][j]==1))dfs(j);}voidbfs(inti)//廣搜{intj,k,open,closed;memset(q,0,sizeof(q));open=0;closed=1;q[1]=i;//i進隊列cout<<i<<"";f[i]=1;//標(biāo)志while(open<closed)//隊列不空{(diào)open++;k=q[open];//出隊for(j=1;j<=n;j++)if((a[k][j]==1)&&(f[j]==0)){cout<<j<<"";f[j]=1;closed++;//進隊q[closed]=j;}}}intmain(){init();dfs(1);cout<<endl;memset(f,0,sizeof(f));bfs(1);return0;}高中信息競賽-數(shù)據(jù)結(jié)構(gòu)—圖基本概念及搜索遍歷共30頁，您現(xiàn)在瀏覽的是第27頁!樣例輸入：118124354135671051089輸出：3