|
和樹的遍歷相似，若從圖中某頂點(diǎn)出發(fā)訪遍圖中每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問一次，此過程稱為圖的遍歷(Traversing Graph)。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。圖的遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。對(duì)每種搜索順序，訪問各頂點(diǎn)的順序也不是唯一的。 1、鄰接表及逆鄰接表的存儲(chǔ)方法 （1）定義 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用單鏈表中的一個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條?。?，稱為邊（或?。┙Y(jié)點(diǎn)。特征如下： 1) 為每個(gè)頂點(diǎn)建立一個(gè)單鏈表， 2) 第i個(gè)單鏈表中包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。 把同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，鏈表的每一個(gè)結(jié)點(diǎn)代表一條邊，叫做表結(jié)點(diǎn)（邊結(jié)點(diǎn)），鄰接點(diǎn)域adjvex保存與該邊相關(guān)聯(lián)的另一頂點(diǎn)的頂點(diǎn)下標(biāo) ， 鏈域nextarc存放指向同一鏈表中下一個(gè)表結(jié)點(diǎn)的指針
，數(shù)據(jù)域info存放邊的權(quán)。邊鏈表的表頭指針存放在頭結(jié)點(diǎn)中。頭結(jié)點(diǎn)以順序結(jié)構(gòu)存儲(chǔ)，其數(shù)據(jù)域da 
帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值。 頂點(diǎn) Vi 的邊鏈表的頭結(jié)點(diǎn)存放在下標(biāo)為 i 的頂點(diǎn)數(shù)組中。 在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。 設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則用鄰接表表示無(wú)向圖時(shí)，需要 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，2e 個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，e 個(gè)邊結(jié)點(diǎn)。 建立鄰接表的時(shí)間復(fù)雜度為O(n*e)。若頂點(diǎn)信息即為頂點(diǎn)的下標(biāo)，則時(shí)間復(fù)雜度為O(n+e)。 （2）鄰接表的示例及逆鄰接表
在有向圖的鄰接表中，第 i 個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi的出度，表結(jié)點(diǎn)的adjvex存儲(chǔ)的是以當(dāng)前頭結(jié)點(diǎn)為弧尾的弦。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的入度。 在有向圖的逆鄰接表中，第 i 個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi 的入度，表結(jié)點(diǎn)的adjvex存儲(chǔ)的是以當(dāng)前頭結(jié)點(diǎn)為弧首的弦。 如下為帶權(quán)圖的鄰接表：
2、深度優(yōu)先算法思想 深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作： （1）訪問搜索到的未被訪問的鄰接點(diǎn)； （2）將此頂點(diǎn)的visited數(shù)組元素值置1； （3）搜索該頂點(diǎn)的未被訪問的鄰接點(diǎn)，若該鄰接點(diǎn)存在，則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索。 深度優(yōu)先搜索DFS可描述為： （1）訪問v0頂點(diǎn)； （2）置 visited[v0]=1； （3）搜索v0未被訪問的鄰接點(diǎn)w，若存在鄰接點(diǎn)w，則DFS(w)。 遍歷過程： DFS 在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；再?gòu)?/span> w1 出發(fā)，訪問與 w1鄰 接但還沒有訪問過的頂點(diǎn) w2；然后再?gòu)?/span> w2 出發(fā)，進(jìn)行類似的訪問，… 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。 接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。如下圖所示：
3、深度優(yōu)先算法C語(yǔ)言描述
4、深度優(yōu)先算法C語(yǔ)言實(shí)現(xiàn) #include "stdio.h" #define MAX_VERTEX_NUM 10 #include "conio.h" #include "stdlib.h"
typedef char VertexType;
typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; //表結(jié)點(diǎn)類型
typedef struct VNode{ VertexType
da ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; //頭結(jié)點(diǎn)
typedef struct{ AdjList vertices; //鄰接表 int vexnum,arcnum; }ALGraph;
int visited[MAX_VERTEX_NUM];
int LocateVex(ALGraph G,char u) { int i; for (i=0;i<G.vexnum;i++)
{ if(u==G.vertices[i].da if (i==G.vexnum) {printf("Error u!\n");exit(1);} return 0; }
void CreateALGraph_adjlist(ALGraph &G) { int i,j,k,w; char v1,v2,enter; ArcNode *p; printf("Input vexnum & arcnum:\n"); scanf("%d",&G.vexnum); scanf("%d",&G.arcnum); printf("Input Vertices:\n"); for (i=0;i<G.vexnum;i++) { scanf("%c%c",&enter,&G.vertices[i].da G.vertices[i].firstarc=NULL; }//for
printf("Input Arcs(v1,v2,w)以回車分開各個(gè)數(shù)據(jù):\n"); for (k=0;k<G.arcnum;k++) { scanf("%c%c",&enter,&v1); scanf("%c%c",&enter,&v2); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; p->info = w; p->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p; }//for return; }//CreateALGraph_adjlist
void DFS(ALGraph &G, int v) { ArcNode *p;
printf("%c",G.vertices[v].da visited[v]=1; p=G.vertices[v].firstarc; while (p) { if (!visited[p->adjvex]) DFS(G,p->adjvex); p=p->nextarc; } } //從第v個(gè)頂點(diǎn)出發(fā)DFS
void DFSTraverse(ALGraph &G) { for (int v=0;v<G.vexnum;++v) visited[v]=0; for (int v=0;v<G.vexnum;++v) if (!visited[v]) DFS(G,v); }//DFSTraverse
int main() { ALGraph G; CreateALGraph_adjlist(G); DFSTraverse(G); } 5、注意點(diǎn) （1）強(qiáng)制轉(zhuǎn)換：p=(char*)&a; （2）字符輸入中，賦值順序和緩存的聯(lián)系 scanf是從標(biāo)準(zhǔn)輸入緩沖區(qū)中讀取輸入的數(shù)據(jù)，如果連續(xù)輸入兩個(gè)%c格式的字符，而中間又要涉及回車，那么第二個(gè)字符將被賦予回車。 解決辦法： 1、清空輸入緩沖區(qū) 第一個(gè)scanf后加入語(yǔ)句：fflush(stdin); //C語(yǔ)言清空輸入緩沖區(qū)函數(shù) 2、格式控制中加入空格 將第二個(gè)scanf改為：scanf(" %c",&ch2);//在%號(hào)前面加一個(gè)空格 scanf格式輸入時(shí)要求輸入格式與格式控制符中的完全一樣(如：scanf("abcd%c",&ch);輸入時(shí)必須輸入abcde,ch得到的值為e)空格可以抵消前面輸入的回車符。 3、直接用ch=getche()吸收回車 4、當(dāng)輸入完整數(shù)或字符時(shí)，后面還需要輸入字符時(shí)，為了避免輸入的字符變成回車符，可以在輸入字符前多加一條scanf語(yǔ)句來吃掉前面的回車符。此時(shí)用來吃掉回車符的scanf輸入可以用%c方式，也可以用%d方式。當(dāng)用%c方式來吃掉回車符時(shí)，回車符被讀進(jìn)了char類型變量中，當(dāng)用%d方式來吃掉回車符時(shí)，回車符并沒有被送進(jìn)int類型變量中，而是在異常的字符輸入后，被自動(dòng)清除了。 （3）我們這里，對(duì)圖中各個(gè)頂點(diǎn)以單個(gè)字符來處理，當(dāng)然也可以字符串來進(jìn)行。對(duì)各個(gè)節(jié)點(diǎn)的訪問，也僅僅是輸出他們的節(jié)點(diǎn)名，當(dāng)然還可以進(jìn)一步的操作。 |
|
|
