《數(shù)據(jù)結(jié)構(gòu)》考研課程第五章圖

本節(jié)內(nèi)容圖圖ACEBD樹是N（N≥0）個結(jié)點(diǎn)的有限集合，N=0時，稱為空樹，這是一種特殊情況。在任意一棵非空樹中應(yīng)滿足：1）有且僅有一個特定的稱為根的結(jié)點(diǎn)。2）當(dāng)N>1時，其余結(jié)點(diǎn)可分為m（m>0）個互不相交的有限集合T1，T2，…，Tm，其中每一個集合本身又是一棵樹，并且稱為根結(jié)點(diǎn)的子樹。F圖G由頂點(diǎn)集V和邊集E組成，記為G=(V，E)V(G)表示圖G中頂點(diǎn)的有限非空集。用|V|表示圖G中頂點(diǎn)的個數(shù)，也稱為圖G的階。E(G)表示圖G中頂點(diǎn)之間的關(guān)系（邊）集合。用|E|表示圖G中邊的條數(shù)。VertexEdge圖不可為空，一個圖中就算是一條邊都沒有，也就是邊集為空，但是頂點(diǎn)集一定不為空。圖的基本概念A(yù)BCABC無向圖G2有向圖G1G1=(V1，E1)V1={A，B，C}E1={<A，B>，<B，A>，<A，C>}G2=(V2，E2)V2={A，B，C}E2={(A，B)，(A，C)，(B，C)}圖的基本概念A(yù)BCABC圖的基本概念A(yù)BCABC對于n個頂點(diǎn)每個頂點(diǎn)都與其他n-1個頂點(diǎn)有一條邊，由于重復(fù)，所以一共有n*(n-1)/2條邊每個頂點(diǎn)都與其他n-1個頂點(diǎn)有一條邊，由于有方向不重復(fù)，所以一共有n*(n-1)條邊圖的基本概念若有滿足V(G’)=V(G)的子圖G’，則為G的生成子圖ACA并非V和E的任何子集都能構(gòu)成G的子圖，因為這樣的子集可能不是圖，也就是說，E的子集中的某些邊關(guān)聯(lián)的頂點(diǎn)可能不在這個V的子集中。G=(V，E)V={A，B，C}E={<A，B>，<B，A>，<A，C>}ABCG’=(V’，E’)V’={C}E’={<A，B>，<B，A>}子圖(a)子圖(b)B圖的基本概念A(yù)BDCEFG=(V，E)V={A，B，C，D，E，F(xiàn)}E={(A，B)，(B，C)，(C，D)，(D，A)，(E，F(xiàn))}如果右圖看成一個圖則是不連通的找連通分量的方法：從選取一個頂點(diǎn)開始，以這個頂點(diǎn)作為一個子圖，然后逐個添加與這個子圖相連的頂點(diǎn)和邊直到所有相連的頂點(diǎn)都加入該子圖結(jié)論1:如果一個圖有n個頂點(diǎn)，并且有小于n-1條邊，則此圖必是非連通圖。圖的基本概念A(yù)BCDG=(V，E)V={A，B，C，D}E={<A，B>，<B，C>，<C，A>，<C，D>}不連通ABCD強(qiáng)連通分量圖的基本概念A(yù)BCDEF6個頂點(diǎn)，7條邊ABCDEF6個頂點(diǎn)，5條邊結(jié)論2:生成樹去掉一條邊則變成非連通圖，加上一條邊就會形成回路。圖的基本概念

ABC無向圖ABC有向圖無向圖：有向圖：TD(v)=ID(v)+OD(v)

ABC有向樹圖的基本概念A(yù)BCD1000A->B->C->D->A路徑長度為4A->B->C->A->D和A->B->C->DB和D的距離為2圖的基本概念本節(jié)內(nèi)容圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)相比線性表和樹顯得更復(fù)雜圖中頂點(diǎn)沒有次序之分圖中邊和頂點(diǎn)的數(shù)量任意鄰接矩陣頂點(diǎn)：用一維數(shù)組來存儲邊或?。河枚S數(shù)組來存儲二維數(shù)組就是一維數(shù)組的拓展，相當(dāng)于一維數(shù)組中每個元素也是一個一維數(shù)組。二維數(shù)組也叫做鄰接矩陣a[0]a[1]a[2]a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]a[2][0]a[2][1]a[2][2]3*3二維數(shù)組ABCD頂點(diǎn)數(shù)組：ABCD邊或弧數(shù)組：ABCDABCD0000a[i][j]=1

若(vi,vj)或<vi,vj>是E(G)中的邊0

若(vi,vj)或<vi,vj>不是E(G)中的邊111111111010無向圖的鄰接矩陣是一個對稱矩陣1.判定兩個頂點(diǎn)是否有邊2.求某個頂點(diǎn)的度3.找到某個頂點(diǎn)的所有鄰接點(diǎn)因此可以只存儲上半部分矩陣鄰接矩陣ABCD頂點(diǎn)數(shù)組：ABCD邊或弧數(shù)組：ABCDABCD00001010111100001.頂點(diǎn)的入度是頂點(diǎn)所在這一列的各數(shù)之和；出度是頂點(diǎn)所在這一行的各數(shù)之和。2.判定兩個頂點(diǎn)是否有邊3.找到某個頂點(diǎn)的所有鄰接點(diǎn)對于帶權(quán)圖(網(wǎng))可以在矩陣中存儲邊的權(quán)值A(chǔ)BCD586732ABCDABCD00005∞86732∞∞∞∞∞1、帶權(quán)邊存儲權(quán)值2、行和列相同結(jié)點(diǎn)權(quán)值為03、不存在的邊權(quán)值為無限大鄰接矩陣#defineMaxVertexNuml00 //頂點(diǎn)數(shù)目的最大值typedef

charVertexType; //頂點(diǎn)的數(shù)據(jù)類型不同情況不一樣typedefintEdgeType; //整數(shù)表示權(quán)值或者連通性typedefstruct{ VertexTypeVex[MaxVertexNum]; //頂點(diǎn)表

EdgeTypeEdge[MaxVertexNum][MaxVertexNum]; //鄰接矩陣(二維數(shù)組)，邊表

intvexnum,arcnum; //圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}MGraph;由于鄰接矩陣基于二維數(shù)組，所以利用二維數(shù)組創(chuàng)建圖的時間復(fù)雜度為O(n2)，其中n為圖的頂點(diǎn)數(shù)。所以當(dāng)頂點(diǎn)數(shù)較多時，鄰接矩陣的復(fù)雜度也會比較大。鄰接表對于稀疏圖(|E|遠(yuǎn)小于|V|2)ABCDABCDABCD0000100000000000浪費(fèi)存儲空間順序存儲結(jié)構(gòu)存在預(yù)先分配內(nèi)存可能浪費(fèi)的問題，按照經(jīng)驗會想到鏈?zhǔn)酱鎯Y(jié)構(gòu)adbcefdataabcdef下標(biāo)012345firstchild^^^13524^^^孩子表示法鄰接表dataABCD下標(biāo)0123firstedge1ABCD23^02^013^02^圖中的頂點(diǎn)用一個一維數(shù)組存儲。同時每個元素還要存儲指向第一個鄰接點(diǎn)的指針(鏈表的頭指針)。存儲頂點(diǎn)和頭指針的表叫頂點(diǎn)表圖中每個頂點(diǎn)的所有鄰接點(diǎn)構(gòu)成一個單鏈表。對于無向圖，這個表稱為該結(jié)點(diǎn)的邊表，對于有向圖稱為該結(jié)點(diǎn)的出邊表頂點(diǎn)表邊表鄰接表dataABCD下標(biāo)0123firstedge1ABCD2^2^3^0^注意是以頂點(diǎn)為弧尾需要設(shè)計兩種結(jié)點(diǎn)結(jié)構(gòu)類型：一是頂點(diǎn)表的頂點(diǎn)，二是單鏈表的結(jié)點(diǎn)#defineMaxVertexNum100//圖中頂點(diǎn)數(shù)目的最大值typedefstructArcNode{ //邊表結(jié)點(diǎn)

intadjvex; //該弧所指向的頂點(diǎn)的位置

structArcNode*next;//指向下一條弧的指針}ArcNode;typedefstructVNode{ //頂點(diǎn)表結(jié)點(diǎn)

VertexTypedata; //頂點(diǎn)信息

ArcNode*firstedge; //單鏈表頭指針}VNode,AdjList[MaxVertexNum];//AdjList是結(jié)構(gòu)體數(shù)組類型typedefstruct{ AdjListvertices; //鄰接表

intvexnum,arcnum; //圖的頂點(diǎn)數(shù)和弧數(shù)}ALGraph; //ALGraph是以鄰接表存儲的圖類型十字鏈表dataABCD下標(biāo)0123firstedge1ABCD2^2^3^0^注意是以頂點(diǎn)為弧尾有向圖的鄰接表關(guān)心了有向圖的出邊問題，我們通過有向圖很容易找到頂點(diǎn)的出邊比如從每個頂點(diǎn)表的firstedge指針找到第一條邊的頂點(diǎn)，再通過next指針依次找到下一條邊的頂點(diǎn)直到空指針。但是，如果要找到其他頂點(diǎn)到該頂點(diǎn)的邊，或者說考慮一個頂點(diǎn)的入度問題，則需要遍歷整個圖。這是鄰接表存儲有向圖的缺陷。十字鏈表十字鏈表是針對有向圖的存儲方式，對應(yīng)于有向圖中的每條弧有一個結(jié)點(diǎn)，對應(yīng)于每個頂點(diǎn)也有一個結(jié)點(diǎn)datafirstoutfirstin頂點(diǎn)結(jié)點(diǎn)headvextaillinkheadlinktailvex邊表結(jié)點(diǎn)圖中頂點(diǎn)的數(shù)據(jù)該頂點(diǎn)的入邊表的頭指針該頂點(diǎn)的出邊表的頭指針這條弧的弧尾(起點(diǎn))所在頂點(diǎn)表下標(biāo)這條弧的弧頭(終點(diǎn))所在頂點(diǎn)表下標(biāo)指向弧頭(終點(diǎn))相同的下一條邊指向弧尾(起點(diǎn))相同的下一條邊其實(shí)十字鏈表是在鄰接表的基礎(chǔ)上進(jìn)行了優(yōu)化。在十字鏈表中不僅包含了鄰接表本身就包含的結(jié)點(diǎn)出度結(jié)點(diǎn)，而且還包含了入度結(jié)點(diǎn)的信息。十字鏈表ABCDABCD01下標(biāo)0123入邊表出邊表02弧尾弧頭相同弧頭相同弧尾12^(A->B)(A->C)(B->C)21(C->B)30^(D->A)23(C->D)^^^^^^該頂點(diǎn)的出邊該頂點(diǎn)的入邊十字鏈表的存儲形式不唯一十字鏈表datafirstoutfirstin頂點(diǎn)結(jié)點(diǎn)headvextaillinkheadlinktailvex邊表結(jié)點(diǎn)圖中頂點(diǎn)的數(shù)據(jù)該頂點(diǎn)的入邊表的頭指針該頂點(diǎn)的出邊表的頭指針這條弧的弧尾(起點(diǎn))所在頂點(diǎn)表下標(biāo)這條弧的弧頭(終點(diǎn))所在頂點(diǎn)表下標(biāo)指向弧頭(終點(diǎn))相同的下一條邊指向弧尾(起點(diǎn))相同的下一條邊typedefstructArcNode{

inttailvex,headvex;

structArcNode*hlink,*tlink; }ArcNode;typedefstructVNode{

VertexTypedata;

ArcNode*firstin,*firstout; }VNode;typedefstruct{ VNodexlist[MaxVertexNum]; //頂點(diǎn)依舊用順序存儲(數(shù)組)

intvexnum,arcnum; //圖的頂點(diǎn)數(shù)和弧數(shù)}GLGraph; //十字鏈表存儲的圖類型鄰接多重表ABCDdataABCD下標(biāo)0123firstedge123^02^013^02^頂點(diǎn)表邊表鄰接表存儲的無向圖中查找頂點(diǎn)是比較容易的，但是如果要修改圖中的邊或者是查詢邊,則需要遍歷鏈表。這是鄰接表的缺陷。仿照十字鏈表，對鄰接表的邊表進(jìn)行改造，得到專門針對存儲無向圖的鄰接多重表鄰接多重表ABCDdataABCD下標(biāo)0123firstedge123^02^013^02^頂點(diǎn)表邊表ilinkjlinkjvexivex鄰接多重表邊表結(jié)點(diǎn)這條邊依附的兩個頂點(diǎn)在頂點(diǎn)表的下標(biāo)指向依附頂點(diǎn)ivex的下一條邊指向依附頂點(diǎn)jvex的下一條邊鄰接多重表ABCDilinkjlinkjvexivex這條邊依附的兩個頂點(diǎn)在頂點(diǎn)表的下標(biāo)指向依附頂點(diǎn)ivex的下一條邊指向依附頂點(diǎn)jvex的下一條邊ABCD下標(biāo)01230102301223datafirstedge（A-B）（A-C）（D-A）（B-C）（C-D）^^^^本節(jié)內(nèi)容圖的遍歷圖的遍歷圖的遍歷：從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次，這個過程就叫做圖的遍歷。圖中頂點(diǎn)沒有特殊性，可能存在沿著某條路徑搜索后回到原起點(diǎn)，而有些頂點(diǎn)沒有訪問到。解決辦法：設(shè)置一個訪問數(shù)組,記錄遍歷過程中訪問過的頂點(diǎn)。BFS廣度優(yōu)先搜索(BFS:Breadth-First-Search):廣度優(yōu)先搜索類似于樹的層序遍歷算法ABCDEFGABCDEFG第一層第二層第三層第四層層序遍歷序列：ABCEFDGBFSvoidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個隊列visit(v); //訪問第一個頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對v做已訪問標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊列

while(!isEmpty(Q)){//只要隊列不空 DeQueue(Q,v); //頂點(diǎn)v出隊列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向頂點(diǎn)如果未被訪問 visit(p->adjvex); //訪問p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對這個頂點(diǎn)做已訪問標(biāo)記

EnQueue(Q,p->adjvex); //這個頂點(diǎn)入隊列

}p=p->next；//p指向該頂點(diǎn)的下一條邊 }}}voidBFSTraverse(GraphG){

inti;//單獨(dú)定義是為了方便多個循環(huán)中使用

for(i=0;i<G->vexnum;i++）visited[i]=false;//將標(biāo)志數(shù)組初始化(全局?jǐn)?shù)組)for(i=0;i<G->vexnum;i++){if(!visited[i])BFS(G,i);}//為了避免非連通圖一些頂點(diǎn)訪問不到

若是連通圖只會執(zhí)行一次}}#defineMaxSize100;boolvisited[MaxSize]；BFSvoidBFS(GraphG,intv){ArcNode*p;InitQueue(Q);visit(v);visited[v]=TRUE;

Enqueue(Q,v);

while(!isEmpty(Q)){ DeQueue(Q,v);

p=G->adjList[v].firstedge;while(p){ If(!visited[p->adjvex]){visit(p->adjvex); visited[p->adjvex]=TRUE;

EnQueue(Q,p->adjvex); }p=p->next；}}}ABCD頂點(diǎn)訪問序列：AABCD訪問標(biāo)記數(shù)組是否訪問falsefalsefalsefalse頂點(diǎn)truetruetruetrueAdataABCD下標(biāo)0123firstedge123^02013^02^BBCCDDE4E^1Efalse4^EtrueEpBFS空間復(fù)雜度：BFS需要借助一個隊列，n個頂點(diǎn)均需要入隊一次，所以最壞情況下n個頂點(diǎn)在隊列，那么則需要O(|V|)的空間復(fù)雜度。voidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個隊列visit(v); //訪問第一個頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對v做已訪問標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊列

while(!isEmpty(Q)){//只要隊列不空 DeQueue(Q,v); //頂點(diǎn)v出隊列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向結(jié)點(diǎn)如果未被訪問 visit(p->adjvex); //訪問p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對這個頂點(diǎn)做已訪問標(biāo)記

EnQueue(Q,p->adjvex); //這個頂點(diǎn)入隊列

}p=p->next；//指向該頂點(diǎn)的下一條邊 }}}BFS時間復(fù)雜度：1)鄰接表：每個頂點(diǎn)入隊一次，時間復(fù)雜度為O(|V|),對于每個頂點(diǎn)，搜索它的鄰接點(diǎn)，就需要訪問這個頂點(diǎn)的所有邊，所以時間復(fù)雜度為O(|E|)。所以總的時間復(fù)雜度為O(|V|+|E|)2)鄰接矩陣：每個頂點(diǎn)入隊一次，時間復(fù)雜度為O(|V|),對于每個頂點(diǎn)，搜索它的鄰接點(diǎn)，需要遍歷一遍矩陣的一行，所以時間復(fù)雜度為O(|V|),所以總的時間復(fù)雜度為O(|V|2)voidBFS(GraphG,intv){ArcNode*p;//工作指針pInitQueue(Q);//初始化一個隊列visit(v); //訪問第一個頂點(diǎn)v具體可以是Print visited[v]=TRUE; //對v做已訪問標(biāo)記

Enqueue(Q,v); //頂點(diǎn)v入隊列

while(!isEmpty(Q)){//只要隊列不空 DeQueue(Q,v); //頂點(diǎn)v出隊列

p=G->adjList[v].firstedge;//指針p指向當(dāng)前頂點(diǎn)的邊表鏈表頭指針while(p){

if(!visited[p->adjvex]){ //p所指向結(jié)點(diǎn)如果未被訪問 visit(p->adjvex); //訪問p所指向的頂點(diǎn) visited[p->adjvex]=TRUE;//對這個頂點(diǎn)做已訪問標(biāo)記

EnQueue(Q,p->adjvex); //這個頂點(diǎn)入隊列

}p=p->next；//指向該頂點(diǎn)的下一條邊 }}}BFS應(yīng)用voidBFS_MIN_Distance(GraphG,intu){//d[i]表示從u到i結(jié)點(diǎn)的最短路徑

for(i=0;i<G.vexnum;++i)d[i]=∞;//初始化路徑長度

visited[u]=TRUE;d[u]=0; EnQueue(Q,u); while(!isEmpty(Q)){

DeQueue(Q,u);

ArcNode*p=G->adjList[u].firstedge;while(p){ If(!visited[p->adjvex]){visited[p->adjvex]=TRUE;

//路徑長度加1

d[p->adjvex]=d[u]+1;

EnQueue(Q,p->adjvex); }p=p->next；}} }ABCDEd[A]=0d[B]=d[A]+1=1d[C]=d[A]+1=1d[D]=d[A]+1=1d[E]=d[B]+1=2BFS解決單源非帶權(quán)圖最短路徑問題：按照距離由近到遠(yuǎn)來遍歷圖中每個頂點(diǎn)廣度優(yōu)先生成樹ABCDE如果圖是鄰接矩陣存儲的，廣度優(yōu)先生成樹唯一。如果圖是鄰接矩陣存儲的，廣度優(yōu)先生成樹則不唯一。ABCDEACBDEDFS深度優(yōu)先搜索(DFS:Depth-First-Search):深度優(yōu)先搜索類似于樹的先序遍歷算法首先訪問圖中某一起始頂點(diǎn)v，然后由v出發(fā)，訪問與v鄰接且未被訪問的任一頂點(diǎn)w1，再訪問與w1鄰接且未被訪問的任一頂點(diǎn)w2，……重復(fù)上述過程。當(dāng)不能再繼續(xù)向下訪問時，依次退回到最近被訪問的頂點(diǎn)，若它還有鄰接頂點(diǎn)未被訪問過，則從該點(diǎn)開始繼續(xù)上述搜索過程，直到圖中所有頂點(diǎn)均被訪問過為止ABCDEABECDDFSvoidDFS(GraphG,intv){ArcNode*p;//工作指針p visit(v); //訪問頂點(diǎn)v(一般是打印，即printf) visited[v]=TRUE; //修改訪問標(biāo)記

p=G->adjlist[v].firstarc;//指針p開始指向該頂點(diǎn)的第一條邊

while(p!=NULL){//沒遍歷完頂點(diǎn)的所有鄰接頂點(diǎn)

if(!visited[p->adjvex]){//如果該頂點(diǎn)沒被訪問

DFS(G,p->adjvex);//遞歸訪問該頂點(diǎn)}p=p->nextarc;//看還有沒有其他未訪問的頂點(diǎn)}voidDFSTraverse(GraphG){

inti;//單獨(dú)定義是為了方便多個循環(huán)中使用

for(i=0;i<G->vexnum;i++）visited[i]=false;//將標(biāo)志數(shù)組初始化(全局?jǐn)?shù)組)for(i=0;i<G->vexnum;i++){if(!visited[i])DFS(G,i);//對所有}#defineMaxSize100;boolvisited[MaxSize]；DFS#defineMaxSize100;boolvisited[MaxSize]；voidDFS(GraphG,intv){ArcNode*p; visit(v); visited[v]=TRUE;

p=G->adjlist[v].firstarc;

while(p!=NULL){

if(!visited[p->adjvex]){

DFS(G,p->adjvex);}p=p->nextarc;}}ABCDE頂點(diǎn)訪問序列：AABCD訪問標(biāo)記數(shù)組是否訪問falsefalsefalsefalse頂點(diǎn)truetruetruetrueEfalsetruedataABCD0123firstedge123^02013^02^4E^14^下標(biāo)pBCDEDFSvoidDFS(GraphG,intv){ArcNode*p;//工作指針p visit(v); //訪問頂點(diǎn)v(一般是遍歷，即printf) visited[v]=TRUE; //修改訪問標(biāo)記

p=G->adjlist[v].firstarc;//指針p開始指向該頂點(diǎn)的第一條邊

while(p!=NULL){//沒遍歷完頂點(diǎn)的所有鄰接頂點(diǎn)

if(!visited[p->adjvex]){//如果該頂點(diǎn)沒被訪問

DFS(G,p->adjvex);//遞歸訪問該頂點(diǎn)}p=p->nextarc;//看還有沒有其他未訪問的頂點(diǎn)}空間復(fù)雜度：由于DFS是一個遞歸算法，遞歸是需要一個工作棧來輔助工作，最多需要圖中所有頂點(diǎn)進(jìn)棧，所以時間復(fù)雜度為O(|V|)時間復(fù)雜度：1)鄰接表：遍歷過程的主要操作是對頂點(diǎn)遍歷它的鄰接點(diǎn)，由于通過訪問邊表來查找鄰接點(diǎn)，所以時間復(fù)雜度為O(|E|),訪問頂點(diǎn)時間為O(|V|),所以總的時間復(fù)雜度為O(|V|+|E|)2)鄰接矩陣：查找每個頂點(diǎn)的鄰接點(diǎn)時間復(fù)雜度為O(|V|),對每個頂點(diǎn)都進(jìn)行查找，所以總的時間復(fù)雜度為O(|V|2)深度優(yōu)先生成樹ABCDEABECD如果是一個非連通圖，則是深度優(yōu)先森林ABCDEABEDC深度優(yōu)先生成樹深度優(yōu)先森林本節(jié)內(nèi)容圖的應(yīng)用(1)最小生成樹最小生成樹我們之前講過連通圖的生成樹，它是一個極小的連通子圖。它包含圖中全部的頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊。ABCDEF生成樹不唯一6個頂點(diǎn)，7條邊最小生成樹ABCDEFG51122015841831224A鎮(zhèn)51122015841831224B鎮(zhèn)C鎮(zhèn)D鎮(zhèn)E鎮(zhèn)F鎮(zhèn)G鎮(zhèn)選擇總權(quán)值最小的修路成本自然最小普利姆算法普利姆(Prim)算法:①從圖中找第一個起始頂點(diǎn)v0，作為生成樹的第一個頂點(diǎn)，然后從這個頂點(diǎn)到其他頂點(diǎn)的所有邊中選一條權(quán)值最小的邊。然后把這條邊的另一個頂點(diǎn)v和這條邊加入到生成樹中。②對剩下的其他所有頂點(diǎn)，分別檢查這些頂點(diǎn)與頂點(diǎn)v的權(quán)值是否比這些頂點(diǎn)在lowcost數(shù)組中對應(yīng)的權(quán)值小，如果更小，則用較小的權(quán)值更新lowcost數(shù)組。③從更新后的lowcost數(shù)組中繼續(xù)挑選權(quán)值最小而且不在生成樹中的邊，然后加入到生成樹。④反復(fù)執(zhí)行②③直到所有所有頂點(diǎn)都加入到生成樹中。需要維護(hù)兩個數(shù)組：lowcost[n]adjvex[n]（n是圖中的頂點(diǎn)數(shù)）普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值

lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost0511∞∞∞∞adjvex0000000初始化初始化普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost0511∞∞∞∞adjvex0000000找頂點(diǎn)更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost0011∞∞∞∞adjvex0000000找頂點(diǎn)打?。?->1）更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost00111228∞adjvex0001110找頂點(diǎn)更新數(shù)組i=1普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost00111228∞adjvex0001110找頂點(diǎn)更新數(shù)組i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost00111208∞adjvex0001110找頂點(diǎn)更新數(shù)組打?。?->4）i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}printf(“(%d->%d)”,adjvex[k],k);//打印權(quán)值最小的邊lowcost[k]=0;//將這個頂點(diǎn)加入生成樹//生成樹加入了新的頂點(diǎn)從下標(biāo)為1的頂點(diǎn)開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){

//如果新加入樹的頂點(diǎn)k使得權(quán)值變小lowcost[j]=G.arc[k][j];//更新更小的權(quán)值

adjvex[j]=k;//修改這條邊鄰接的頂點(diǎn)也就是表示這條邊是

從選出的頂點(diǎn)k指過來的方便打印}}}}Lowcost[i]=0表示i號頂點(diǎn)在生成樹中下標(biāo)0123456lowcost0011120415adjvex0001144找頂點(diǎn)更新數(shù)組i=2普利姆算法普利姆(Prim)算法012345651122015841831224VoidMiniSpanTree_Prim(MGraphG){intmin,i,j,k;intadjvex[MAXVEX];//保存鄰接頂點(diǎn)下標(biāo)的數(shù)組intlowcost[MAXVEX];//記錄當(dāng)前生成樹到剩余頂點(diǎn)的最小權(quán)值lowcost[0]=0;//將0號頂點(diǎn)(以0號頂點(diǎn)作為第一個頂點(diǎn))加入生成樹adjvex[0]=0;//由于剛開始生成樹只有一個頂點(diǎn)不存在邊干脆都設(shè)為0for(i=1;i<G.vexnum;i++){//除下標(biāo)為0以外的所有頂點(diǎn)lowcost[i]=G.arc[0][i];//將與下標(biāo)為0的頂點(diǎn)有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0;//這些頂點(diǎn)的adjvex數(shù)組全部初始化為0}

//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點(diǎn)數(shù)min=65535;//tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){//從1號頂點(diǎn)開始找if(lowcost[j]!=0&&lowcost[j]<min){//不在生成樹中的頂點(diǎn)而且權(quán)值更小的min=lowcost[j];//更新更小的值k=j;//找到了新的點(diǎn)下標(biāo)給k}j++;//再看下一個頂點(diǎn)}