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

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

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

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

某個數(shù)據(jù)對象}是非空有限的頂點集合；

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

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

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

E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序?qū)Γ洖?lt;v,w>，v,w是頂點，v為弧尾，w為弧頭無向圖——無向圖G是由兩個集合V(G)和E(G)組成的

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

E(G)是邊的有限集合，邊是頂點的無序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v) 7.1圖的定義和術(shù)語有向圖——有向圖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ù)語例7.1245136G1圖G1中：V(G1)={1,2,3,無向完全圖(Completedgraph)—n個頂點的無向圖有n(n-1)/2條邊（最大邊數(shù)是n(n-1)/2）有向完全圖——n個頂點的有向圖，有n(n-1)條邊（最大邊數(shù)是n(n-1)）稀疏圖(sparsegraph)：邊或弧很少的圖,通常邊數(shù)<nlog2n稠密圖(Densegraph)無向圖中，邊數(shù)接近n(n-1)/2；

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

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

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

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

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

無向圖G的生成樹

7.1圖的定義和術(shù)語生成樹：是一個極小連通子圖，它含有圖中全部n個頂點，但只有n生成森林：由若干棵生成樹組成，含全部頂點，但構(gòu)成這些樹的邊是最少的。有向圖G的生成森林有向圖G7.1圖的定義和術(shù)語生成森林：有向圖G的生成森林有向圖G7.1圖的定義和術(shù)語本章只討論簡單圖,有兩類圖形不在本章討論之列：7.1圖的定義和術(shù)語本章只討論簡單圖,有兩類圖形不在本章討論之列：7.1圖的圖的抽象數(shù)據(jù)類型定義ADTGraph{數(shù)據(jù)對象V：v是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(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ù)類型定義ADTGraph{CreatGraph(&G,V,VR)

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

//若G中存在頂點u，則返回該頂點在圖中“位置”

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

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

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

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

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

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

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

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

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

v1v2

v3v4v5v6

)頂點表：5v1v2v3v4v5v6489755613N∞

5

∞

7

∞

∞∞

∞

4

∞

∞

∞

8

∞

∞

∞∞

9∞

∞

5∞

∞

6∞

∞

∞

5

∞

∞

3

∞

∞∞

1

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

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

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

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

VRTypeadj;//VRType是頂點關(guān)系類型。

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

//對帶權(quán)圖，則為權(quán)值類型。

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

VertexTypevexs[MAX_VERTEX_NUM];//頂點信息

AdjMatrixarcs;//弧的信息

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

GraphKindkind;//圖的種類標志

}MGraph;

用鄰接矩陣表示的圖的存儲表示(continue)typedefstruct{//圖的定義用鄰接矩陣表StatusCreateUDN(Mgraph&G){//用鄰接矩陣表示returnOK;}例：用鄰接矩陣生成無向網(wǎng)的算法（參見教材P162）scanf(&G.vexnum,&G.arcnum,&IncInfo);//輸入總頂點數(shù)，總弧數(shù)和信息for(i=0;i<G.vexnum,;++i)scanf(&G.vexs[i]);//輸入頂點值，存入一維向量中for(i=0;i<G.vexnum;++i)//對鄰接矩陣n*n個單元初始化，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);//找到兩頂點在矩陣中的位置(n次)

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

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

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

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

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

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

個單鏈表鏈接的邊都是頂點i

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

個單鏈表鏈接的邊都是進入頂點

i

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

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

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

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

鄰接表表示的圖的存儲結(jié)構(gòu)（P163）//圖的定義鄰接表表示的圖的存儲結(jié)構(gòu)（P163）圖的操作在鄰接連表的上的實現(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()找某頂點的所有鄰接點的時間復(fù)雜度是O(e)圖的操作在鄰接連表的上的實現(xiàn)找某頂點的所有鄰接點的時間復(fù)雜度如何建立鄰接表（以有向圖為例）算法思想：首先將鄰接表表頭數(shù)組初始化，vertex域初始化為i，firstarc初始化為NULL；然后對讀入的每一條弧<i,j>，產(chǎn)生一個表結(jié)點，adjver域置為j，并將結(jié)點鏈接到鄰接表的第i個鏈表中。如何建立鄰接表（以有向圖為例）算法思想：算法如下：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)系：都可以用來存儲有向圖和無向圖；鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：①鄰接矩陣是順序結(jié)構(gòu)，鄰接表是鏈式結(jié)構(gòu)②對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)討論：鄰接表與鄰接矩陣的比較1.聯(lián)系：都可以用來存儲有向圖三、鄰接多重表(無向圖的一種存儲結(jié)構(gòu))在無向圖的鄰接表中,一條邊出現(xiàn)兩個單鏈表中.浪費空間，也給某種操作帶來了困難。在鄰接多重表中，每一條邊只有一個結(jié)點(稱邊結(jié)點)為有關(guān)邊的處理提供了方便。三、鄰接多重表(無向圖的一種存儲結(jié)構(gòu))在無向圖的鄰接表中

markivexjvexilinkjlink其中:mark

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

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

其中:data

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

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

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

tailvex表示該弧的弧尾頂點在圖中的位置；

headvex表示該弧的弧頭頂點在圖中的位置；

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

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

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

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

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

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

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

被訪問，就立即讓visited[i]

為1，防止它被多次訪問。7.3圖的遍歷圖中可能存在回路，在訪問完某個頂點之后可能會沿著某些邊又回到DFS算法思想：深度優(yōu)先搜索DFS(DepthFirstSearch)從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至V0的所有鄰接點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。DFS算法思想：深度優(yōu)先搜索DFS(DepthFirs深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例深度優(yōu)先遍歷生成樹深度優(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ù)中增加一計數(shù)器sum，初值為n，每訪問一次就減1,減到0則return，可避免遞歸時間過長。圖的深度優(yōu)先遍歷算法在遞歸函數(shù)中增加一計數(shù)器sum，初值為n在鄰接矩陣A上實現(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上實現(xiàn)圖的深度優(yōu)先遍歷算法在鄰接鏈表上實現(xiàn)

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

p=ghead[v]->firstArc;

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

p=p->next;

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

//第一個頂點入棧并訪問Visit(v);visit[v]=1;push(s,v);//當棧不空時做

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

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

pop(s,v);}//while}Dfs1(Graphg,intv){//利用棧實現(xiàn)非遞V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc2783^^^adjvexnext55641^51282^678678736354^^^V3V7V6V2V5V8V4V1V2V4V5V3V7V6V8例深度遍歷：V112341V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1V3V7V6V2V4V8V5V1V2V4V5V3V7V6V8例12341342vexdaDFS算法效率分析:

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

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

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

for(v=0;v<G.vexnum;v++)visited[v]=0;//清訪問標記

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

for(v=0;v<G.vexnum;v++)//對每一個頂點vif(!visited[v]){visited[v]=1;visit(v);//訪問v;標記v;EnQueue(Q,v);//v未被訪問

while(!QueueEmpty(Q))

{

//Q不空

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

if(!visited[w]){visited[w]=1;visit(w);EnQueue(w);//將u的每個未被訪問的鄰接點w入隊

}//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)的總時間代價為d0+d1+…+dn-1=O(e)，其中的di是頂點i的度如果使用鄰接矩陣，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。廣度優(yōu)先搜索BFSDFS與BFS之比較：空間復(fù)雜度相同，都是O(n)(借用了堆?；蜿犃校?；時間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。算法分析:如果使用鄰接表表示圖，則循環(huán)的總時間代價為d0+1.求一條從頂點i到頂點s的簡單路徑2.

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

b

adhce

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

b

chdae

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

visited[v]=TRUE;//訪問第v個頂點

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

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

}

Append(PATH,getVertex(v));

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

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

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

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

312475

Q.front

Q.rear321475689例如:求下圖中頂點3至頂點5的一條最短路徑。隊列用雙7.4圖的連通性問題對無向連通圖進行遍歷得到的將是一個極小連通子圖，即圖的生成樹！由深度優(yōu)先搜索得到的生成樹，稱為深度優(yōu)先搜索生成樹。由廣度優(yōu)先搜索得到的生成樹，稱為廣度優(yōu)先搜索生成樹。對非連通圖進行遍歷，得到的將是各連通分量的生成樹，即圖的生成森林！7.4.1無向圖的連通分量和生成樹7.4圖的連通性問題對無向連通圖進行遍歷得到的將是一個極例1：畫出下圖的生成樹DFS生成樹v0v1v2v4v4v3鄰接表01234^1334^142^0v4v3v2v1v023^142^0v0v2v1v4v3BFS生成樹v0v1v3v2v4無向連通圖例1：畫出下圖的生成樹DFS生成樹v0v1v2v4v4v3DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連通子圖）求解步驟：Step1:先求出鄰接矩陣或鄰接表；Step2:寫出DFS或BFS結(jié)果序列；Step3:畫出對應(yīng)子圖或生成森林。我們選用鄰接表方式來求深度優(yōu)先搜索生成森林DEABCFJLMGHIK例2：畫出下圖的生成森林（或極小連1155M12L11K10J9I8H7G6F5E4D3C2B1A012^^0^120^0^4^378^106^6^1011^126^709^1219^111^1229^47^10811DEGHIK子圖1：再寫出DFS結(jié)果（3次）ABMJLCFDEGHKIABCFJLM先寫出鄰接表（或鄰接矩陣）：子圖2：子圖3：極小連通！1155M12L11K10J9I8H7G6F5E4D3C2BDEGHIK子圖(或連通分量)ABCFJLMABCFJLMDEGHIK生成森林DEGHIK子圖ABCFJLMABCFJLMDEGHIK生成求連通分量的算法（生成森林用對應(yīng)的二叉樹存儲）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));//生成樹的根*p={GetVex(G,v),NULL,NULL}if(!T)T=p;//森林空，p是第一棵樹

elseq->nextsibling=p;q=p;//q當前森林中最后一棵樹的根

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

}//if}//求連通分量的算法（生成森林用對應(yīng)的二叉樹存儲）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));//生成樹的根*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有向圖的強連通分量

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

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

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

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

Prim算法

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

};2.在U和V-U之間選最小邊（u,v），將v加入U，將(u,v)加入TE中;3.重復(fù)2直到U=V(或n-1次)1、普里姆(Prim)算法普里姆算法的基本思想（是一種貪婪算普里姆(Prim)算法過程示例1237456281612222510251418普里姆(Prim)算法過程示例1237456281612221237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P1237456281612222510251418普里姆(Prim)算法過程示例1237456281612222510251418普里姆(P設(shè)置一個輔助數(shù)組closedge[]，對每個頂點viV－U,存在分量closedge[i-1],有兩個域，Lowcost=Min{cost(u,vi)|uU}adjvex:

存儲與該邊關(guān)聯(lián)的U中頂點Prime算法的實現(xiàn)輔助數(shù)組closedge說明如下:Struct{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];設(shè)置一個輔助數(shù)組closedge[]，對每個頂點viV細化的普里姆(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的鄰接點w的lowcost值，規(guī)則是：如果closedge[w].lowcost>adj.matrix[k][w]則：closedge[w].lowcost=adj.matrix[k][w]細化的普里姆(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為頂點u的序號for(v=0;v<G.vexnum;v++)if(v!=k)closedge[v]={u,G.arcs[k][j].adj};closedge[k].lowcost=0;//第k個頂點加入在U集合中

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

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

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

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

a

和頂點c

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

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

DFSArticul(G,v);

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

if

(count<G.vexnum)

{

//生成樹的根有至少兩棵子樹

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

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

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

其中:頂點w

是生成樹上頂點v

的孩子;頂點k

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

visited記錄深度優(yōu)先遍歷時的訪問次序

若對頂點v，在生成樹上存在一個子樹根w,

且

low[w]≥visited[v]

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

2.遍歷過程中求得

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

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

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

//檢查v0的每個鄰接點low[v0]