图的深度优先遍历思想是：

从图中某结点出发，访问其某一相邻结点，再访问该结点的相邻结点，直至访问完所有的结点。

形象的比喻就是：一条路走到头，回头再走没走过的路。

可见，深度优先遍历是一种递归思想；

需要注意的是：

对于图的邻接矩阵存储和邻接表存储，深度优先遍历输出的次序有有一定去别的。

对于邻接矩阵而言，DFS和BFS得到的序列是唯一的；

对于邻接表而言，DFS和BFS输入的序列不同，得到的输出序列也不相同。

深度优先遍历的核心算法 ：

void DFS(GraAdList G, int v) {EdgeNode* p;int j;cout << G.AdList[v].data << " ";visited[v] = 1;p = G.AdList[v].first;while (p){j = p->adjvex;if (visited[j] == 0){DFS(G, j);}p = p->next;}
}
void DFS(GraAdList G)
{for (int i = 0; i < G.vexnum; i++){if (visited[i] == 0){DFS(G, i);}}
}

完整代码实现：

#include<iostream>
using namespace std;
#define MAX 6
int visited[MAX];
int D[MAX] = { 9999 };
typedef struct EdgeNode {int adjvex;EdgeNode* next;
};
typedef struct VexNode {char data;EdgeNode* first;
};
typedef struct GraAdList {VexNode AdList[MAX];int vexnum;int edgenum;
};
//创建邻接矩
void Creat(GraAdList& G) {int i, j, k;EdgeNode* e = NULL;EdgeNode* q = NULL;cout << "请输入顶点数和边数： " << endl;cin >> G.vexnum >> G.edgenum;cout << "请输入顶点信息" << endl;for (k = 0; k < G.vexnum; k++){cin >> G.AdList[k].data;G.AdList[k].first = NULL;}for (k = 0; k < G.edgenum; k++){cout << "请输入边(vi,vj)的下标i,j： " << endl;cin >> i >> j;e = new EdgeNode;e->adjvex = j;e->next = G.AdList[i].first;G.AdList[i].first = e;}
}
void myprint(GraAdList G) {cout << endl << "邻接表: " << endl;EdgeNode* p;for (int i = 0; i < G.vexnum; i++){cout << G.AdList[i].data << ": ";for (p = G.AdList[i].first; p; p = p->next){cout << p->adjvex << " ";}cout << endl;}
}
void DFS(GraAdList G, int v) {EdgeNode* p;int j;cout << G.AdList[v].data << " ";visited[v] = 1;p = G.AdList[v].first;while (p){j = p->adjvex;if (visited[j] == 0){DFS(G, j);}p = p->next;}
}
void DFS(GraAdList G)
{for (int i = 0; i < G.vexnum; i++){if (visited[i] == 0){DFS(G, i);}}
}
int main() {GraAdList G;Creat(G);myprint(G);for (int i = 0; i < G.vexnum; i++){visited[i] = 0;}cout << endl << "深度遍历： " << endl;DFS(G, 0);return 0;
}

执行结果：

我创建的图：