圖的定義和術(shù)語(yǔ)72圖的存儲(chǔ)結(jié)構(gòu)73圖的遍歷課件

7.1圖的定義和術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖及其應(yīng)用7.6最短路徑

第七章圖7.1圖的定義和術(shù)語(yǔ)第七章圖圖(Graph)——由一個(gè)頂點(diǎn)集V和一個(gè)邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。

Graph=(V,E)其中，V={x|x

某個(gè)數(shù)據(jù)對(duì)象}是非空有限的頂點(diǎn)集合；

E={(x,y)|x,y

V}或E={<x,y>|x,y

V&&Path(x,y)}是有限的頂點(diǎn)之間關(guān)系的集合，(x,y)也叫做邊(edge)集合,它是無(wú)方向的;Path(x,y)表示從x到y(tǒng)的一條單向通路,它是有方向的,所以<x,y>也叫做弧(arc)的集合,x稱(chēng)為弧尾或始點(diǎn),y稱(chēng)為弧頭或終點(diǎn).7.1圖的定義和術(shù)語(yǔ)圖(Graph)——由一個(gè)頂點(diǎn)集V和一個(gè)邊集E構(gòu)成的數(shù)據(jù)結(jié)構(gòu)有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集

E(G)是有向邊（也稱(chēng)?。┑挠邢藜希∈琼旤c(diǎn)的有序?qū)?，記?lt;v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭無(wú)向圖——無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的

其中：V(G)是頂點(diǎn)的非空有限集

E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v) 7.1圖的定義和術(shù)語(yǔ)有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的7.1例7.1245136G1圖G1中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例7.2157324G26圖G2中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}7.1圖的定義和術(shù)語(yǔ)例7.1245136G1圖G1中：V(G1)={1,2,3,無(wú)向完全圖(Completedgraph)—n個(gè)頂點(diǎn)的無(wú)向圖有n(n-1)/2條邊（最大邊數(shù)是n(n-1)/2）有向完全圖——n個(gè)頂點(diǎn)的有向圖，有n(n-1)條邊（最大邊數(shù)是n(n-1)）稀疏圖(sparsegraph)：邊或弧很少的圖,通常邊數(shù)<nlog2n稠密圖(Densegraph)無(wú)向圖中，邊數(shù)接近n(n-1)/2；

有向圖中，邊數(shù)接近n(n-1)7.1圖的定義和術(shù)語(yǔ)無(wú)向完全圖(Completedgraph)—n個(gè)頂點(diǎn)的無(wú)有向完全圖7.1圖的定義和術(shù)語(yǔ)無(wú)向圖(樹(shù))有向圖完全圖無(wú)向完全圖有向完全圖7.1圖的定義和術(shù)語(yǔ)無(wú)向圖(樹(shù))有向圖完全圖無(wú)權(quán)——與圖的邊或弧相關(guān)的數(shù)網(wǎng)——帶權(quán)的有向圖叫有向網(wǎng)，帶權(quán)的無(wú)向圖叫無(wú)向網(wǎng)7.1圖的定義和術(shù)語(yǔ)權(quán)——與圖的邊或弧相關(guān)的數(shù)7.1圖的定義和術(shù)語(yǔ)子圖——如果圖G(V,E)和圖G’(V’,E’),滿(mǎn)足：V’V，E’E

則稱(chēng)G‘為G的子圖7.1圖的定義和術(shù)語(yǔ)子圖——如果圖G(V,E)和圖G’(V’,E’),滿(mǎn)足：7.鄰接點(diǎn)(或相鄰點(diǎn)),關(guān)聯(lián)

如果e=(u,v)是E(G)中的一條邊，則稱(chēng)u與v互為鄰接頂點(diǎn)或相鄰頂點(diǎn);稱(chēng)邊e與頂點(diǎn)u,v關(guān)聯(lián);如果e=<u,v>

是E(G)中的一條弧，則稱(chēng)u鄰接到v,v鄰接于u,也稱(chēng)e與u,v關(guān)聯(lián);稱(chēng)弧e與頂點(diǎn)u,v關(guān)聯(lián);7.1圖的定義和術(shù)語(yǔ)鄰接點(diǎn)(或相鄰點(diǎn)),關(guān)聯(lián)7.1圖的定義和術(shù)語(yǔ)頂點(diǎn)的度（于樹(shù)的度不同）無(wú)向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù),記作TD(v)有向圖中，頂點(diǎn)的度分成入度與出度入度：以該頂點(diǎn)為頭的弧的數(shù)目,記為ID(v)出度：以該頂點(diǎn)為尾的弧的數(shù)目,記為OD(v)一個(gè)頂點(diǎn)的度數(shù)等于該頂點(diǎn)的入度與出度之和,即TD(v)=OD(v)+ID(v)7.1圖的定義和術(shù)語(yǔ)頂點(diǎn)的度（于樹(shù)的度不同）7.1圖的定義和術(shù)語(yǔ)路徑——路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，滿(mǎn)足(Vij-1,Vij)E或<Vij-1,Vij>E,(1<jn)路徑長(zhǎng)度——沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和簡(jiǎn)單路徑——序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑回路(環(huán))——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑簡(jiǎn)單回路(簡(jiǎn)單環(huán))——除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路7.1圖的定義和術(shù)語(yǔ)路徑——路徑是頂點(diǎn)的序列V={Vi0,Vi1,……Vin}，7.1圖的定義和術(shù)語(yǔ)V0V1V3V2V0V1V3V2V0V1V2V0V1V3V07.1圖的定義和術(shù)語(yǔ)V0V1V3V2V0V1V3V2V0連通圖與連通分量在無(wú)向圖中,若從頂點(diǎn)v1到頂點(diǎn)v2有路徑,則稱(chēng)頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的,則稱(chēng)此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。ABCDEHMFGIJLK無(wú)向圖G的三個(gè)連通分量ABCDEFGIJLHMK無(wú)向圖G7.1圖的定義和術(shù)語(yǔ)連通圖與連通分量ABCDEHMFGIJLK無(wú)向圖G的三個(gè)連通強(qiáng)連通圖與強(qiáng)連通分量在有向圖中,

若對(duì)于每一對(duì)頂點(diǎn)vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱(chēng)此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。強(qiáng)連通圖有向圖G有向圖G的兩個(gè)強(qiáng)連通分量7.1圖的定義和術(shù)語(yǔ)強(qiáng)連通圖與強(qiáng)連通分量強(qiáng)連通圖有向圖G生成樹(shù)：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊。如果在生成樹(shù)上添加1條邊，必定構(gòu)成一個(gè)環(huán)若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。ABCDEHMABCDEHM無(wú)向圖G

無(wú)向圖G的生成樹(shù)

7.1圖的定義和術(shù)語(yǔ)生成樹(shù)：是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n生成森林：由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。有向圖G的生成森林有向圖G7.1圖的定義和術(shù)語(yǔ)生成森林：有向圖G的生成森林有向圖G7.1圖的定義和術(shù)語(yǔ)本章只討論簡(jiǎn)單圖,有兩類(lèi)圖形不在本章討論之列：7.1圖的定義和術(shù)語(yǔ)本章只討論簡(jiǎn)單圖,有兩類(lèi)圖形不在本章討論之列：7.1圖的圖的抽象數(shù)據(jù)類(lèi)型定義ADTGraph{數(shù)據(jù)對(duì)象V：v是具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}；VR={<v,w>|v,w∈V且P(v,w),

<v,w>表示從v到w的弧，

謂詞P(v,w)定義了弧<v,w>的意義或信息}基本操作P：}圖的抽象數(shù)據(jù)類(lèi)型定義ADTGraph{CreatGraph(&G,V,VR)

//按定義(V,VR)構(gòu)造圖DestroyGraph(&G)://銷(xiāo)毀圖基本操作LocateVex(G,u);

//若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在圖中“位置”

；否則返回其它信息。GetVex(G,v);

//返回v的值。PutVex(&G,v,value);

//對(duì)v賦值value。CreatGraph(&G,V,VR)DestroyGrFirstAdjVex(G,v);//返回v的“第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)//在G中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G,v,w);//返回v的（相對(duì)于w的）“下一個(gè)鄰接

點(diǎn)”。若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”?；静僮鱂irstAdjVex(G,v);NextAdjVex(InsertArc(&G,v,w);

//在G中增添弧<v,w>，若G是無(wú)向的，//則還增添對(duì)稱(chēng)弧<w,v>。DeleteArc(&G,v,w);

//在G中刪除弧<v,w>，若G是無(wú)向的，//則還刪除對(duì)稱(chēng)弧<w,v>。DeleteVex(&G,v);//刪除G中頂點(diǎn)v及其相關(guān)的弧。InsertVex(&G,v);//在圖G中增添新頂點(diǎn)v?；静僮鱅nsertArc(&G,v,w);DeleteArcDFSTraverse(G,v,Visit())//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit())//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。DFSTraverse(G,v,Visit())BFST圖的四種常用的存儲(chǔ)形式：鄰接矩陣和加權(quán)鄰接矩陣（labeledadjacencymatrix）鄰接表十字鏈表鄰接多重表7.2圖的存儲(chǔ)結(jié)構(gòu)圖的四種常用的存儲(chǔ)形式：7.2圖的存儲(chǔ)結(jié)構(gòu)一、(加權(quán))鄰接矩陣（labeledadjacencymatrix）設(shè)圖G=<V,E>是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣是一個(gè)二維數(shù)組G.arcs[n][n]，定義：一、(加權(quán))鄰接矩陣（labeledadjacencym無(wú)向圖G1有向圖G2無(wú)向圖G1有向圖G2

一、(加權(quán))鄰接矩陣（continue）(1)對(duì)稱(chēng)矩陣(可采用壓縮存儲(chǔ));(2)每一行(或列)1的個(gè)數(shù)是該頂點(diǎn)的度;(3)主對(duì)角線(xiàn)全為0(簡(jiǎn)單圖);從鄰接矩陣中可以反映圖的許多特征:無(wú)向圖一、(加權(quán))鄰接矩陣（continue）(1)對(duì)稱(chēng)矩陣(

一、(加權(quán))鄰接矩陣（continue）有向圖(1)每一行1的個(gè)數(shù)是該頂點(diǎn)的出度;(2)每一列1的個(gè)數(shù)是該頂點(diǎn)的入度;(3)主對(duì)角線(xiàn)全為0(簡(jiǎn)單圖);有向圖的鄰接矩陣不一定對(duì)稱(chēng)。一、(加權(quán))鄰接矩陣（continue）有向圖(1)每一定義為：G.arcs[i][j]=Wij

<vi,vj>或（vi,vj）∈VR∞無(wú)邊（?。┮杂邢蚓W(wǎng)為例：鄰接矩陣：N.Edge=(

v1v2

v3v4v5v6

)頂點(diǎn)表：5v1v2v3v4v5v6489755613N∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

∞網(wǎng)絡(luò)的鄰接矩陣

一、(加權(quán))鄰接矩陣（continue）定義為：G.arcs[i][j]=Wij<v容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。⒄翼旤c(diǎn)的鄰接點(diǎn)等等。

n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。對(duì)稀疏圖而言尤其浪費(fèi)空間。鄰接矩陣法優(yōu)點(diǎn)：鄰接矩陣法缺點(diǎn)：

一、(加權(quán))鄰接矩陣（continue）容易實(shí)現(xiàn)圖的操作，如：求某頂#defineINFINITYINT_MAX#defineMAX_VERTEX_NUM20typedefenum{DG,DN,UDG,UDN}GraghKind;typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點(diǎn)關(guān)系類(lèi)型。

//對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；

//對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。

InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];用鄰接矩陣表示的圖的存儲(chǔ)表示(P161)用鄰接矩陣表示的圖的存儲(chǔ)表示(P161)typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)信息

AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)

GraphKindkind;//圖的種類(lèi)標(biāo)志

}MGraph;

用鄰接矩陣表示的圖的存儲(chǔ)表示(continue)typedefstruct{//圖的定義用鄰接矩陣表StatusCreateUDN(Mgraph&G){//用鄰接矩陣表示returnOK;}例：用鄰接矩陣生成無(wú)向網(wǎng)的算法（參見(jiàn)教材P162）scanf(&G.vexnum,&G.arcnum,&IncInfo);//輸入總頂點(diǎn)數(shù)，總弧數(shù)和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//輸入頂點(diǎn)值，存入一維向量中for(i=0;i<G.vexnum;++i)//對(duì)鄰接矩陣n*n個(gè)單元初始化，adj=∞,info=NULLfor(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};for(k=0;k<G.arcnum;++k){//給弧賦初值(循環(huán)次數(shù)＝弧數(shù))

scanf(&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);//找到兩頂點(diǎn)在矩陣中的位置(n次)

G.arcs[i][j].adj=w;//輸入對(duì)應(yīng)權(quán)值

If(IncInfo)Input(*G.arcs[i][j].info);G.arcs[j][i]=G.arcs[i][j]；//無(wú)向網(wǎng)是對(duì)稱(chēng)矩陣}對(duì)于n個(gè)頂點(diǎn)e條弧的網(wǎng)，建網(wǎng)時(shí)間效率=O(n2+n+e*n)StatusCreateUDN(Mgraph&G){//intfirstAdjVex(MgraphG,intv){

//返回頂點(diǎn)v的第一個(gè)鄰接點(diǎn)，G為無(wú)向圖for(k=0;k<G.vexnum;k++) if(G.adj[v][k]>0)break; if(k>=G.vexnum)k=-1;//無(wú)鄰接點(diǎn)

returnk;}//endfirstAdjVex()圖的部分操作在鄰接矩陣上的實(shí)現(xiàn)intfirstAdjVex(MgraphG,int二、鄰接表(AdjacencyList)無(wú)向圖的鄰接表為每個(gè)頂點(diǎn)建立一個(gè)單鏈表,第i個(gè)單鏈表中的結(jié)點(diǎn)表示與頂點(diǎn)vi相鄰的頂點(diǎn)01234^1334^142^0注：鄰接表不唯一，因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。v1v2v3v4v523^142^0v1v2v3v5v4v4二、鄰接表(AdjacencyList)無(wú)向圖的鄰接表data:結(jié)點(diǎn)的數(shù)據(jù)域，保存結(jié)點(diǎn)的數(shù)據(jù)值。firstarc:結(jié)點(diǎn)的指針域，給出自該結(jié)點(diǎn)出發(fā)的的第一條邊

的邊結(jié)點(diǎn)的地址。頭結(jié)點(diǎn):datafirstarcadjvexnextarc表結(jié)點(diǎn):adjvex:該邊或弧所指向的頂點(diǎn)的位置.nextarc:指向下一條邊或弧的指針.二、鄰接表(AdjacencyList)adjvexnextarcdatafirstarcdata:結(jié)點(diǎn)的數(shù)據(jù)域，保存結(jié)點(diǎn)的數(shù)據(jù)值。頭結(jié)點(diǎn):在無(wú)向圖的鄰接表中,如何求每個(gè)頂點(diǎn)的度？若頂點(diǎn)數(shù)為n,邊數(shù)為e時(shí),則在無(wú)向圖中共需多少個(gè)結(jié)點(diǎn)？二、鄰接表(AdjacencyList)01234^1334^142^0v1v2v3v4v523^142^0v1v2v3v5v4v4n個(gè)頭結(jié)點(diǎn),2e個(gè)表結(jié)點(diǎn)第i

個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)i的度在無(wú)向圖的鄰接表中,如何求每個(gè)頂點(diǎn)的度？若頂點(diǎn)數(shù)為n,邊數(shù)為有向圖的鄰接表和逆鄰接表在有向圖的鄰接表中，第i

個(gè)單鏈表鏈接的邊都是頂點(diǎn)i

發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i

個(gè)單鏈表鏈接的邊都是進(jìn)入頂點(diǎn)

i

的邊。也叫做入邊表。v1v2v3v4V4V3^V2V12^3^0^1V4V3V2V1^3^0^2^0鄰接表(出邊)逆鄰接表(入邊)01230123用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需n個(gè)頂點(diǎn)結(jié)點(diǎn)，e個(gè)邊結(jié)點(diǎn)。有向圖的鄰接表和逆鄰接表v1v2v3v4V4V3^V2V12網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值cost網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表帶權(quán)圖的邊結(jié)點(diǎn)中保存該邊上的權(quán)值鄰接表表示的圖的存儲(chǔ)結(jié)構(gòu)（P163）//邊結(jié)點(diǎn)定義typedefstructArcNode{intadjvex;//該弧所指向的頂點(diǎn)的位置

structArcNode*nextarc;//指向下一條弧的指針

InfoType*info;//該弧相關(guān)信息的指針}ArcNode;adjvexinfonextarc鄰接表表示的圖的存儲(chǔ)結(jié)構(gòu)（P163）//邊結(jié)點(diǎn)定義adjve//頭結(jié)點(diǎn)定義typedefstructVNode{VertexTypedata;//頂點(diǎn)信息

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧}VNode,AdjList[MAX_VERTEX_NUM];datafirstArc鄰接表表示的圖的存儲(chǔ)結(jié)構(gòu)（P163）//頭結(jié)點(diǎn)定義datafirstArc鄰接表表示//圖的定義typedefstruct{AdjListvertices;intvexnum,arcnum;intkind;//圖的種類(lèi)標(biāo)志}ALGraph;

鄰接表表示的圖的存儲(chǔ)結(jié)構(gòu)（P163）//圖的定義鄰接表表示的圖的存儲(chǔ)結(jié)構(gòu)（P163）圖的操作在鄰接連表的上的實(shí)現(xiàn)intfirstAdjVex(ALGraphghead,intv){ returnghead[v]->firstArc.adjvex; }//endfirstAdjVex()intnextAdjVex(ALGraphghead,intv,intw){ p=ghead[v]->firstArc; while(p&&p->adjvex!=w)p=p->next; if(!p)return0; elsereturnp->next->adjvex; }//endnextAdjVex()找某頂點(diǎn)的所有鄰接點(diǎn)的時(shí)間復(fù)雜度是O(e)圖的操作在鄰接連表的上的實(shí)現(xiàn)找某頂點(diǎn)的所有鄰接點(diǎn)的時(shí)間復(fù)雜度如何建立鄰接表（以有向圖為例）算法思想：首先將鄰接表表頭數(shù)組初始化，vertex域初始化為i，firstarc初始化為NULL；然后對(duì)讀入的每一條弧<i,j>，產(chǎn)生一個(gè)表結(jié)點(diǎn)，adjver域置為j，并將結(jié)點(diǎn)鏈接到鄰接表的第i個(gè)鏈表中。如何建立鄰接表（以有向圖為例）算法思想：算法如下：VoidGreatAdjList(ALGraph&G){ArcNode*p;sacnf(“%d%d”,&n,&e);G.vexnum=n;G.arcnum=e;for(i=0;i<n;i++){G.vertices[i].vertex=i;G.vertices[i].firstarc=NULL;}for(k=0;k<e;k++){scanf(i,j);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=p;}}//GreatAdjList算法如下：VoidGreatAdjList(ALGraph討論：鄰接表與鄰接矩陣的比較1.聯(lián)系：都可以用來(lái)存儲(chǔ)有向圖和無(wú)向圖；鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。2.區(qū)別：①鄰接矩陣是順序結(jié)構(gòu)，鄰接表是鏈?zhǔn)浇Y(jié)構(gòu)②對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。

鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。

鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<<n2)討論：鄰接表與鄰接矩陣的比較1.聯(lián)系：都可以用來(lái)存儲(chǔ)有向圖三、鄰接多重表(無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu))在無(wú)向圖的鄰接表中,一條邊出現(xiàn)兩個(gè)單鏈表中.浪費(fèi)空間，也給某種操作帶來(lái)了困難。在鄰接多重表中，每一條邊只有一個(gè)結(jié)點(diǎn)(稱(chēng)邊結(jié)點(diǎn))為有關(guān)邊的處理提供了方便。三、鄰接多重表(無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu))在無(wú)向圖的鄰接表中

markivexjvexilinkjlink其中:mark

是記錄是否處理過(guò)的標(biāo)記；ivex和jvex是依附于該邊的兩頂點(diǎn)位置。ilink域指向下一條依附于頂點(diǎn)ivex的邊；jlink指向下一條依附于頂點(diǎn)jvex的邊。需要時(shí)還可設(shè)置一個(gè)存放與該邊相關(guān)的權(quán)值的域

cost。邊結(jié)點(diǎn)的結(jié)構(gòu)Ebox:三、鄰接多重表(無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu))markivexjvexilinkj頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu):

其中:data

存放與該頂點(diǎn)相關(guān)的信息;Firstarc是指示第一條依附于該頂點(diǎn)的邊的指針。存儲(chǔ)頂點(diǎn)信息的結(jié)點(diǎn)表以順序表方式組織.在鄰接多重表中,所有依附于同一個(gè)頂點(diǎn)的邊都鏈接在同一個(gè)單鏈表中。從頂點(diǎn)i

出發(fā),可以循鏈找到所有依附于該頂點(diǎn)的邊，也可以找到它的所有鄰接頂點(diǎn)。

dataFirstarcVexBox:三、鄰接多重表(無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu))頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu):dataFirsta例aecbd0123acdb4e010323212441^^^^^三、鄰接多重表(無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu))例aecbd0123acdb4e0四、十字鏈表(有向圖的一種存儲(chǔ)結(jié)構(gòu))可以把十字鏈表看成是將有向圖的鄰接表和逆鄰接表這兩個(gè)表結(jié)合起來(lái)而得到的一種鏈表。在十字鏈表中,有向圖中每一條弧對(duì)應(yīng)一個(gè)結(jié)點(diǎn)(稱(chēng)弧結(jié)點(diǎn))每一個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)結(jié)點(diǎn)(稱(chēng)頂點(diǎn)結(jié)點(diǎn))。四、十字鏈表(有向圖的一種存儲(chǔ)結(jié)構(gòu))可以把十字鏈表看成是將有其中:

tailvex表示該弧的弧尾頂點(diǎn)在圖中的位置；

headvex表示該弧的弧頭頂點(diǎn)在圖中的位置；

hlink指向弧頭相同的下一條弧的指針；

tlink指向弧尾相同的下一條邊的指針。需要時(shí)還可有權(quán)值域cost

邊結(jié)點(diǎn)的結(jié)構(gòu)tailvexheadvexhlinktlinkArcBox:四、十字鏈表(有向圖的一種存儲(chǔ)結(jié)構(gòu))其中:邊結(jié)點(diǎn)的結(jié)構(gòu)tailvexheadv頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)

dataFirstinFirstoutVexNode:其中:數(shù)據(jù)域data存放與該頂點(diǎn)相關(guān)的信息，指針域Firstin指向以該頂點(diǎn)為弧頭的第一條??；指針域Firstout指向以該頂點(diǎn)為弧尾的第一條弧。四、十字鏈表(有向圖的一種存儲(chǔ)結(jié)構(gòu))頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)dataFirstin例bdacabcd012302012320323130^^^^^^^^四、十字鏈表(有向圖的一種存儲(chǔ)結(jié)構(gòu))例bdacabcd01230#defineMAX_VERTEX_NUM20TypedefstructArcBox{//弧結(jié)點(diǎn)結(jié)構(gòu)

inttailvex,headvex;structArcBox*hlink,tlink;InfoType*info;}ArcBox；TypedefstructVexNode{//頂點(diǎn)結(jié)構(gòu)

VertexTypedata;ArcBox*firstin,*firstout;}VexNode;Typedefstruct{VexNodexlist[MAX_VERTEX_NUM];//表頭向量

intvexnum,arcnum;}OLGraph;//圖結(jié)構(gòu)#defineMAX_VERTEX_NUM207.3圖的遍歷從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪(fǎng)問(wèn)圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪(fǎng)問(wèn)一次，就叫做圖的遍歷(GraphTraversal)。深度優(yōu)先遍歷廣度優(yōu)先遍歷圖的兩種遍歷方法7.3圖的遍歷從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊訪(fǎng)圖中可能存在回路，在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)為了避免重復(fù)訪(fǎng)問(wèn)，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn)i

被訪(fǎng)問(wèn)，就立即讓visited[i]

為1，防止它被多次訪(fǎng)問(wèn)。7.3圖的遍歷圖中可能存在回路，在訪(fǎng)問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到DFS算法思想：深度優(yōu)先搜索DFS(DepthFirstSearch)從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪(fǎng)問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至V0的所有鄰接點(diǎn)都被訪(fǎng)問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn),則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。DFS算法思想：深度優(yōu)先搜索DFS(DepthFirs深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例深度優(yōu)先遍歷生成樹(shù)深度優(yōu)先搜索DFS(DepthFirstSearch圖的深度優(yōu)先遍歷算法voiddfsTraverse(){ for(v=1;v<=n;v++)visited[v]=false; for(v=1;v<=n;v++) if(!visited[v])dfs(v);}voiddfs(intv){visited[v]=1;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w)) if(!visited[w])dfs(w); }//使用ADT在遞歸函數(shù)中增加一計(jì)數(shù)器sum，初值為n，每訪(fǎng)問(wèn)一次就減1,減到0則return，可避免遞歸時(shí)間過(guò)長(zhǎng)。圖的深度優(yōu)先遍歷算法在遞歸函數(shù)中增加一計(jì)數(shù)器sum，初值為n在鄰接矩陣A上實(shí)現(xiàn)

voiddfs(intv){visited[v]=true;for(w=1;w<=n;w++) if(A[v][w]>0) if(!visited[w])dfs(w); }//

圖的深度優(yōu)先遍歷算法在鄰接矩陣A上實(shí)現(xiàn)圖的深度優(yōu)先遍歷算法在鄰接鏈表上實(shí)現(xiàn)

voiddfs(intv){visited[v]=true;

p=ghead[v]->firstArc;

while(p){w=p->adjvex; if(!visited[w])dfs(w);

p=p->next;

}同學(xué)們自己考慮非遞歸實(shí)現(xiàn)算法圖的深度優(yōu)先遍歷算法在鄰接鏈表上實(shí)現(xiàn)同學(xué)們自己考慮非遞歸實(shí)現(xiàn)算法圖的深度優(yōu)先遍Dfs1(Graphg,intv){//利用棧實(shí)現(xiàn)非遞歸算法

//第一個(gè)頂點(diǎn)入棧并訪(fǎng)問(wèn)Visit(v);visit[v]=1;push(s,v);//當(dāng)棧不空時(shí)做

Whlie(!EmptyStack(s)){p=ghead[v]->firstArc;//找到棧頂?shù)囊粋€(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，入棧并訪(fǎng)問(wèn)

while(p){w=p->adjvex; if(!visited[w]){push(s,w);visit(w);p=ghead[w]->firstArc;}elsep=p->next;}//while//如果所有鄰接點(diǎn)都被訪(fǎng)問(wèn)，出棧

pop(s,v);}//while}Dfs1(Graphg,intv){//利用棧實(shí)現(xiàn)非遞V1V2V4V5V3V7V6V8例深度遍歷：V1

12341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8例深度遍歷：V112341V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1

V3V7V6V2V4V8V5V1V2V4V5V3V7V6V8例12341342vexdaDFS算法效率分析:

設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，遍歷時(shí)對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DSF函數(shù)，遍歷圖的過(guò)程就是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程，消耗的時(shí)間取決于所采用的存儲(chǔ)結(jié)構(gòu)如果用鄰接矩陣來(lái)表示圖，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(n2)。如果用鄰接表來(lái)表示圖，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(e),加上訪(fǎng)問(wèn)n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。DFS算法效率分析:設(shè)圖中有n個(gè)頂點(diǎn)，e條邊，遍歷二、廣度優(yōu)先搜索BFS(BreadthFirstSearch

)BFS算法思想：從圖中的某個(gè)頂點(diǎn)V0出發(fā)，并在訪(fǎng)問(wèn)此頂點(diǎn)之后依次訪(fǎng)問(wèn)V0的所有未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪(fǎng)問(wèn)的先后次序依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪(fǎng)問(wèn),則另選圖中一個(gè)未曾被訪(fǎng)問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪(fǎng)問(wèn)到為止。二、廣度優(yōu)先搜索BFS(BreadthFirstSeABCDEFGHIJKL樹(shù)的按層次進(jìn)行訪(fǎng)問(wèn)的次序：

A、B、C、D、E、F、G、H、I、J、K、L適用的數(shù)據(jù)結(jié)構(gòu)：隊(duì)列二、廣度優(yōu)先搜索BFSABCDEFGHIJKL樹(shù)的按層次進(jìn)行訪(fǎng)問(wèn)的次序：二、廣度優(yōu)除了輔助數(shù)組visited[]之外，為了實(shí)現(xiàn)逐層訪(fǎng)問(wèn)，算法中使用了一個(gè)隊(duì)列，以記憶正在訪(fǎng)問(wèn)的這一層和上一層的頂點(diǎn)，以便于向下一層訪(fǎng)問(wèn)廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪(fǎng)問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。廣度優(yōu)先搜索BFS除了輔助數(shù)組visited[]之外，為了實(shí)現(xiàn)逐層訪(fǎng)VoidBFSTraverse(GraghG,intv){

for(v=0;v<G.vexnum;v++)visited[v]=0;//清訪(fǎng)問(wèn)標(biāo)記

InitQueue(Q);//清隊(duì)列Q;

for(v=0;v<G.vexnum;v++)//對(duì)每一個(gè)頂點(diǎn)vif(!visited[v]){visited[v]=1;visit(v);//訪(fǎng)問(wèn)v;標(biāo)記v;EnQueue(Q,v);//v未被訪(fǎng)問(wèn)

while(!QueueEmpty(Q))

{

//Q不空

DeQueue(Q,u);//出隊(duì)頭元素到ufor(w=firstAdjVex(u);w;w=nextAdjVex(u,w))

if(!visited[w]){visited[w]=1;visit(w);EnQueue(w);//將u的每個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)w入隊(duì)

}//if

}//while

}//if}VoidBFSTraverse(GraghG,int例adbce1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22012345afr遍歷序列：a012345dfr遍歷序列：ad012345dcfr遍歷序列：adc例adbce1234acdbvexdatafirstarc1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22012345dcbfr遍歷序列：adcb012345

cbfr遍歷序列：adcb012345

cbefr遍歷序列：adcbe例adbce1234acdbvexdatafirstarc55401234525fr遍歷序列：adcbe0123455fr遍歷序列：adcbe012345

fr遍歷序列：adcbe1234acdbvexdatafirstarc5543^^^adjvexnext5e1^51143^22例adbce012345算法分析:如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+d1+…+dn-1=O(e)，其中的di是頂點(diǎn)i的度如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的n個(gè)元素，總的時(shí)間代價(jià)為O(n2)。廣度優(yōu)先搜索BFSDFS與BFS之比較：空間復(fù)雜度相同，都是O(n)(借用了堆棧或隊(duì)列）；時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。算法分析:如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑2.

求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑三、遍歷應(yīng)用舉例1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑2.求兩個(gè)頂應(yīng)用1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑abchdekfg求從頂點(diǎn)b到頂點(diǎn)k的一條簡(jiǎn)單路徑。從頂點(diǎn)b出發(fā)進(jìn)行深度優(yōu)先搜索遍歷例如:假設(shè)找到的第一個(gè)鄰接點(diǎn)是a,且得到的結(jié)點(diǎn)訪(fǎng)問(wèn)序列為:

b

adhce

kfg假設(shè)找到的第一個(gè)鄰接點(diǎn)是c,則得到的結(jié)點(diǎn)訪(fǎng)問(wèn)序列為:

b

chdae

kfg應(yīng)用1.求一條從頂點(diǎn)i到頂點(diǎn)s的簡(jiǎn)單路徑abchvoidDFSearch(intv,ints,char*PATH){//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，//求得一條從v到s的簡(jiǎn)單路徑，并記錄在PATH中

visited[v]=TRUE;//訪(fǎng)問(wèn)第v個(gè)頂點(diǎn)

for(w=FirstAdjVex(v);w!=0;

w=NextAdjVex(v))if(!visited[w])DFSearch(w,s,PATH);

}

Append(PATH,getVertex(v));

//第v個(gè)頂點(diǎn)加入路徑&&!foundif(w==s){found=TRUE;Append(PATH,w);}else

if(!found)Delete(PATH,v);

//從路徑上刪除頂點(diǎn)vvoidDFSearch(intv,ints,c應(yīng)用2.求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑

若兩個(gè)頂點(diǎn)之間存在多條路徑，則其中必有一條路徑長(zhǎng)度最短的路徑。如何求得這條路徑?應(yīng)用2.求兩個(gè)頂點(diǎn)之間的一條路徑長(zhǎng)度最短的路徑若兩abchdekfg求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先搜索遍歷進(jìn)行，但需要修改隊(duì)列的結(jié)點(diǎn)結(jié)構(gòu)及其入隊(duì)列和出隊(duì)列的算法。深度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序取決于圖的存儲(chǔ)結(jié)構(gòu)，而廣度優(yōu)先搜索訪(fǎng)問(wèn)頂點(diǎn)的次序是按“路徑長(zhǎng)度”漸增的次序。abchdekfg求路徑長(zhǎng)度最短的路徑可以基于廣度優(yōu)先搜索遍例如:求下圖中頂點(diǎn)3至頂點(diǎn)5的一條最短路徑。隊(duì)列用雙向鏈表的表示:

312475

Q.front

Q.rear321475689例如:求下圖中頂點(diǎn)3至頂點(diǎn)5的一條最短路徑。隊(duì)列用雙7.4圖的連通性問(wèn)題對(duì)無(wú)向連通圖進(jìn)行遍歷得到的將是一個(gè)極小連通子圖，即圖的生成樹(shù)！由深度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為深度優(yōu)先搜索生成樹(shù)。由廣度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為廣度優(yōu)先搜索生成樹(shù)。對(duì)非連通圖進(jìn)行遍歷，得到的將是各連通分量的生成樹(shù)，即圖的生成森林！7.4.1無(wú)向圖的連通分量和生成樹(shù)7.4圖的連通性問(wèn)題對(duì)無(wú)向連通圖進(jìn)行遍歷得到的將是一個(gè)極例1：畫(huà)出下圖的生成樹(shù)DFS生成樹(shù)v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹(shù)v0v1v3v2v4無(wú)向連通圖例1：畫(huà)出下圖的生成樹(shù)DFS生成樹(shù)v0v1v2v4v4v3DEABCFJLMGHIK例2：畫(huà)出下圖的生成森林（或極小連通子圖）求解步驟：Step1:先求出鄰接矩陣或鄰接表；Step2:寫(xiě)出DFS或BFS結(jié)果序列；Step3:畫(huà)出對(duì)應(yīng)子圖或生成森林。我們選用鄰接表方式來(lái)求深度優(yōu)先搜索生成森林DEABCFJLMGHIK例2：畫(huà)出下圖的生成森林（或極小連1155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DEGHIK子圖1：再寫(xiě)出DFS結(jié)果（3次）ABMJLCFDEGHKIABCFJLM先寫(xiě)出鄰接表（或鄰接矩陣）：子圖2：子圖3：極小連通！1155M12L11K10J9I8H7G6F5E4D3C2BDEGHIK子圖(或連通分量)ABCFJLMABCFJLMDEGHIK生成森林DEGHIK子圖ABCFJLMABCFJLMDEGHIK生成求連通分量的算法（生成森林用對(duì)應(yīng)的二叉樹(shù)存儲(chǔ)）VoidDFSForest(BiTree&T)

{T=NULL;for(v=0;v<n;v++)visited[v]=0;for(v=0;v<n;v++)if(!visited[v]){p=(CSTree)malloc(sizeof(CSNode));//生成樹(shù)的根*p={GetVex(G,v),NULL,NULL}if(!T)T=p;//森林空，p是第一棵樹(shù)

elseq->nextsibling=p;q=p;//q當(dāng)前森林中最后一棵樹(shù)的根

DFSTree(G,v,p);//深度優(yōu)先遍歷，并建立樹(shù)；

}//if}//求連通分量的算法（生成森林用對(duì)應(yīng)的二叉樹(shù)存儲(chǔ)）VoidDFSTree(GraphG,intv,CSTree&T){visited[v]=1;first=true;for(w=firstAdjVex(v);w;w=nextAdjVex(v,w))

if(!visited[w]){ p=(CSTree)malloc(sizeof(CSNode));//生成樹(shù)的根*p={GetVex(G,v),NULL,NULL}; if(first){T->lchild=p;first=false;} elseq->nextsibling=p;}q=p; DFSTree(G,w,q);

}//if

}//DFSTree()VoidDFSTree(GraphG,intv,7.4.2有向圖的強(qiáng)連通分量

算法思想：使用dfs算法思想。設(shè)一編號(hào)數(shù)組finished[]1.

對(duì)圖G的鄰接鏈表進(jìn)行dfs遍歷，并按退出遞歸的次序給頂點(diǎn)編號(hào)。（1，2，3，….）2.對(duì)圖G的逆鄰接鏈表進(jìn)行dfs遍歷，每次調(diào)用dfs的出發(fā)點(diǎn)是編號(hào)最大的未被訪(fǎng)問(wèn)的頂點(diǎn)(上次最后完成搜索的頂點(diǎn)）圖G1234513245例Finished1234535421得到的頂點(diǎn)集：1,3，24，57.4.2有向圖的強(qiáng)連通分量圖G1234513245例7.4.3最小生成樹(shù)MST(MinimumcostSpanningTree)

使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。按照生成樹(shù)的定義，n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)有n個(gè)頂點(diǎn)、n-1條邊。MST:在網(wǎng)絡(luò)的多個(gè)生成樹(shù)中，尋找一個(gè)各邊權(quán)值之和最小的生成樹(shù)。構(gòu)造最小生成樹(shù)的準(zhǔn)則必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)；必須使用且僅使用n-1條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)；不能使用產(chǎn)生回路的邊。7.4.3最小生成樹(shù)MST(Minimumcost假設(shè)在n個(gè)城市之間要建立通信網(wǎng)絡(luò)線(xiàn)，要求使得這個(gè)城市之間連通且費(fèi)用最少。MST典型用途：數(shù)學(xué)模型：頂點(diǎn)———表示城市，有n個(gè)；邊————表示線(xiàn)路，有n–1條；邊的權(quán)值—表示線(xiàn)路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)——表示n個(gè)城市間通信網(wǎng)。問(wèn)題抽象：

n個(gè)頂點(diǎn)的生成樹(shù)很多，需要從中選一棵代價(jià)最小的生成樹(shù)，即該樹(shù)各邊的代價(jià)之和最小。此樹(shù)便稱(chēng)為最小生成樹(shù)MST假設(shè)在n個(gè)城市之間要建立通信網(wǎng)絡(luò)線(xiàn)，要求使得這個(gè)城市之間連通求一個(gè)帶權(quán)連通圖中的最小生成樹(shù)的方法:

Prim算法

Kruskal算法都是利用MST的性質(zhì)構(gòu)造最小生成樹(shù)的算法7.4.3最小生成樹(shù)MST求一個(gè)帶權(quán)連通圖中的最小生成樹(shù)的方法:都是利用MST的性質(zhì)構(gòu)最小生成樹(shù)的MST性質(zhì)：若U集是V的一個(gè)非空子集，若(u0,v0)是一條最小權(quán)值的邊，其中u0

U，v0

V-U；則：(u0,v0)必在某一最小生成樹(shù)上。UV-U最小生成樹(shù)的MST性質(zhì)：若U集是V的一個(gè)非空子集，若(u證明（反證法）設(shè)G的任何MST都不包含（u,v）。設(shè)T是G的一個(gè)MST，將（u,v）加入T，形成回路。去掉（u’,v’）得到T’,因wuv<wu’v’，所以T’的邊權(quán)之和小于T的邊權(quán)之和，與T是MST矛盾。Uuu’V-Uvv’最小生成樹(shù)的MST性質(zhì)：證明（反證法）UV-U最小生成樹(shù)的MST性質(zhì)：1、普里姆(Prim)算法普里姆算法的基本思想（是一種貪婪算法）設(shè)連通網(wǎng)絡(luò)圖G=<V,E,W>,TE是G上最小生成樹(shù)中邊的集合.1.TE=，U={u0

};2.在U和V-U之間選最小邊（u,v），將v加入U(xiǎn)，將(u,v)加入TE中;3.重復(fù)2直到U=V(或n-1次)1、普里姆(Prim)算法普里姆算法的基本思想（是一種貪婪算普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612221237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過(guò)程示例1237456281612222510251418普里姆(P設(shè)置一個(gè)輔助數(shù)組closedge[]，對(duì)每個(gè)頂點(diǎn)vi

V－U,存在分量closedge[i-1],有兩個(gè)域，Lowcost=Min{cost(u,vi)|u

U}adjvex:

存儲(chǔ)與該邊關(guān)聯(lián)的U中頂點(diǎn)Prime算法的實(shí)現(xiàn)輔助數(shù)組closedge說(shuō)明如下:Struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];設(shè)置一個(gè)輔助數(shù)組closedge[]，對(duì)每個(gè)頂點(diǎn)viV細(xì)化的普里姆(Prim)算法:TE={};closedge[v].adjvex=v1;closedge[v].lowcost=adj.matrix[1][v];2.U[1]=1;U[2…n]=0;3.選U[k]=0的closedge[k].lowcost最小的k；4.U[k]=1,u=closedge[k].adjvex,(u,k)加入TE中5.修改所有不屬于U的k的鄰接點(diǎn)w的lowcost值，規(guī)則是：如果closedge[w].lowcost>adj.matrix[k][w]則：closedge[w].lowcost=adj.matrix[k][w]細(xì)化的普里姆(Prim)算法:12374562816122225102514181237456281612222510251418Adjvexv3v4v5v6v1v2{1,6,5,4,{}Lowcost1612222410423,2,7}Closedge

I

2

3

4

5

6

7UV-UkAdjvexv1v1v1v1v1v1{1}{2,3,4,6

Lowcost28105,6,7}Adjvexv1v1v1v6v1v1{1,6}{2,3,4,5,5Lowcost2824

10

7}Adjvexv1v1v5v6v1v5{1,6,5}{2,3,4,7}4Lowcost2822

241025Adjvexv1v4v5v6v1v4{1,6,5,4}{2,3,7}3

Lowcost2812

22241018Adjvexv3

v4v5v6v1v4{1,6,5,4,{2,7}2

Lowcost16

12222410

18

3}Adjvexv3v4v5v6v1

v2{1,6,5,4,{7}7Lowcost1612222410

14

3,2}Adjvexv3v4vvoidMiniSpanTree_PRIM(MgtaphG,VertexTypeintu){k=LocateVer(G,u);//k為頂點(diǎn)u的序號(hào)for(v=0;v<G.vexnum;v++)if(v!=k)closedge[v]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;//第k個(gè)頂點(diǎn)加入在U集合中

for(i=1;i<G.vexnum;i++){k=minimum(closedge);//lowcost最小的頂點(diǎn)序號(hào)為ku=closedge[k].adjvex;prinf(u,G.vexs[k]);closedge[k].lowcost=0;//第k個(gè)頂點(diǎn)并入U(xiǎn)集

for(j=0;j<G.vexnum;j++)if(G.arcs[k][j].adj<closedge[j].lowcost)closedge[j]={G.vexs[k],G.arcs[k][j].adj}

}//for

}//MinISpan_Tree_PRIMvoidMiniSpanTree_PRIM(Mgtaph設(shè)連通網(wǎng)絡(luò)有n個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為O(n2)。它適用于邊稠密的網(wǎng)絡(luò)。Prime算法分析設(shè)連通網(wǎng)絡(luò)有n個(gè)頂點(diǎn)，則該算法的時(shí)間復(fù)雜度為O(n2)2、Kruscal算法算法思想:先構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)的子圖SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。2、Kruscal算法算法思想:先構(gòu)造一個(gè)只含n個(gè)頂構(gòu)造非連通圖ST=(V,{});k=i=0;//k計(jì)選中的邊數(shù),i計(jì)檢查的邊數(shù)

while(k<n-1){++i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);

且k++;}算法描述:構(gòu)造非連通圖ST=(V,{});算法描述:√√√√×√×√√√√√×√×√7.4.4關(guān)節(jié)點(diǎn)和重連通分量

(BiconnectedComponent)若從一個(gè)連通圖中刪去任何一個(gè)頂點(diǎn)及其相關(guān)聯(lián)的邊，它仍為一個(gè)連通圖的話(huà)，則該連通圖被稱(chēng)為重（雙）連通圖。若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱(chēng)此頂點(diǎn)為關(guān)節(jié)點(diǎn)(割點(diǎn))。沒(méi)有關(guān)節(jié)點(diǎn)的連通圖為重（雙）連通圖。如何判別給定的連通圖是否是雙連通圖？7.4.4關(guān)節(jié)點(diǎn)和重連通分量(BiconnectedC在一個(gè)無(wú)向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹(shù)找到。關(guān)節(jié)點(diǎn)的兩個(gè)特性：1.深度優(yōu)先生成樹(shù)的根是關(guān)節(jié)點(diǎn)的充要條件是它至少有兩個(gè)子女。2.其它頂點(diǎn)u是關(guān)節(jié)點(diǎn)的充要條件是它至少有一個(gè)子女w,以w為根的子樹(shù)與u的任一祖先之間無(wú)回邊。7.4.4關(guān)節(jié)點(diǎn)和重連通分量

(BiconnectedComponent)在一個(gè)無(wú)向連通圖G中,重連通分量可以利用深度優(yōu)先生成樹(shù)找到ahgcbfde例如:下列連通圖中，頂點(diǎn)

a

和頂點(diǎn)c

是關(guān)節(jié)點(diǎn)深度優(yōu)先生成樹(shù)abcdefghahgcbfde例如:下列連通圖中，頂點(diǎn)a和頂點(diǎn)c是1abcdefgh2345678331111111abcdefgh2345678331111111)設(shè)V0為深度優(yōu)先遍歷的出發(fā)點(diǎn)

p=G.vertices[0].firstarc;v=p->adjvex;

DFSArticul(G,v);

//從第v頂點(diǎn)出發(fā)深度優(yōu)先搜索

if

(count<G.vexnum)

{

//生成樹(shù)的根有至少兩棵子樹(shù)

printf(0,G.vertices[0].data);

//根是關(guān)節(jié)點(diǎn)1)設(shè)V0為深度優(yōu)先遍歷的出發(fā)點(diǎn)2)定義函數(shù):

low(v)=Min{visited[v],low[w],visited[k]}

其中:頂點(diǎn)w

是生成樹(shù)上頂點(diǎn)v

的孩子;頂點(diǎn)k

是生成樹(shù)上和頂點(diǎn)v有回邊相聯(lián)接的祖先;

visited記錄深度優(yōu)先遍歷時(shí)的訪(fǎng)問(wèn)次序

若對(duì)頂點(diǎn)v，在生成樹(shù)上存在一個(gè)子樹(shù)根w,

且

low[w]≥visited[v]

則頂點(diǎn)v為關(guān)節(jié)點(diǎn)。2)定義函數(shù):對(duì)深度優(yōu)先遍歷算法作如下修改：visited[v]的值改為遍歷過(guò)程中頂點(diǎn)的訪(fǎng)問(wèn)次序count值;

2.遍歷過(guò)程中求得

low[v]=Min{visited[v],low[w],visited[k]}3.從子樹(shù)遍歷返回時(shí)，判別low[w]≥visited[v]?對(duì)深度優(yōu)先遍歷算法作如下修改：visited[v]的值改為遍for(p=G.vertices[v0].firstarc;p;p=p->nextarc){

}voidDFSArticul(ALGraphG,intv0){//從第v0個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,

//查找并輸出關(guān)節(jié)點(diǎn)}//DFSArticulmin=visited[v0]=++count;//v0是第count個(gè)訪(fǎng)問(wèn)的頂點(diǎn),并設(shè)low[v0]的初值為min

//檢查v0的每個(gè)鄰接點(diǎn)low[v0]=min;for(p=G.vertices[v0].f