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