本文实例讲述了图的遍历中深度优先搜索的C++实现方法，是一种非常重要的算法，具体实现方法如下：
首先，图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历主要有两种算法：广度优先搜索（Breadth-First-Search）和深度优先搜索（Depth-First-Search）。
一、深度优先搜索（DFS）的算法思想
深度优先搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想就是：首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直到图中所有顶点均被访问过为止。
如上图所示，从顶点2开始深度优先遍历图，结果为：2，0，1，3。
二、DFS算法实现
和广度优先搜索一样，为了防止顶点被多次访问，需要使用一个访问标记数组visited[]来标记顶点是否已经被访问过。
这里使用邻接表表示图。对于一个有向图，假设从给定顶点可以访问到图的所有其他顶点，则DFS递归算法的C++代码实现：
/*************************************************************************
> File Name: DFS.cpp
> Author: SongLee
************************************************************************/
#include
#include
using namespace std;
/* 图 */
class Graph
{
int V; // 顶点数
list *adj; // 邻接表
void DFSUtil(int v, bool visited[]); // 从顶点v深度优先遍历
public:
Graph(int V); // 构造函数
void addEdge(int v, int w); // 向图中添加边
void DFS(int v); // 从v开始深度优先遍历图
};
/* 构造函数 */
Graph::Graph(int V)
{
this->V = V;
adj = new list[V];
}
/* 添加边，构造邻接表 */
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // 将w添加到v的链表
}
/* 从v开始深度优先遍历 */
void Graph::DFSUtil(int v, bool visited[])
{
// 访问顶点v并输出
visited[v] = true;
cout