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

7.2圖的存儲結(jié)構(gòu)圖的數(shù)組(鄰接矩陣)存儲表示圖的鄰接表存儲表示有向圖的十字鏈表存儲表示無向圖的鄰接多重表存儲表示鄰接矩陣是用于描述圖中頂點之間關(guān)系(即弧或邊的權(quán))的矩陣。鄰接表類似樹的孩子鏈表。即對圖中的每個頂點vi建立一個單鏈表，表中結(jié)點表示依附于該頂點vi的邊或弧。鄰接點域鏈域數(shù)據(jù)域數(shù)據(jù)域鏈域表結(jié)點表頭結(jié)點V1V3V2V4例：432121∧113∧4∧4∧2v1v2v3v4012310/\20v3v1v4v2/\03/\13/\/\2302/\/\32例：datafirstinfirstouttailvexheadvexhlinktlink/\標志域邊頂點i邊頂點j鏈域i鏈域j信息域數(shù)據(jù)域邊鏈域4.無向圖的鄰接多重表存儲表示邊結(jié)點頂點結(jié)點1

3

4

2

例：1234121^3^2^4^7.3圖的遍歷從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷。通常有兩條遍歷圖的路徑：深度優(yōu)先搜索廣度優(yōu)先搜索1.深度優(yōu)先搜索(DFS)基本思想：從圖中某頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點；重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。例：從頂點v1出發(fā)，DFS下圖。頂點訪問序列為：v1,v2,v4,v8,v5,v3,v6,v7v1v6v2v5v3v8v4v7voidDFS(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

}用鄰接表實現(xiàn)圖的深度優(yōu)先搜索v1v6v2v5v3v8v4v7v9v101234567828^28^37^36^45^23^

23^167^145^910

9/\10/\分析：在遍歷圖時，對圖中每個頂點至多調(diào)用一次DFS函數(shù)，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結(jié)構(gòu)。例：從頂點v1出發(fā)，BFS下圖。頂點訪問序列為：v1,v2,v3,v4,v5,v6,v7,v8v1v6v2v5v3v8v4v7用鄰接表實現(xiàn)圖的廣度優(yōu)先搜索12345678

28^28^3

7^3

6^45^2

3

^

23^167^145^v1v6v2v5v3v8v4v7BFS非遞歸算法voidBFSTraverse(GraphG,Status(*Visit)(intv)){//使用輔助隊列Q和訪問標志數(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入隊分析：每個頂點至多進一次隊列。遍歷圖的過程實質(zhì)上是通過邊或弧找鄰接點的過程，因此廣度優(yōu)先搜索遍歷圖的時間復(fù)雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅在于對頂點訪問的順序不同。第7章圖7.1圖的定義和術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問題7.5有向無環(huán)圖及其應(yīng)用7.6最短路徑7.4圖的連通性問題1）無向圖的連通分量和生成樹2）最小生成樹3）普里姆算法4）克魯斯卡爾算法設(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)先生成樹。例：求下圖的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。v1v6v2v5v3v8v4v7voidDFSTree(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)；

//從第w個頂點出發(fā)深度優(yōu)先遍歷圖G，建立子生成樹q}//if}//DFSTree1.理解并掌握圖的深度優(yōu)先搜