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

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

3

4

2

例：1234121^3^2^4^第七頁，共三十頁，編輯于2023年，星期三第7章圖7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑第八頁，共三十頁，編輯于2023年，星期三7.3圖的遍歷從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索廣度優(yōu)先搜索第九頁，共三十頁，編輯于2023年，星期三1.深度優(yōu)先搜索(DFS)基本思想：從圖中某頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點；重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。第十頁，共三十頁，編輯于2023年，星期三例：從頂點v1出發(fā)，DFS下圖。頂點訪問序列為：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7第十一頁，共三十頁，編輯于2023年，星期三圖的DFS算法一般描述intvisited[MAXVEX];//訪問標(biāo)志數(shù)組voidDFSgraph(GraphG,Visit())

{

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

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

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

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

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

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

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

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

23^167^145^910

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

28^28^3

7^3

6^45^2

3

^

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

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

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

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

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

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

DFSTree(G,v,p);//建立以p為根的生成樹}}//DFSForest第二十八頁，共三十頁，編輯于2023年，星期三voidDFSTree(GraphG，intv，CSTree&T){//從第v個頂點出發(fā)深度優(yōu)先遍歷圖Q，建立以T為根的生成樹。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é)點*p={GetVex(G,w)，NULL，NULL}；if(first){//w是v的第一個未被訪問的鄰接頂點T—>lchild=p；first=FALSE；//是根的左孩子結(jié)點}else{//w是v的其它未被訪問的鄰接頂點q—>nextsibling=p；//是上一鄰接頂點的右兄弟結(jié)點}q=p；DFSTree(G,w,q)；