首先數(shù)據(jù)結構(C語言版第二版)的關于深度優(yōu)先搜索遍歷連通圖的圖G4如下:

?使用鄰接表去創(chuàng)建上面這個無向圖，然后再使用書本DFS函數(shù)以及DFSTraverse函數(shù)實現(xiàn)深度優(yōu)先搜索遍歷

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 20
//下面三個結構體就是鄰接表的結構體，完全一樣的方式
typedef struct EdgeNode
{int adjvex;struct EdgeNode* next;
}EdgeNode;
typedef struct VertexNode
{char data;EdgeNode* firstedge;
}VertexNode;
typedef struct
{VertexNode adjlist[MAXVEX];int numVertexs;int numEdges;
}GraphAdjlist;
int visited[10];//一個標記數(shù)組，記錄遍歷過的不會重復遍歷
//創(chuàng)建鄰接表
void CreateALGraph(GraphAdjlist* G)
{int i, j, k;EdgeNode* p;printf("請輸入頂點數(shù)+邊數(shù)\n");scanf("%d%d", &G->numVertexs, &G->numEdges);getchar();//接收scanf殘留的換行符\nprintf("請輸入頂點的信息\n");for (i = 0; i < G->numVertexs; i++){scanf("%c", &G->adjlist[i].data);G->adjlist[i].firstedge = NULL;//初始化指向邊表的指針為null}for (k = 0; k < G->numEdges; k++){printf("請輸入(vi,vj)的頭，尾,一共有%d條\n", G->numEdges);scanf("%d%d", &i, &j);//我們這里是實現(xiàn)深度遍歷連通圖的無向圖p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = j;p->next = G->adjlist[i].firstedge;G->adjlist[i].firstedge = p;p = (EdgeNode*)malloc(sizeof(EdgeNode));p->adjvex = i;p->next = G->adjlist[j].firstedge;G->adjlist[j].firstedge = p;}printf("鄰接表創(chuàng)建成功\n");
}
void DFS(GraphAdjlist* G,int i)
{EdgeNode* p;visited[i] = 1;printf("%c ", G->adjlist[i].data);//先把這個頂點值輸出,有點類似樹的先序遍歷（根左右）p = G->adjlist[i].firstedge;while (p!=NULL){if (visited[p->adjvex] == 0){DFS(G, p->adjvex);}p = p->next;}
}
void DFSTraverse(GraphAdjlist* G)
{int i;for (i = 0; i < G->numVertexs; i++){visited[i] = 0;//全部初始為0，然后遍歷過的(vi,vj)就置為1 由未訪問 -> 已訪問}for (i = 0; i < G->numVertexs; i++){if (visited[i] == 0){DFS(G, i);}}
}
int main()
{GraphAdjlist G;CreateALGraph(&G);printf("深度遍歷如下\n");DFSTraverse(&G);return 0;
}

關于深度遍歷，很相似樹的前序遍歷(根左右),如果出現(xiàn)(根右左)，其實這個問題也就是鄰接表邊表插入結點的時候，我們使用的是頭插法，所以才有時候出現(xiàn)深度優(yōu)先遍歷會出現(xiàn)根右左，這個沒關系的，不重復遍歷就好?

下面是終端輸入內(nèi)容:

請輸入頂點數(shù)+邊數(shù)
8 9
請輸入頂點的信息
01234567
請輸入(vi,vj)的頭，尾,一共有9條
0 1
請輸入(vi,vj)的頭，尾,一共有9條
0 2
請輸入(vi,vj)的頭，尾,一共有9條
1 3
請輸入(vi,vj)的頭，尾,一共有9條
1 4
請輸入(vi,vj)的頭，尾,一共有9條
3 7
請輸入(vi,vj)的頭，尾,一共有9條
4 7
請輸入(vi,vj)的頭，尾,一共有9條
2 5
請輸入(vi,vj)的頭，尾,一共有9條
2 6
請輸入(vi,vj)的頭，尾,一共有9條
5 6
鄰接表創(chuàng)建成功
深度遍歷如下
0 2 6 5 1 4 7 3

下標全部+1就可以查看12345678的遍歷情況?

關于非連通圖，代碼通用的;

數(shù)據(jù)結構書本關于深度優(yōu)先搜索遍歷的非連通圖如下:

終端輸入內(nèi)容如下:?

請輸入頂點數(shù)+邊數(shù)
8 8
請輸入頂點的信息
01234567
請輸入(vi,vj)的頭，尾,一共有8條
0 1
請輸入(vi,vj)的頭，尾,一共有8條
1 3
請輸入(vi,vj)的頭，尾,一共有8條
1 4
請輸入(vi,vj)的頭，尾,一共有8條
3 7
請輸入(vi,vj)的頭，尾,一共有8條
4 7
請輸入(vi,vj)的頭，尾,一共有8條
2 5
請輸入(vi,vj)的頭，尾,一共有8條
2 6
請輸入(vi,vj)的頭，尾,一共有8條
5 6
鄰接表創(chuàng)建成功
深度遍歷如下
0 1 4 7 3 2 6 5

非連續(xù)圖中的邊數(shù)由9 -> 8?