圖的定義和基本術語圖的存儲結構圖的遍歷生成樹最短路徑

圖的定義和基本術語圖的存儲結構圖的遍歷生成樹最短路徑圖的定義和基本術語一、圖的定義

本章介紹另一種非線性數據結構—圖,主要學習圖的存儲結構以及若干圖的操作的實現。

圖是一種多對多的結構關系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼。

圖G由兩個集合構成，記作G=(V,{A})

其中V是頂點的非空有限集合，A

是邊的有限集合，其中邊是頂點的無序對或有序對(此時的圖稱為無向圖或)。無向圖G1=(V1,{A1})，V1={v0,v1,v2,v3,v4}，A1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}無序對(vi,vj)：用連接頂點vi、vj的線段表示，稱為無向邊；G1圖示

V0

V4

V3

V1

V2有序對<vi,vj>：用以為vi起點(弧尾)、以vj為終點(弧頭)的有向線段表示，稱為有向邊或?。籊2圖示

V0

V1

V2

V3有向圖G2=(V2,{A2})，V2={v0v1,v2,v3}，A2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>}例1交通圖（公路、鐵路）頂點：地點邊：連接地點的路交通圖中的有單行道、雙行道，分別用有向邊、無向邊表示；例2電路圖頂點：元件邊：連接元件之間的線路例3通訊線路圖頂點：地點邊：地點間的連線例4各種流程圖(如生產流程圖)

頂點：工序邊：各道工序之間的順序關系

V0

V4

V3

V1

V2

V0

V1

V2

V3圖的實例ADTGraph{

數據對象V:V是具有相同特性的數據元素的集合，稱為頂點集。

ADT圖的定義基本操作:CreateGraph(&G,V,VR)//按定義構造圖

初始條件:V是圖的頂點集,VR是圖中弧的集合。

操作結果:按V和VR的定義構造圖G

。數據關系R:R={VR}VR={<v

,w

>︱v

,w

V，且p(v

,w

),<v

,w

>表示從v到w

的弧，謂詞p(v

,w

)定義了弧<v

,w

>的意義或信息。}DestroyGraph(&G)//銷毀

初始條件:圖G存在。

操作結果:銷毀圖G

。LocateVex(G,u)//定位初始條件:圖G存在，u和G中頂點有相同特性。

操作結果:

若G中存在頂點u，則返回該頂點在圖中位置；否則返回其它信息。GetVex(G,v)//求值初始條件:圖G存在，v是G中某個頂點。

操作結果:返回v的值。PutVex(&G,v,value)//賦值初始條件:圖G存在，v是G中某個頂點。

操作結果:對v賦值value。FirstAdjVex(G,v)//求第一個鄰接點初始條件:圖G存在，v是G中某個頂點。

操作結果:返回v的第一個鄰接點。若頂點v在G中沒有鄰接頂點，則返回“空”。NextAdjVex(G,v,w)//求下一個鄰接點

初始條件:圖G存在，v是G中某個頂點，w是v的鄰接點。

操作結果:

返回v的（相對于w的）下一個鄰接點。若w是v的最后一個鄰接點，則返回“空”。InsertVex(&G,v);

//插入頂點初始條件:圖G存在，v和G中頂點有相同特性。

操作結果:

在圖G中增添新頂點v。DeleteVex(&G,v)//刪除頂點初始條件:圖G存在，v和G中頂點有相同特性。

操作結果:刪除G中頂點v及其相關的弧。InsertArc(&G,v,w)//插入弧初始條件:圖G存在，v和w是G中兩個頂點。

操作結果:在G中增添弧<v,w>，若G是無向的，則還增添對稱弧<w,v>。DeleteArc(&G,v,w)

//刪除弧初始條件:圖G存在，v和w是G中兩個頂點。

操作結果:在G中刪除弧<v,w>，若G是無向的，則還刪除對稱弧<w,v>。DFSTraverse(G,v,Visit())//深度優(yōu)先遍歷初始條件:圖G存在，v是G中某個頂點，

Visit是頂點的應用函數。

操作結果:

從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調用函數Visit一次且僅一次。一旦Visit（）失敗，則操作失敗。BFSTraverse(G,v,Visit())//廣度優(yōu)先遍歷初始條件:圖G存在，v是G中某個頂點，

Visit是頂點的應用函數。

操作結果:

從頂點v起廣度優(yōu)先遍歷圖G，并對每個頂點調用函數Visit一次且僅一次。一旦Visit（）失敗，則操作失敗。2頂點的度、入度、出度頂點v的度TD(v)=與v相關聯的邊的數目。在有向圖中：頂點v的出度OD(v)=以v為起點有向邊數；頂點v的入度ID(v)=以v為終點有向邊數；

TD(v)=OD(v)+ID(v)

V0

V4

V3

V1

V2

V0

V1

V2

V3二、圖的基本術語1鄰接點及關聯邊鄰接點：邊的兩個頂點；關聯邊：若邊e=(v,u),則稱邊e與頂點

v和u相關聯；設圖G的頂點數為n，邊數為e則圖的所有頂點的度數之和=2*e（每條邊對圖的所有頂點的度數之和“貢獻”2度）

無向圖G1有向圖G2

V0

V4

V3

V1

V2

V0

V1

V2

V3路徑、回路(環(huán))無向圖G1=（V1，E1）中的頂點序列v1,v2,…,vk,若(vi,vi+1)E1(i=1,2,…k-1),v=v1,u=vk,則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路；在G1中，v0,v1,v2,v3

是v0到v3的路徑；

v0,v1,v2,v3,

v0是回路；有向圖G2=（V2，E2）中的頂點序列v1,v2,…,vk,<vi,vi+1>E2(i=1,2,…k-1),若v=v1,u=vk,則稱該序列是從頂點v到頂點u的路徑；若v=u，則稱該序列為回路；在G2中，v0,v2,v3是v0到v3的路徑v0,v2,v3,v0是回路；

簡單路徑和簡單回路

在一條路徑中,若所有頂點各不相同,則稱該路徑為簡單路徑；若除起點和終點外,

其余頂點各不相同的回路稱為簡單回路。

例有向圖G2無向圖G1

V0

V4

V3

V1

V2

V0

V1

V2

V3在圖G1中，V0,V1,V2,V3

是簡單路徑；V0,V1,V2,V4,V1不是簡單路徑；在圖G2中，V0,V2,V3,V0是簡單回路；連通圖（強連通圖）

在無（有）向圖G=(V,E)中，若對任何兩個頂點v、u都存在從v到u的路徑，則稱G是連通圖（強連通圖）

非連通圖

連通圖

強連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V4

非強連通圖設有兩個圖G=（V，E）、G1=（V1，E1），若V1V，E1E，E1關聯的頂點都在V1中，則稱G1是G的子圖；(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V25子圖例下列(b)、(c)是(a)的子圖(強)連通分量

無向圖G的極大連通子圖稱為G的連通分量。極大連通子圖意思是：該子圖是G連通子圖，將G的任何不在該子圖中的頂點加入，子圖不再連通；

連通分量非連通圖

V0

V2

V3

V1

V5

V4

V0

V2

V1非連通分量有向圖D的極大強連通子圖稱為D的強連通分量。極大強連通子圖意思是：該子圖是D強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的。強連通分量

V0

V1

V2

V3

V0

V2

V3

V1非強連通圖7生成樹

包含無向圖G所有頂點的極小連通子圖稱為G的生成樹。極小連通子圖意思是：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。G的生成樹

V0

V4

V3

V1

V2連通圖G

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2若T是G的生成樹當且僅當T滿足如下條件：

T是G的連通子圖；

T包含G的所有頂點；

T中無回路。一棵n個頂點的生成樹有且僅有足以構成樹的n-1條邊。說明：G的生成樹

V0

V4

V3

V1

V2連通圖G

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2若在一棵生成樹上刪除一條邊，就不再連通。若在一棵生成樹上添加一條邊，必定構成一個環(huán)。

不再連通構成環(huán)圖的存儲結構

由于圖中任意兩個頂點之間都可能存在聯系，因此難以以數據元素在存儲區(qū)中物理位置表示它們間的關系，仍可以借助數組表示之。另一方面，用也可以多重鏈表示圖。但由于圖中頂點的度可能相差懸殊，會因此造成空間的浪費；反之，若按每個頂點的度設計不同的結點結構，又會造成操作上的不便。應根據具體的圖和需要，設計恰當的結點結構和表結構。圖的存儲結構至少要保存兩類信息：

1)頂點的數據；

2)頂點間的關系。

如何表示頂點間的關系？？

V0

V4

V3

V1

V2

V0

V1

V2

V3常用圖的存儲表示一、圖的數組(鄰接矩陣)存儲表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示四、無向圖的鄰接多重表存儲表示鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：A[i][j]=1若(vi,vj)E或<vi,vj>E0否則01010010101011010001100011000000001000

V0

V4

V3

V1

V2

V0

V1

V2

V3一、數組表示法(鄰接矩陣表示)在數組表示法中，用鄰接矩陣表示頂點間的關系typedefstructArcCell{//

弧的定義

VRTypeadj;//VRType是頂點關系類型。對無權圖，

//用1或0表示相鄰否；對帶權圖，則為權值類型。

InfoType*info;//該弧相關信息的指針}ArcCell,

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//－－圖的數組(鄰接矩陣)存儲表示－－#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//最大頂點個數typedefenum{DG,DN,UDG,UDN}graphkind；

//{有向圖，有向網，無向圖，無向網}typedefstruct

{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點向量—保存頂點數據

AdjMatrixarcs;

//鄰接矩陣—保存頂點間關系

intvexnum,arcnum;//頂點數，弧數

GraphKindkind;//圖的種類標志

}MGraph;無向圖數組表示法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表示了兩次；01010010101011010001100對有向圖的數組表示法可做類似的討論

V0

V4

V3

V1

V22）頂點v的度：等于二維數組對應行（或列）中1的個數；3）判斷兩頂點v、u是否為鄰接點：只需判二維數組對應分量是否非零；4）頂點不變，在圖中增加、刪除邊：只需對二維數組對應分量賦非零值或清零；5）用二維數組存儲頂點數為n的圖,占用存儲空間只與它的頂點數n有關，與邊數e無關。適用于邊稠密的圖。

圖的基本操作的實現(采用數組表示法)：1）求無向圖某頂點vi的度：(或有向圖vi的出度)A[i][0]到A[i][n-1]中的非零個數，即數組A第i行的非零元素的個數；01010010101011010001100

V0

V4

V3

V1

V2

V0

V1

V2

V30110000000010002）求有向圖某頂點vi

的入度：A[0][i]到A[n-1][i]中的非零個數，即數組A中第i列的非零元素的個數；3）求圖中的總邊數：掃描整個數組A，統(tǒng)計出數組中非零元素的個數。無向圖的總邊數為非零元素個數的一半，而有向圖的總弧數為非零元素個數。圖的構造操作的實現(采用數組表示法)StatusCreateGraph(Mgraph&G){

//采用數組表示法,

構造圖Gscanf(&G.kind);switch(G.kind){

caseDG:returnCreateDG(G);//構造有向圖G

caseDN:returnCreateDN(G);//構造有向網G

caseUDG:returnCreateUDG(G);//構造無向圖G

caseUDN:returnCreateUDN(G);//構造無向網G

default:returnERROR;}}//CreateGraph無向網的構造算法StatusCreateUDN(Mgraph&G){

//采用數組表示法,

構造無向網Gscanf(&G.vexnum,&G.arcnum,&IncInfo);

//IncInfo為0則各不含其它信息

for(i=0;i<G.vexnum;++i)scanf(G.vexs[i]);//構造頂點向量

for(i=0;i<G.vexnum;++i)//初始化鄰接矩陣

for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){//構造鄰接矩陣

scanf(&v1,

&v2,

&w);//輸入一條邊依附的頂點及權值

i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1和v2在G中位置

G.arcs[i][j].adj=w;//弧<v1,v2>的權值

if(IncInfo)input(*G.arcs[i][j].info)//若弧含有相關信息,則輸入

G.arcs[j][i]=G.arcs[i][j]}

//置<v1,v2>的對稱弧<v2,v1>

returnOK}//CreateUDN例V0V4V3V1V2201234V0V1V2V3V413422110034下標頂點頭指針編號1無向圖的鄰接表頂點通常按編號順序將頂點數據存儲在一維數組中；關聯同一頂點的邊用線性鏈表存儲。二、鄰接表該結點表示邊（V4,Vj）,其中的j是Vj在一維數組中的位置01234ABCDEABECD可見，在有向圖的鄰接表中不易找到指向該頂點的弧。14230122有向圖的鄰接表ABECD303420

在有向圖的逆鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。ABCDE012343有向圖的逆鄰接表typedefstructArcNode{

intadjvex;//該弧所指向的頂點的位置

structArcNode

*nextarc;

//指向下一條弧的指針

InfoType

*info;//該弧相關信息的指針}ArcNode;//表結點弧的結點結構adjvexnextarcinfo//－－圖的鄰接表存儲表示－－typedefstructVNode{VertexTypedata;//頂點信息

ArcNode*firstarc;

//指向第一條依附自該頂點的弧}VNode,AdjList[MAX_VERTEX_NUM];

//頭結點、頭結點數組類型datafirstarc頂點的結點結構typedefstruct{AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標志

}ALGraph;圖的結構定義(鄰接表)無向圖的鄰接表的特點

1）在G鄰接表中，同一條邊對應兩個表結點；

2）頂點v的度：等于v對應線性鏈表的長度；

3）判定兩頂點v，u是否鄰接：要看v對應線性鏈表中有無對應的結點u；

4）在G中增減邊：在兩個單鏈表插入、刪除結點；

5）設存儲頂點的一維數組大小為m(m圖的頂點數n),圖的邊數為e，G占用存儲空間為：m+2×e，與G的頂點數、邊數均有關，適用于邊稀疏的圖。

01234V0V1V2V3V413422110043鄰接表的空間代價與圖的邊及頂點數均有關

V0

V4

V3

V1

V22三、有向圖的十字鏈表存儲表示

弧的結點結構弧尾頂點位置弧頭頂點位置弧的相關信息指向下一個有相同弧尾的結點指向下一個有相同弧頭的結點typedefstructArcBox{//弧的結構表示

inttailvex,headvex;InfoType*info;structArcBox*tlink,*hlink;}ArcBox;頂點的結點結構

頂點數據指向該頂點的第一條入弧指向該頂點的第一條出弧typedefstructVexNode{//頂點的結構表示

VertexTypedata;

ArcBox

*firstin,

*firstout;}VexNode;typedefstruct{VexNodexlist[MAX_VERTEX_NUM];

//頂點結點表頭向量

intvexnum,arcnum;

//有向圖的當前頂點數和弧數}OLGraph;有向圖的結構表示(十字鏈表)

V1

V2

V3

V4v1v2v3v4012323Λ32Λ2031300102有向圖的十字鏈表(圖示）ΛΛΛΛΛΛ

若將有向圖的鄰接矩陣看成是稀疏矩陣的話，則十字鏈表也可以看成是鄰接矩陣的鏈表存儲結構。四、無向圖的鄰接多重表存儲表示typedefstructEbox{VisitIfmark;//訪問標記

intivex,jvex;//該邊依附的兩個頂點的位置

structEBox*ilink,*jlink;//分別依附于這兩個頂點的下一條邊

InfoType*info;//該邊信息指針}EBox;邊的結構表示訪問標記端點i位置依附i的下一條邊端點j位置依附j的下一條邊信息指針頂點的結構表示typedefstructVexBox{VertexTypedata;EBox*firstedge;//第一條依附該頂點的邊的指針}VexBox;頂點的數據第一條依附該頂點的邊的指針typedefstruct{//鄰接多重表

VexBoxadjmulist[MAX_VERTEX_NUM];

intvexnum,edgenum;

}AMLGraph;無向圖的結構表示

V1

V2

V4

V5

V3v1v2v3v4v501234010Λ3Λ

212341Λ2Λ4Λ2Λ4Λ

在不同的存儲結構下，實現各種操作的效率可能是不同的。所以在求解實際問題時，要根據求解問題所需操作，選擇合適的存儲結構。圖的遍歷

在圖中，訪問某個頂點后，可能沿著某條路徑又回到該頂點。為保證每一個頂點只被訪問一次，必須記下已被訪問頂點，

有兩種遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷圖的遍歷算法是圖的許多算法的基礎。一深度優(yōu)先遍歷1）從中某頂點v（起始點）出發(fā)，訪問該頂點；2）依次從v的未被訪問的鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷。直至圖中所有和v有路徑相通的頂點都被訪問到；3）若圖中尚有頂點未被訪問，則另選一個未被訪問頂點作起始點，重復1）、2），直至圖中所有頂點都被訪問到為止。

V0

V7

V6

V5

V4

V3

V2

V1圖G步驟：說明：(強)連通圖的遍歷只須執(zhí)行1）和

2）兩步。Vw1SG1SG2SG3W1、W2和W3

均為V的鄰接點，SG1、SG2和SG3分別為含頂點W1、W2和W3

的子圖。訪問頂點V

;for(W1、W2、W3)

若該鄰接點Wi未被訪問，則從它出發(fā)進行深度優(yōu)先搜索遍歷。w2w3w2

V0

V7

V6

V5

V4

V3

V2

V1,V6例求圖G以V0起始點的的深度優(yōu)先序列V0V1V3V2V7V5

V4V0,V1,V4,V7,V3,V2,V5,V6

V0,V1,V3,V7,V4,V2,V5圖GV6由于沒有規(guī)定訪問鄰接點的順序，深度優(yōu)先序列不唯一為保證每一個頂點只被訪問一次，必須對頂點進行標記。一般用一個輔助數組visited作為對頂點的標記，當頂點vi未被訪問，visited[i]值為FALSE；當vi已被訪問，則visited[i]值為TRUE或被訪問時的次序號。說明：

從深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;如果將圖的頂點的未被訪問鄰接點看作樹結點的孩子，圖的深度優(yōu)先遍歷與樹的先根遍歷是類似的。圖的深度優(yōu)先遍歷從圖中某頂點v出發(fā)：（1）訪問頂點v；

（2）依次從v的未被訪問的鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷。樹的先根遍歷若樹非空

（1）訪問根結點；（2）依次先根遍歷各棵子樹。比較類似voidDFSTraverse(GraphG,Status(*Visit)(intv))

{//對圖G作深度優(yōu)先遍歷

VisitFunc=Visit;

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標志數組初始化

for(v=0;v<G.vexnum;++v)

if(!visited[v])DFS(G,v);

//對尚未訪問的頂點調用DFS}Booleanvisited[MAX]；Status(*VisitFunc)(intv)；voidDFS(GraphG,intv){

//

從頂點v出發(fā)，深度優(yōu)先搜索遍歷連通圖Gvisited[v]=TRUE;VisitFunc(v);

for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

//對v的尚未訪問的鄰接頂點w，遞歸調用DFS}//DFSFFFFFFFFF012345678TTTTTTTTTachdfkebg訪問標志:訪問次序:例如:abchdekfg812345670achkfedbg

V0

V7

V6

V5

V4

V3

V2

V1從圖中某未訪問過的頂點vi出發(fā)：1）訪問頂點vi

；2）依次訪問

vi

的所有未被訪問的鄰接點；3）從這些鄰接點出發(fā)，訪問它們的所有未被未被訪問的鄰接點;依此類推，直到圖中所有的頂點的鄰接點都被訪問。V0V1V3V2V7V6V5V4由于沒有規(guī)定訪問鄰接點的順序，廣度優(yōu)先序列不唯一。你能寫出一個不同的序列嗎？例求圖G的以V0起點的的廣度優(yōu)先序列V0,V1,V2,V3,V4,V5,V6,V7二廣度優(yōu)先遍歷（類似于樹的按層遍歷）Vw1w8w3w7w6w2w5w4對連通圖，從起始點V到其余各頂點必存在路徑。其中，V->w1,V->w2,V->w8

的路徑長度為1;V->w7,V->w3,V->w5的路徑長度為2;V->w6,V->w4

的路徑長度為3。w1Vw2w7w6w3w8w5w4說明：在廣度優(yōu)先遍歷圖時，“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問?！匆訴為起始點，由近至遠，依次訪問和V有路徑相通且路徑長度為1，2，…的頂點。Q

在廣度優(yōu)先遍歷中,為使“先被訪問的頂點,其鄰接點亦先被訪問”

,需附設隊列Q保存被訪問過的頂點，并控制遍歷頂點的順序。V0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7

V0

V7

V6

V5

V4

V3

V2

V1

算法開始時,將起始點訪問后插入Q中,

以后,當Q不空時就從Q中刪除一個頂點,每刪除一個頂點,就依次訪問它的每一個未被訪問過的鄰接點,并令其進隊。這樣,當Q為空時,表明所有與起始點有路徑相通的頂點都已訪問完畢。

V0

V7

V6

V5

V4

V3

V2

V1

V2voidBFSTraverse(GraphG,Status(*Visit)(intv)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//初始化訪問標志

InitQueue(Q);//置空的輔助隊列Q

for(v=0;v<G.vexnum;++v)

if(!visited[v]){//v尚未訪問

visited[v]=TRUE;Visit(v);EnQueue(Q,v);//v入隊列

while(!QueueEmpty(Q)){

DeQueue(Q,u);//隊頭元素出隊并置為u

for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))

if(!visited[w]){visited[w]=TRUE;Visit(w);EnQueue(Q,w);}}

}}//BFSTraverse

圖的廣度優(yōu)先遍歷算法求一條從頂點i到頂點s的簡單路徑abchdekfg

求從頂點b到頂點k的一條簡單路徑。

從頂點b出發(fā)進行深度優(yōu)先搜索遍歷例如:

假設找到的第一個鄰接點是a,則得到的結點訪問序列為:badhcekfg

假設找到的第一個鄰接點是c,則得到的結點訪問序列為:bchdaekfg遍歷應用的一個例子無向連通圖G的生成樹

生成樹是一個圖G的一個極小的連通子圖，包含圖G的所有頂點，但只有n-1條邊。生成樹可由遍歷過程中所經過的邊組成。深度優(yōu)先遍歷得到的生成樹稱為深度優(yōu)先生成樹；廣度優(yōu)先遍歷得到的生成樹稱為廣度優(yōu)先生成樹。

V0

V7

V6

V5

V4

V3

V2

V1

V3

V0

V7

V6

V5

V4

V2

V1深度優(yōu)先生成樹(連通網的)最小生成樹廣度優(yōu)先生成樹

在n個城市間建立通訊聯絡網，要考慮的問題是:如何在保證n點連通的前提下最節(jié)省經費36521655V5V4V2V0V3V146例即要構造連通網N的最小生成樹。這應在N的所有帶權的邊中選取n－1條邊（不構成回路），使權值之和為最小。？最小生成樹（最小支撐樹）最小生成樹是無向連通網的所有生成樹中邊的權值之和最小的一棵生成樹。最小生成樹的構造算法MST性質：多數最小生成樹的構造算法都利用了下述性質。

設N=（V，{E}）是一個連通網，UV，U≠?。若（u,v）是一條具最小有權值的邊，其中uU，vV－U，則必存在一棵包含邊（u,v）的最小生成樹。（可用反證法證之）

普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法是利用MST性質的兩種構造最小生成樹的算法。1.普里姆算法普里姆算法的基本思想:貪心算法

任取一圖N中頂點v

作為生成樹的根，之后不斷往“生成樹的頂點集”U上添加頂點w(V－U)。新添的頂點w

和已在U的頂點v

之間必定存在一條邊(v,w)：(v,w)權值在所有連通頂點v(U)和w

(V－U)之間的邊中權值最小的，并將(v,w)并入“生成樹的邊集”TE中。直至U=V

（TE中有n-1條邊）為止。V3V1V4V6V5V26665551324V3V1V4V6V5V2普里姆算法構造最小生成樹的過程V3V1V4V6V5V2V3V1V4V6V5V2UV-UTEV3V1V4V6V5V2(v1,v3),(v3,v6),(v6,v4),(v3,v2),(v2,v5)

為實現此算法需設置輔助數組closedge，對當前V－U中每個頂點，記錄從U到V－U的代價最小的邊：struct{VertexTypeadjvex;

//U集中的頂點序號

VRTypelowcost;

//邊的權值}closedge[MAX_VERTEX_NUM];

顯然，對viV－U有closedge[i-1].lowcost=Min{cost(u,vi)|uU}iabcdegf195141827168213127aaa19141814例如:e12ee8168d3dd7213c5516e21edcbagfabcdefg所得生成樹權值和=14+8+3+5+16+21=67abcdefg0123456∞19∞∞14∞1819∞5712∞∞∞5∞3∞∞∞∞73∞8∞∞12∞8∞∞16∞∞∞21∞∞2718∞∞∞1627∞構造最小生成樹的普里姆算法voidMiniSpantree_PRIM(mgraphG,VertexTypeu){

輔助數組closedge的定義

k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)

//輔助數組初始化

if(j!=k)closedge[j]={u,G.arcs[k][j].arj};closedge[k].lowcost=0;//起始點u并入U(={u})for(i=1;i<G.vexnum;++i){//k=mininum(closedge);

//求下一個頂點：第k頂點printf(closedge[k].adjvex,G.vexs[k])//輸出生成樹的邊closedge[k].lowcost=0;//第k頂點并入Ufor(j=0;j<G.vexnum;++j)//重新選擇最小邊

if(G.arcs[k][j].arj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].arj}}}具體做法:先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止?？紤]問題的出發(fā)點:為使生成樹上邊的權值之和達到最小，則應使生成樹中每一條邊的權值盡可能地小?？唆斔箍査惴ǖ幕舅枷耄篴bcdegf195141816821312727148531621例如:7121819cdbaegf27最短路徑一、從某個源點到各頂點的最短路徑V5

V4

1006053010V1

V2

V0

V3102050始終路徑點點長度最短路徑v0

v1無∞v2(v0,v2)10v5(v0,v4,v3,v5)60v4(v0,v4)30v3(v0,v4,v3)50迪杰斯特拉(Dijkstra)算法

迪杰斯特拉提出一個求按路徑長度遞增次序產生的最短路徑算法。其基本思想為:

設置S為已求得最短路徑的終點的集合，并用數組D記錄當前所找到的從源點v到每個終點的最短特殊路徑長度（特殊路徑或是弧，或是中間只經過S中頂點的路徑）。初始時，S為空；D[i]值為源v到每個頂點vi的權值。按以下方法不斷擴充S：每次從V－S中取出具有最短特殊路徑長度的頂點添加到S中，同時對D作必要的修改(若D[j]+arcs[j][k]<D[k]，則

D[k]=D[j]+arcs[j][k])。一旦S=V-{v}(S共擴充n-1次)，D就記錄了從源v到其他頂點vi的最短路徑長度（若欲求相應的路徑還應另設數組P）。∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞鄰接矩陣arcs[i][j]∞10∞30100V5

V4

1006053010V1

V2

V0

V310205012