數(shù)據(jù)結(jié)構(gòu)圖的遍歷與連通性參考用

數(shù)據(jù)結(jié)構(gòu)圖的遍歷與連通性參考用第一頁(yè)，共三十頁(yè)，編輯于2023年，星期三鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系(即弧或邊的權(quán))的矩陣。鄰接表類(lèi)似樹(shù)的孩子鏈表。即對(duì)圖中的每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，表中結(jié)點(diǎn)表示依附于該頂點(diǎn)vi的邊或弧。鄰接點(diǎn)域鏈域數(shù)據(jù)域數(shù)據(jù)域鏈域表結(jié)點(diǎn)表頭結(jié)點(diǎn)第二頁(yè)，共三十頁(yè)，編輯于2023年，星期三V1V3V2V4例：432121∧113∧4∧4∧2第三頁(yè)，共三十頁(yè)，編輯于2023年，星期三3.有向圖的十字鏈表存儲(chǔ)表示兩種結(jié)點(diǎn)結(jié)構(gòu)：尾域tailvex頭域headvex鏈域hlink鏈域tlink信息域info數(shù)據(jù)域data鏈域firstin鏈域firstout頂點(diǎn)結(jié)點(diǎn)弧結(jié)點(diǎn)第四頁(yè)，共三十頁(yè)，編輯于2023年，星期三v1v2v3v4012310/\20v3v1v4v2/\03/\13/\/\2302/\/\32例：datafirstinfirstouttailvexheadvexhlinktlink/\第五頁(yè)，共三十頁(yè)，編輯于2023年，星期三標(biāo)志域邊頂點(diǎn)i邊頂點(diǎn)j鏈域i鏈域j信息域數(shù)據(jù)域邊鏈域4.無(wú)向圖的鄰接多重表存儲(chǔ)表示邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)第六頁(yè)，共三十頁(yè)，編輯于2023年，星期三1

3

4

2

例：1234121^3^2^4^第七頁(yè)，共三十頁(yè)，編輯于2023年，星期三第7章圖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最短路徑第八頁(yè)，共三十頁(yè)，編輯于2023年，星期三7.3圖的遍歷從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次。這一過(guò)程就叫做圖的遍歷。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索廣度優(yōu)先搜索第九頁(yè)，共三十頁(yè)，編輯于2023年，星期三1.深度優(yōu)先搜索(DFS)基本思想：從圖中某頂點(diǎn)V0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)；重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。第十頁(yè)，共三十頁(yè)，編輯于2023年，星期三例：從頂點(diǎn)v1出發(fā)，DFS下圖。頂點(diǎn)訪問(wèn)序列為：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7第十一頁(yè)，共三十頁(yè)，編輯于2023年，星期三圖的DFS算法一般描述intvisited[MAXVEX];//訪問(wèn)標(biāo)志數(shù)組voidDFSgraph(GraphG,Visit())

{

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

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;

//訪問(wèn)標(biāo)志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);

//對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS}第十二頁(yè)，共三十頁(yè)，編輯于2023年，星期三voidDFS(GraphG,intv){//從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisited[v]=TRUE;Visit(v);//訪問(wèn)第v個(gè)頂點(diǎn)

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

//對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS

}第十三頁(yè)，共三十頁(yè)，編輯于2023年，星期三用鄰接表實(shí)現(xiàn)圖的深度優(yōu)先搜索v1v6v2v5v3v8v4v7v9v101234567828^28^37^36^45^23^

23^167^145^910

9/\10/\第十四頁(yè)，共三十頁(yè)，編輯于2023年，星期三分析：在遍歷圖時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFS函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問(wèn)，就不再?gòu)乃霭l(fā)進(jìn)行搜索。因此，遍歷圖的過(guò)程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過(guò)程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。第十五頁(yè)，共三十頁(yè)，編輯于2023年，星期三2.廣度優(yōu)先搜索(BFS)基本思想：從圖中某個(gè)頂點(diǎn)V0出發(fā)，并在訪問(wèn)此頂點(diǎn)后依次訪問(wèn)V0的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問(wèn)的先后次序依次訪問(wèn)它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)；重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。第十六頁(yè)，共三十頁(yè)，編輯于2023年，星期三例：從頂點(diǎn)v1出發(fā)，BFS下圖。頂點(diǎn)訪問(wèn)序列為：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7第十七頁(yè)，共三十頁(yè)，編輯于2023年，星期三用鄰接表實(shí)現(xiàn)圖的廣度優(yōu)先搜索12345678

28^28^3

7^3

6^45^2

3

^

23^167^145^v1v6v2v5v3v8v4v7第十八頁(yè)，共三十頁(yè)，編輯于2023年，星期三BFS非遞歸算法voidBFSTraverse(GraphG,Status(*Visit)(intv)){//使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited[v]for(v=0;v<G.vexnum;++v)visited[v]=FALSE;InitQueue(Q);//置空的輔助隊(duì)列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未訪問(wèn)visited[v]=TRUE;Visit(v);EnQueue(Q,v);//v入隊(duì)第十九頁(yè)，共三十頁(yè)，編輯于2023年，星期三

while(!QueueEmpty(Q)){DeQueue(Q,u);//隊(duì)頭元素出隊(duì)并置為u

for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)）if(!visited[w]){

//w為u的尚未訪問(wèn)的鄰接頂點(diǎn)visited[w]=TRUE;Visit(w);EnQueue(Q,w);}//if

}//while}if}//BFSTraverse第二十頁(yè)，共三十頁(yè)，編輯于2023年，星期三分析：每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程實(shí)質(zhì)上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，因此廣度優(yōu)先搜索遍歷圖的時(shí)間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問(wèn)的順序不同。第二十一頁(yè)，共三十頁(yè)，編輯于2023年，星期三第7章圖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最短路徑第二十二頁(yè)，共三十頁(yè)，編輯于2023年，星期三7.4圖的連通性問(wèn)題1）無(wú)向圖的連通分量和生成樹(shù)2）最小生成樹(shù)3）普里姆算法4）克魯斯卡爾算法第二十三頁(yè)，共三十頁(yè)，編輯于2023年，星期三1.無(wú)向圖的連通分量和生成樹(shù)基本概念連通分量的頂點(diǎn)集：即從該連通分量的某一頂點(diǎn)出發(fā)進(jìn)行搜索所得到的頂點(diǎn)訪問(wèn)序列；生成樹(shù)：某連通分量的極小連通子圖；生成森林：非連通圖的各個(gè)連通分量的極小連通子圖構(gòu)成的集合。第二十四頁(yè)，共三十頁(yè)，編輯于2023年，星期三設(shè)E(G)為連通子圖G中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)分成兩個(gè)集合T(G)和B(G)，其中T(G)是遍歷過(guò)程中歷經(jīng)的邊的集合。顯然，T(G)和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖，按照7.1節(jié)的定義，它是連通圖的一棵生成樹(shù)，并且稱(chēng)由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹(shù)；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹(shù)。第二十五頁(yè)，共三十頁(yè)，編輯于2023年，星期三例：求下圖的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。v1v6v2v5v3v8v4v7第二十六頁(yè)，共三十頁(yè)，編輯于2023年，星期三對(duì)非連通圖，每個(gè)連通分量中的頂點(diǎn)集和遍歷時(shí)走過(guò)的邊一起構(gòu)成若干棵生成樹(shù)，這些連通分量的生成樹(shù)組成非連通圖的生成森林。例：第二十七頁(yè)，共三十頁(yè)，編輯于2023年，星期三生成非連通圖的深度優(yōu)先生成森林的算法voidDFSForest(GraphG，CSTree&T){//建立無(wú)向圖G的深度優(yōu)先生成森林的(左)孩子(右)兄弟鏈表T。T=NULL；for(v=0；v<G.vexnum；++v)visited[v]=FALSE；for(v=0；v<G.vexnum；++v)if(!visited[v]){//第v頂點(diǎn)為新的生成樹(shù)的根結(jié)點(diǎn)p=(CSTree)malloc(sizeof(CSNode))//分配根結(jié)點(diǎn)*p={GetVex(G，v)，NULL，NULL}；//給該結(jié)點(diǎn)賦值if(!T)T=p；//是第一棵生成樹(shù)的根(T的根)elseq—>nextsibling=p;

//是其它生成樹(shù)的根(前一棵的根的“兄弟”)q=p;//q指示當(dāng)前生成樹(shù)的根

DFSTree(G,v,p);//建立以p為根的生成樹(shù)}}//DFSForest第二十八頁(yè)，共三十頁(yè)，編輯于2023年，星期三voidDFSTree(GraphG，intv，CSTree&T){//從第v個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖Q，建立以T為根的生成樹(shù)。visited[v]=TRUE；first=TRUE；for(w=FisrtAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))if(!visited[w]){p=(CSTree)malloc(sizeof(CSNode));//分配孩子結(jié)點(diǎn)*p={GetVex(G,w)，NULL，NULL}；if(first){//w是v的第一個(gè)未被訪問(wèn)的鄰接頂點(diǎn)T—>lchild=p；first=FALSE；//是根的左孩子結(jié)點(diǎn)}else{//w是v的其它未被訪問(wèn)的鄰接頂點(diǎn)q—>nextsibling=p；//是上一鄰接頂點(diǎn)的右兄弟結(jié)點(diǎn)}q=p；DFSTree(G,w,q)；