DFS 深度優(yōu)先遍歷?
DFS算法用于遍歷圖結(jié)構(gòu)蹦疑，旨在遍歷每一個(gè)結(jié)點(diǎn)西雀，顧名思義，這種方法把遍歷的重點(diǎn)放在深度上歉摧，什么意思呢艇肴？就是在訪問過的結(jié)點(diǎn)做標(biāo)記的前提下，一條路走到天黑叁温，我們都知道當(dāng)每一個(gè)結(jié)點(diǎn)都有很多分支再悼，那么我們的小人就沿著每一個(gè)結(jié)點(diǎn)走，定一個(gè)標(biāo)準(zhǔn)券盅，比如優(yōu)先走右手邊的路帮哈，然后在到達(dá)下一個(gè)結(jié)點(diǎn)前先敲敲門，當(dāng)一個(gè)結(jié)點(diǎn)的所有門都被敲了個(gè)遍都標(biāo)記過锰镀，那么就走回頭路，再重復(fù)敲門咖刃，直到返回起點(diǎn)泳炉，這樣的方式我們叫做 DFS 深度優(yōu)先遍歷，本文以圖結(jié)構(gòu)講解嚎杨，例子取自《大話數(shù)據(jù)結(jié)構(gòu)》花鹅。
如我剛才所講，從A點(diǎn)出發(fā)枫浙，將路徑畫出來就是以下效果刨肃。
實(shí)線是走過的路程，虛線就是我們的小人敲門然后發(fā)現(xiàn)標(biāo)記過的一個(gè)過程箩帚，大家可以寄幾模擬一哈真友。一句話總結(jié)就是：
從圖中某個(gè)頂點(diǎn) v 出發(fā)，訪問此頂點(diǎn)紧帕，然后從 v 的未被訪問的鄰接點(diǎn)出發(fā) 深度優(yōu)先遍歷圖結(jié)構(gòu)盔然，直至圖中所有和 v 有路徑相通的頂點(diǎn)都被訪問到桅打。
結(jié)構(gòu)定義代碼：
typedefchar VertexType;
typedef int EdgeType;#defineMAXVEX 10#defineINFINITY 65535typedef int boolean;
boolean visited[MAXVEX];
typedef struct{
? ? VertexType vexs[MAXVEX];
? ? EdgeType arc[MAXVEX][MAXVEX];
? ? intnumVertexes,numEdges;}MGraph;
鄰接矩陣創(chuàng)建：
voidCreateMGraph(MGraph *G)
{
? ? int i,j,k;
? ? printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（空格隔開）\n");
? ? scanf("%d %d",&G->numVertexes,&G->numEdges);
? ? printf("請(qǐng)依次輸入每個(gè)頂點(diǎn)的內(nèi)容：\n");
? ? for(i =0;i < G->numVertexes;i++)
? ? {
? ? ? ? scanf("%c",&G->vexs[i]);
? ? }
? ? for(i =0;i < G->numVertexes;i++)
? ? {
? ? ? ? for(j =0;j < G->numVertexes;j++)
? ? ? ? {
? ? ? ? ? ? G->arc[i][j] = INFINITY;
? ? ? ? }
? ? }
? ? for(k =0;k < G->numEdges;k++)
? ? {
? ? ? ? printf("輸入邊（vi,vj）上的下標(biāo)i，下標(biāo)j：\n");
? ? ? ? scanf("%d %d",&i,&j);
? ? ? ? G->arc[i][j] =1;
? ? ? ? G->arc[j][i] = G->arc[i][j];
? ? }
}
DFS算法
voidDFS(MGraph G,int i) //深度優(yōu)先遞歸算法
{
? ? int j;
? ? visited[i] =1;
? ? printf("%c",G.vexs[i]);
? ? for(j =0;j < G.numVertexes;j++)
? ? {
? ? ? ? if(G.arc[i][j] ==1&& !visited[j])
? ? ? ? ? ? DFS(G,j);
? ? }
}void DFStraverse(MGraph G)? //深度遍歷
{
? ? int i;
? ? for(i =0;i < G.numVertexes;i++)
? ? visited[i] =0;
? ? for(i =0;i < G.numVertexes;i++)
? ? {
? ? ? ? if(!visited[i])
? ? ? ? ? ? DFS(G,i);
? ? }
}
這種方法比較好理解在于使用循環(huán)進(jìn)入函數(shù)再遞歸愈案，可以保證以鄰接矩陣為儲(chǔ)存單位的每一個(gè)格子都被遍歷到挺尾，且做好標(biāo)注，那么用鄰接矩陣的DFS算法時(shí)間復(fù)雜度可以想見是 O（n2）
我們來看下一種實(shí)現(xiàn)方式站绪，這次我們使用的是鄰接單鏈表
結(jié)構(gòu)定義：
typedefint boolean;
boolean visited[MAXVEX];
typedef char VertexType;
typedef int EdgeType;#defineMAXVEX 10#defineINFINITY 65535typedef struct EdgeNode //邊表結(jié)構(gòu)點(diǎn)
{
? ? int adjvex;
? ? structEdgeNode *next;
}EdgeNode;
typedef struct VertexNode //頂點(diǎn)表結(jié)構(gòu)點(diǎn)
{
? ? VertexType data;
? ? EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];
typedef struct //總表結(jié)構(gòu)
{
? ? AdjList adjList;
? ? int numVertexes,numEdges;
}GraphAdjList;
比鄰接矩陣復(fù)雜一點(diǎn)遭铺，但是其結(jié)構(gòu)只有三種，總表恢准、定點(diǎn)表和邊表
創(chuàng)建：
voidCreateALGraph(GraphAdjList *G)
{
? ? int i,j,k;
? ? EdgeNode *e;
? ? printf("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)（空格隔開）\n");
? ? scanf("%d %d",&G->numVertexes,&G->numEdges);
? ? for(i =0;i < G->numVertexes;i++)
? ? {
? ? ? ? scanf("%c",&G->adjList[i].data);
? ? ? ? G->adjList[i].firstedge = NULL;
? ? }
? ? for(k =0;k < G->numVertexes;k++)
? ? {
? ? ? ? printf("輸入邊（vi,vj）上的下標(biāo)i魂挂，下標(biāo)j：\n");
? ? ? ? scanf("%d %d",&i,&j);
? ? ? ? e = (EdgeNode*)malloc(sizeof(EdgeNode));
? ? ? ? e->adjvex=i;
? ? ? ? e->next = adjList[j].firstedge;
? ? ? ? adjList[j].firstedge = e;
? ? ? ? e = (EdgeNode*)malloc(sizeof(EdgeNode));
? ? ? ? e->adjvex=j;
? ? ? ? e->next = adjList[i].firstedge;
? ? ? ? adjList[i].firstedge = e;
? ? }
}
DFS算法實(shí)現(xiàn)：
voidDFS(GraphAdjList GL,int i)
{
? ? EdgeNode *p;
? ? visited[i] =1;
? ? printf("%c",GL->adjList[i].data);
? ? while(p)
? ? {
? ? ? ? if(!visited[p->adjvex])
? ? ? ? ? ? DFS(GL,p->adjvex);
? ? ? ? p = p->next;
? ? }
}void DFStraverse(GraphAdjList GL)
{
? ? int i;
? ? for(i =0;i < GL->numVertexes;i++)
? ? visited[i] =0;
? ? for(i =0;i < GL->numVertexes;i++)
? ? {
? ? ? ? if(!visited[i])
? ? ? ? ? ? DFS(GL,i);
? ? }
}
利用鄰接表的方式能夠?qū)崿F(xiàn)相同效果的遍歷，同時(shí)這種方法的算法時(shí)間復(fù)雜度為 O（n+e）
顯然對(duì)于點(diǎn)多邊少的稀疏圖來說顷歌，鄰接表結(jié)構(gòu)使得算法在時(shí)間效率上大大提高锰蓬。
