1. DFS遍历
DFS 算法的思想：对一个无向连通图，在访问图中某一起始顶点 v 后，由 v 出发，访问它的某一邻接顶点 w1；再从 w1 出发，访问与 w1 邻接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问；…；如此进行下去，直至到达所有邻接顶点都被访问过的顶点 u 为止；接着，回退一步，回退到前一次刚访问过的顶点，看是否还有其它没有被访问过的邻接顶点，如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再回退一步进行类似的访问。重复上述过程，直到该连通图中所有顶点都被访问过为止。
对上图示的无向连通图， 采用 DFS 思想搜索的过程为（在图(a)中，实线表示前进方向，虚线表示回退方向，箭头旁的数字跟下面的序号对应）：
- 从顶点 A 出发，访问顶点序号最小的邻接顶点，即顶点 B；
- 然后访问顶点 B 的未访问过的、顶点序号最小的邻接顶点，即顶点 C；
- 接着访问顶点 C 的未访问过的、顶点序号最小的邻接顶点，即顶点 G；
- 此时顶点 G 已经没有未访问过的邻接顶点了，所以回退到顶点 C；
- 回退到顶点 C 后，顶点 C 也没有未访问过的邻接顶点了，所以继续回退到顶点 B；
- 顶点 B 还有一个未访问过的邻接顶点，即顶点 E，所以访问顶点 E；
- 然后访问顶点 E 的未访问过的、顶点序号最小的邻接顶点，即顶点 F；
- 顶点 F 有两个未访问过的邻接顶点，选择顶点序号最小的，即顶点 D，所以访问 D；
- 此时顶点 D 已经没有未访问过的邻接顶点了，所以回退到顶点 F；
- 顶点 F 还有一个未访问过的邻接顶点，即顶点 H，所以访问顶点 H；
- 然后访问顶点 H 的未访问过的、顶点序号最小的邻接顶点，即顶点 I；
- 此时顶点 I 已经没有未访问过的邻接顶点了，所以回退到顶点 H；
- 回退到顶点 H 后，顶点 H 也没有未访问过的邻接顶点了，所以继续回退到顶点 F；
- 回退到顶点 F 后，顶点 F 也没有未访问过的邻接顶点了，所以继续回退到顶点 E；
- 回退到顶点 E 后，顶点 E 也没有未访问过的邻接顶点了，所以继续回退到顶点 B；
- 回退到顶点 B 后，顶点 B 也没有未访问过的邻接顶点了，所以继续回退到顶点 A。
回退到顶点 A 后，顶点 A 也没有未访问过的邻接顶点了，而且顶点 A 是搜索的起始顶点。至此，整个搜索过程全部结束。由此可见， DFS 搜索最终要回退到起始顶点，并且如果起始顶点没有未访问过的邻接顶点了，则算法结束。
2. DFS 算法的实现
假设有函数 DFS(v)， 可实现从顶点 v 出发访问它的所有未访问过的邻接顶点。 在 DFS 算法中，必有一数组，设为 visited[n]，用来存储各顶点的访问状态。如果 visited[i] = 1，则表示顶点 i 已经访问过；如果 visited[i] = 0，则表示顶点 i 还未访问过。初始时，各顶点的访问状态均为 0。
如果用邻接表存储图，则 DFS 算法实现的伪代码如下：
DFS( 顶点 i ) //从顶点 i 进行深度优先搜索
{
visited[ i ] = 1; //将顶点 i 的访问标志置为 1
p = 顶点 i 的边链表表头指针;
while( p 不为空 )
{
//设指针 p 所指向的边结点所表示的边中，另一个顶点为顶点 j
if( 顶点 j 未访问过 )
{
//递归搜索前的准备工作需要在这里写代码
DFS( 顶点 j );
//以下是 DFS 的回退位置，在很多应用中需要在这里写代码
}
p = p->nextarc; //p 移向下一个边结点
}
}如果用邻接矩阵存储图（设顶点个数为 n），则 DFS 算法实现的伪代码如下：
DFS( 顶点 i ) //从顶点 i 进行深度优先搜索
{
visited[ i ] = 1; //将顶点 i 的访问标志置为 1
for( j=0; j<n; j++ ) //对其他所有顶点 j
{
//j 是 i 的邻接顶点，且顶点 j 没有访问过
if( Edge[i][j]==1 && !visited[j] )
{
//递归搜索前的准备工作需要在这里写代码
DFS( j ) //从顶点 j 出发进行 DFS 搜索
//以下是 DFS 的回退位置，在很多应用中需要在这里写代码
}
}
}在上述伪代码中，在递归调用 DFS 函数前后的两个位置特别重要：
- 如果需要在递归搜索前做一些准备工作，则需要在 DFS 递归调用前的位置写代码；
- 如果需要在搜索的回退后做一些还原工作，或者根据搜索结果做一些统计或计算工作，则需要在 DFS 递归调用后的位置写代码。
DFS的算法度分析：
现以下图(a)所示的无向图为例分析 DFS 算法的复杂度。设图中有 n 个顶点，有 m 条边。
如果用邻接表存储图，如图 (b)所示，从顶点 i 进行深度优先搜索，首先要取得顶点 i 的边链表表头指针，设为 p，然后要通过指针 p 访问它的第 1 个邻接顶点，如果该邻接顶点未访问过，则从这个顶点出发进行递归搜索；如果这个邻接顶点已经访问过，则指针 p 要移向下一个边结点。在这个过程中，对每个顶点递归访问 1 次，即每个顶点的边链表表头指针取出一次，而每个边结点都只访问了一次。由于总共有 2m 个边结点，所以扫描边的时间为 O(2m)。因此采用邻接表存储图时，进行深度优先搜索的时间复杂性为 O(n+2m)。
如果采用邻接矩阵存储图，由于在邻接矩阵中只是间接的存储了边的信息。在对某个顶点进行 DFS 搜索时，要检查其他每个顶点，包括它的邻接顶点和非邻接顶点，所需时间为 O(n)。例如在下图(b)中，执行 DFS(A)时，要在邻接矩阵中的第 0 行检查顶点 A～I 与顶点 A 是否相邻且是否已经访问过。另外，整个 DFS 过程，对每个顶点都要递归进行 DFS 搜索，因此遍历图中所有的顶点所需的时间为 O(n2)。
