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

圖的基本概念及遍歷圖的運(yùn)算

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

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

如果數(shù)據(jù)元素集合D中的各元素之間存在任意的前后件關(guān)系R，則此數(shù)據(jù)結(jié)構(gòu)G=（D，R）稱為圖。如果將數(shù)據(jù)元素抽象為結(jié)點(diǎn)，元素之間的前后件關(guān)系用邊表示，則圖亦可以表示為G=（V，E），其中V是結(jié)點(diǎn)的有窮（非空）集合，E為邊的集合。如果元素a是元素b的前件，這種前后件關(guān)系對應(yīng)的邊用(a，b)表示，即(a，b)∈E。⑵有向圖：如果對于任意的a,b∈V,當(dāng)(a,b)∈E時,(b,a)∈E未必成立，則稱此圖為有向圖。在有向圖中,通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點(diǎn)(方向由前件指向后件)。有向圖中一個結(jié)點(diǎn)的后件個數(shù)稱為該結(jié)點(diǎn)的出度,其前件個數(shù)稱為該結(jié)點(diǎn)的入度。有向圖結(jié)點(diǎn)1的出度和入度分別為1，結(jié)點(diǎn)1和結(jié)點(diǎn)1度都為2路徑和連通集

在圖G=（V，E）中，如果對于結(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稱為該路徑的長度，并稱結(jié)點(diǎn)集合{x1，…，xk}為連通集。x1=ax2…xk=b簡單路徑和回路如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡單路徑。x1=xk的簡單路徑稱為回路（也稱為環(huán)）。v1→v2→v3是一條簡單路徑，v1→v3→v4→v1→v3不是簡單路徑v1→v2→v1為一條回路連通圖和最大連通子圖對于無向圖而言，若其中任兩個結(jié)點(diǎn)之間的連通，則稱該圖為連通圖。一個無向圖的連通分支定義為此圖的最大連通子圖。上圖所示的圖是連通的，它的最大連通子圖即為其本身。強(qiáng)連通圖和強(qiáng)連通分支

若對于有向圖的任意兩個結(jié)點(diǎn)vi、vj間（vi≠vj），都有一條從vi到vj的有向路徑，同時還有一條從vj到vi的有向路徑，則稱該有向圖是強(qiáng)連通的。有向圖中強(qiáng)連通的最大子圖稱為該圖的強(qiáng)連通分支。上圖不是強(qiáng)連通的,因?yàn)関3到v2不存在路徑.它含有兩個強(qiáng)連通分支圖的存儲結(jié)構(gòu)圖的相鄰矩陣表示法相鄰矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個具有n個結(jié)點(diǎn)的圖，則G的相鄰矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n;a[n+1][n+1]1(或權(quán)值)

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

0表示頂點(diǎn)i和頂點(diǎn)j無邊

inta[maxn+1][maxn+1]；boolf[maxn+1]；{頂點(diǎn)的訪問標(biāo)志序列}相鄰矩陣的特點(diǎn)

⑴無向圖的相鄰矩陣是對稱的,而有向圖則不是。無向圖的相鄰矩陣a1[i][j]=a1[j][i](1≤I,j≤n)且對角線上的a[i][i]均為0（或±∝）。正因?yàn)槿绱耍趯?shí)際存儲相鄰矩陣時只需存儲其上三角(或下三角)的元素。因此具有n個結(jié)點(diǎn)的無向圖，其相鄰矩陣的存儲容量可節(jié)約至n(n-1)/2。而有向圖的相鄰矩陣中a2[i][j]不一定與a2[j][i](1≤i，j≤n)相同，且圖中出現(xiàn)自反邊時其對角線上的a2[i][i]也不一定是0（或±∝）。占用的存儲單元數(shù)只與結(jié)點(diǎn)數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點(diǎn)的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝）當(dāng)然是無端浪費(fèi)。⑵相鄰矩陣方便度數(shù)的計算。用相鄰矩陣表示圖，容易判定任意兩個結(jié)點(diǎn)之間是否有邊相聯(lián)，并容易求得各個結(jié)點(diǎn)的度數(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的入度。⑶容易計算路徑的存在性。在無權(quán)有向圖或無向圖中，判定兩個結(jié)點(diǎn)Vi、Vj之間是否存在長度為m的路徑，只要考慮am=a*a*……*a（m個a矩陣相乘后的乘積矩陣）中（i，j）的元素值是否為0就行了。(4)占用的存儲單元數(shù)只與結(jié)點(diǎn)數(shù)有關(guān)而與邊數(shù)無關(guān)。一個含n個結(jié)點(diǎn)的圖，若其邊數(shù)比n2少得多，那么其相鄰矩陣是一個稀疏矩陣，占用許多空間來存儲0（或±∝

）當(dāng)然是無端浪費(fèi)。深度優(yōu)先搜索深度優(yōu)先搜索類似于樹的前序遍歷，是樹的前序遍歷的推廣。其搜索過程如下：假設(shè)初始時所有結(jié)點(diǎn)未曾被訪問。深度優(yōu)先搜索從某個結(jié)點(diǎn)V0出發(fā)，訪問此結(jié)點(diǎn)。然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和V0有路徑相連的結(jié)點(diǎn)都被訪問到。若此時圖中尚有結(jié)點(diǎn)未被訪問，則另選一個未曾訪問的結(jié)點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有結(jié)點(diǎn)都被訪問為止。換句話說，深度優(yōu)先搜索遍歷圖的過程是以V0為起始點(diǎn)，由左而右，依次訪問由V0出發(fā)的每條路徑。從v3出發(fā)，按深度優(yōu)先搜索的順序遍歷，得到的結(jié)點(diǎn)序列是v3→v2→v1→v5→v4。深度優(yōu)先搜索相鄰矩陣初始化；voiddfs(inti)//深搜{intj;訪問處理結(jié)點(diǎn)i;f[i]=true;//置結(jié)點(diǎn)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é)點(diǎn)i所在的連通分支(或強(qiáng)連通分支)。整個圖按深度優(yōu)先搜索順序遍歷的過程如下：voidtravel(){memset(f,0,sizeof(f));//置所有結(jié)點(diǎn)未訪問標(biāo)志for(i=1;i<=n;i++)if(!f[i])dfs(i);//深度優(yōu)先搜索每一個未訪問的結(jié)點(diǎn)}深度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索類似于樹的按層次遍歷的過程，其搜索過程如下：假設(shè)從圖中某結(jié)點(diǎn)v0出發(fā)，在訪問了v0之后依次訪問v0的各個未曾訪問的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點(diǎn)都被訪問到。若此時圖中尚有結(jié)點(diǎn)未被訪問，則任選其中的一個作起始點(diǎn)，重復(fù)上述過程，直至圖中所有結(jié)點(diǎn)都被訪問到為止。換句話說，按廣度優(yōu)先順序搜索遍歷圖的過程是以v0為起始點(diǎn)，由近及遠(yuǎn)，依次訪問和v0有路徑相連且路徑長度為1，2，3……的結(jié)點(diǎn)。

memset(f,0,sizeof(f));//訪問標(biāo)志初始化f[s]=true;q[1]=s;//訪問源點(diǎn)，源點(diǎn)入隊open=1;closed=1;//隊列的首尾指針初始化while(open<=closed)//若隊列非空,則訪問與隊首元素相連的未訪問點(diǎn),計算其路徑長度,并將它們送入隊列{for(i=1;i<=n;i++)if((f[i]==false)&&(a[q[open]][i]!=0)){訪問頂點(diǎn)i;f[i]=true;closed++;q[closed]=i;}open++;//出隊}}調(diào)用一次bfs(i)可按廣度優(yōu)先搜索的順序訪問處理結(jié)點(diǎn)i所在的連通分支(或強(qiáng)連通分支)。整個圖按廣度優(yōu)先搜索順序遍歷的過程如下：

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

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

if(!f[i])bfs(i);//廣度優(yōu)先搜索每一個未訪問的結(jié)點(diǎn)}14356782輸入：81014151626273534375758編程實(shí)現(xiàn)：輸入下圖,按深度優(yōu)先遍歷和廣度優(yōu)先遍歷輸出圖的結(jié)點(diǎn)。145Cin>>x>>y>>z;A[x][y]=z;犯罪團(tuán)伙1703警察抓到了n個罪犯,警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙,卻不能判斷有多少個團(tuán)伙,但通過警察的審訊,知道其中的一些罪犯之間相互認(rèn)識,已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識。有可能一個犯罪團(tuán)伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系,確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號從1至n。輸入：第一行：n(<=1000,罪犯數(shù)量),第二行：m(<5000,關(guān)系數(shù)量)以下若干行：每行兩個數(shù)：I和j,中間一個空格隔開,表示罪犯i和罪犯j相互認(rèn)識。輸出：一個整數(shù),犯罪團(tuán)伙的數(shù)量。樣例輸入：118124354135671051089輸出：3說明：共三個犯罪團(tuán)伙。【培訓(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++;}}【培訓(xùn)試題】位圖1866intmain(){cin>>n>>