數(shù)據(jù)結(jié)構(gòu)與算法分析課件

數(shù)據(jù)結(jié)構(gòu)與算法分析第六章圖（2）6.3圖的遍歷

從圖的某個(gè)頂點(diǎn)出發(fā)，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)被訪問一次且僅被訪問一次(GraphTraversal)。為避免重復(fù)訪問，需要標(biāo)識(shí)訪問過的頂點(diǎn)

訪問有許多方法和策略，不同的訪問方法和策略導(dǎo)致不同的搜索算法圖的遍歷算法是有關(guān)圖的算法的基礎(chǔ)。最重要的遍歷算法深度優(yōu)先搜索DFS(Depth-Firstsearch)廣度優(yōu)先搜索BFS(Breadth-Firstsearch)1．深度優(yōu)先搜索設(shè)給定的(無向、有向)圖的初態(tài)是所有頂點(diǎn)都未訪問過。在G中任選一個(gè)頂點(diǎn)v為初始出發(fā)點(diǎn)(源點(diǎn))，則深度優(yōu)先遍歷可定義為:1)訪問出發(fā)點(diǎn)v，將其標(biāo)記為訪問過

(old);2)從v出發(fā)，依次考察和v相鄰（鄰接于v）的頂點(diǎn)w：若w未訪問過（new），則以w為新的出發(fā)點(diǎn)遞歸地進(jìn)行深度優(yōu)先遍歷，直到圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)（亦稱從源點(diǎn)可到達(dá)的頂點(diǎn)）均被訪問為止；3)若此時(shí)圖中仍有未被訪問過的頂點(diǎn)，則依次選一個(gè)未訪問過的頂點(diǎn)作為新的搜索起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問過為止。數(shù)據(jù)結(jié)構(gòu)typedefstructnode /*邊表結(jié)點(diǎn)類型定義*/{ intadjvex; /*結(jié)點(diǎn)位置序號(hào)*/ structnode*next; /*指向下一結(jié)點(diǎn)的指針域*/}edgenode;typedefstructvnode /*頭結(jié)點(diǎn)類型定義*/{ datatypevertex; /*頂點(diǎn)信息域*/ edgenode*firstedge;/*邊鏈表頭指針*/}vertexnode;typedefstruct /*圖的鄰接表類型定義*/{ vertexnodeadjlist[m];/*存放頭結(jié)點(diǎn)的順序表*/ intn,e;/*存放圖中的頂點(diǎn)數(shù)與邊數(shù)*/ intvisited[m];}adjgraph;存儲(chǔ)ABCDEABCDE1234023014010201234程序voiddfs(adjgraphg,inti){ /*以vi為出發(fā)點(diǎn)深度優(yōu)先遍歷頂點(diǎn)vi所在的連通分量*/ edgenode*p; printf("visitvertex:%c\n",g.adjlist[i].vertex);/*訪問頂點(diǎn)i*/ g.visited[i]=1; p=g.adjlist[i].firstedge; while(p)/*從p的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索*/ { if(!g.visited[p->adjvex])dfs(g,p->adjvex); p=p->next; }}圖示算法1練習(xí)圖示算法22.廣度優(yōu)先遍歷——類似于樹的層次遍歷

設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問過new，在G中任選一頂點(diǎn)v為源點(diǎn)，則先廣搜索可定義如下:1)訪問出發(fā)點(diǎn)v；2)依次訪問所有與v相鄰的頂點(diǎn)w1，w2……wt；3)再

依次訪問與w1，w2…wt相鄰的所有未訪問的頂點(diǎn)；4)依次類推，直至圖中所有與源點(diǎn)v有路相通的頂點(diǎn)都已訪問過為止；5)此時(shí)，從v開始的搜索結(jié)束，若G是連通的，則遍歷完成；否則在G中另選一個(gè)尚未訪問的頂點(diǎn)作為新源點(diǎn)，繼續(xù)上述搜索過程，直到G中的所有頂點(diǎn)均已訪問為止。如何遍歷？以圖(a)為例，假設(shè)從A出發(fā)進(jìn)行廣度優(yōu)先搜索，首先訪問A，然后依次訪問A的各個(gè)未被訪問過的鄰接頂點(diǎn)B、E、D,再分別從B、E、D出發(fā)，訪問它們的所有還未被訪問過的鄰接頂點(diǎn)C、F、G。實(shí)例A1BCDEFG430123456041240031564654ABEDCFG以vk為出發(fā)點(diǎn),對(duì)用鄰接表表示的圖G進(jìn)行先廣搜索voidBFS1(AdjGraph*G,intk){ inti; EdgeNode*p;

QUEUEQ; MAKENULL(Q); cout<<G→vexlist[k].vertex;G→visited[k]=TRUE; ENQUEUE(k,Q);//進(jìn)隊(duì)列 while(!Empty(Q))//隊(duì)空搜索結(jié)束 { i=DEQUEUE(Q);//vi出隊(duì) p=G→vexlist[i].firstedge;//取vi的邊表頭指針 while(p)//若vi的鄰接點(diǎn)vj(j=p→adjvex)存在,依次搜索 { if(!G→visited[p→adjvex])//若vj未訪問過 { cout<<G→vexlist[p→adjvex].vertex;//訪問vj G→visited[p→adjvex]=TRUE;//給vj作訪問過標(biāo)記 ENQUEUE(p→adjvex,Q);//訪問過的vj入隊(duì) } p=p→next;//找vi的下一個(gè)鄰接點(diǎn) }//重復(fù)檢測(cè)vi的所有鄰接頂點(diǎn) }//外層循環(huán)，判隊(duì)列空否6.4生成樹和最小生成樹

圖與樹的關(guān)系：樹是指一個(gè)無回路存在的連通圖。一個(gè)連通圖G的生成樹是指包含了G所有頂點(diǎn)的樹。一個(gè)連通網(wǎng)絡(luò)的生成樹是帶權(quán)生成樹。具有最小權(quán)值的帶權(quán)生成樹是最小生成樹MinimunSpanningTree非連通圖的各個(gè)連通分量的一組生成樹，構(gòu)成生成樹森林

生成樹的特性一個(gè)連通圖的生成樹是它的極小連通子圖。即包含了所有頂點(diǎn)以及最少的邊或弧的子圖，并且這些邊或弧使得任意兩頂點(diǎn)相互連通。在含有n個(gè)頂點(diǎn)的無向圖中，生成樹一定有n-1條邊。生成樹的形式可能有多個(gè)。生成樹的構(gòu)造圖的生成樹不唯一，與起點(diǎn)和構(gòu)造算法有關(guān)深度優(yōu)先搜索構(gòu)造生成樹：從圖G的任意頂點(diǎn)出發(fā)作深度優(yōu)先搜索訪問G的所有頂點(diǎn)，記錄下來的搜索路徑構(gòu)成生成樹，簡(jiǎn)稱DFS生成樹。廣度優(yōu)先搜索構(gòu)造生成樹：從圖G的任意頂點(diǎn)出發(fā)作廣度優(yōu)先搜索訪問G的所有頂點(diǎn)，記錄下來的搜索路徑構(gòu)成生成樹，簡(jiǎn)稱BFS生成樹。最小生成樹的構(gòu)造：利用最小生成樹的性質(zhì)構(gòu)造最小生成樹的準(zhǔn)則：必須使用且僅使用該連通圖中的n-1條邊連接結(jié)圖中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達(dá)到最小。MST性質(zhì):假設(shè)N=(V,E)是一個(gè)連通網(wǎng)18v4756u5652119633134119UV-U最小權(quán)值的邊（u，v）＝（2，3）U是頂點(diǎn)V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值（代價(jià)）的邊，其中

u∈U, v∈V-U,則必存在一棵包含邊(u,v)的最小生成樹。證明

假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含（u,v），設(shè)T是連通網(wǎng)上的一棵最小生成樹由于T是生成樹，則在T上必存在另一條邊（u’,v’），其中u’∈U、v’∈V-U連接兩個(gè)頂點(diǎn)集U和V-U當(dāng)將邊（u,v）加入到T中時(shí)，由生成樹的定義，T中必包含一條（u,v）,(u’,v’)的回路。在回路上。刪去邊(u’,v’)便可消去上述回路，同時(shí)得到另一棵最小生成樹T’。因?yàn)?u,v)的權(quán)不高于(u’,v’)，則T’的權(quán)亦不高于T，T’是包含（u，v）的一棵最小生成樹。vuu∈Uv∈Uv’u’TT假定G={V,E}為連通網(wǎng)絡(luò)，其中V為頂點(diǎn)集合，E為帶權(quán)邊集合。設(shè)置生成樹頂點(diǎn)集合U，最初它只包含某一個(gè)頂點(diǎn)。設(shè)置生成樹邊集合T，最初為空集。而后考察這樣的邊，它的一個(gè)頂點(diǎn)u∈U，另一個(gè)頂點(diǎn)v∈V-U，每次從所有這樣的邊中選擇權(quán)值最小的邊(u,v)加入集合T，并把頂點(diǎn)v加入到集合U中。如此不斷重復(fù)，直到所有頂點(diǎn)都加入到集合U中為止。（1）Prime算法1243561657535426124356165∞∞124356155354124356155421243561542312435615423圖示算法細(xì)化輸入：連通的加權(quán)無向圖（無向網(wǎng)）G=(V,E)，其中V=(1,2,…,n).輸出：G的最小生成樹引入集合U和T。U存放生成樹的頂點(diǎn)，T存放生成樹的邊集。初值U={1}，T=￠。選擇有最小權(quán)的邊(u,v)，u∈U,v∈(V-U),將v加入U(xiǎn),（u,v）加入T。重復(fù)這一過程，直到U=V.T在完成之前，還是待選邊集voidPrim(G,T){ T=￠; U={1}; //選頂點(diǎn)

while((U–V)!=￠) {

設(shè)(u,v)是使u∈U與v∈(V-U)且權(quán)最小的邊；

T=T∪{(u,v)}; U=U∪{v}; }}/*時(shí)間復(fù)雜性：O(|V|2)數(shù)據(jù)結(jié)構(gòu)圖的鄰接矩陣邊的表示和存儲(chǔ)U集合V-U的解決方法：typedefstruct{ intfromvex,endvex; intlength; //權(quán)值}edge;edge T[n-1]；初始化為只有一個(gè)頂點(diǎn)的U集合和待選邊集，通過邊(u,v)不斷擴(kuò)展U為包括所有頂點(diǎn)的U集合和最小生成樹程序#definen 6//邊的數(shù)據(jù)結(jié)構(gòu)typedefstruct{ intfromvex,endvex; intlength; //權(quán)值}edge;//圖的帶權(quán)鄰接矩陣intdist[n][n]={ 1000,6,1,5,1000,1000, 6,1000,5,1000,3,1000, 1,5,1000,7,5,4, 5,1000,7,1000,1000,2, 1000,3,5,1000,1000,6, 1000,1000,4,2,6,1000}; edge T[n-1]; //存放邊序列，是權(quán)值小的、鄰接于U的邊的集合1243561657535426初始化voidPrime(inti) //i為第一個(gè)選中頂點(diǎn)的下標(biāo){ intj,k,d,v,m,min,max=100000; edgee; v=i; //選定頂點(diǎn)置入中間變量

for(j=0;j<=n-2;j++)//T初始化，置入所有與v鄰接的邊，共有n-1條邊，

{ T[j].fromvex=v; // if(j>=v)//去除自己到自己的邊，

{T[j].endvex=j+1;T[j].length=dist[v][j+1]; } else {T[j].endvex=j; T[j].length=dist[v][j];} }……}核心算法for(k=0;k<n-1;k++){ min=max; for(j=k;j<n-1;j++) if(T[j].length<min) //選擇頂點(diǎn)v的最小權(quán)值邊(u,v) {min=T[j].length;m=j;} e=T[m];T[m]=T[k];T[k]=e;//將最短邊交換到T[k]單元,T[m]放原來的T[k]。

v=T[k].endvex;//v中存放新找到的最短邊在V-U中的頂點(diǎn)

for(j=k+1;j<n-1;j++)//根據(jù)新的v，修改存儲(chǔ)的最小邊集

{ d=dist[v][T[j].endvex];//與k之前的頂點(diǎn)的邊，就不必考慮了

if(d<T[j].length) {T[j].length=d;T[j].fromvex=v;} }}圖示:T的變化0132451657535426013245165∞∞013245155354013245155420142451542301324515423T變化情況0fromvex000000endvex122222length6111111fromvex02(0)2222endvex21(1)5555length15(6)44442fromvex005(0)555endvex333(3)333length552(5)2223fromvex02(0)2222endvex44(4)4444length10005(1000)55554fromvex02(0)224(2)4