图的深度优先搜索遍历（DFS）类似于二叉树的先序遍历。它的基本思想是：首先访问出发点v，并将其标记为已访问过；然后选取与v邻接的未被访问的任意一个顶点w，并访问它；再选取与w邻接的未被访问的任一顶点并访问，以此重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个并重复上述访问过程，直至图中所有顶点都被访问过为止。图7-8所示即为一个图的深度优先搜索遍历过程。

图7-8 深度优先搜索遍历过程

算法执行过程：任取一个顶点，访问之，然后检查这个顶点的所有邻接顶点，递归访问其中未被访问过的顶点。

以邻接表为存储结构的图的深度优先搜索遍历算法如下：

(www.daowen.com)

与图的DFS算法对照，再次写出二叉树的先序遍历算法，具体如下：

说明：前边提到图的深度优先搜索遍历类似于二叉树的先序遍历。上面再次写出了二叉树的先序遍历算法代码，对比一下，这种相似到底体现在哪里？二叉树的先序遍历代码中，（2）和（3）两句为递归访问当前结点的两个分支，对应于图的深度优先搜索遍历代码中就是while循环内的语句（1），实现了递归地访问当前顶点的多个分支，两者十分相似。图的深度优先搜索遍历和二叉树的先序遍历的区别只是在于：二叉树的先序遍历对于每个结点要递归地访问两个分支，图的深度优先搜索遍历则是要递归地访问多个分支。

把图的深度优先搜索遍历过程中所经历的边保留，其余的边删掉，就会形成一棵树，称为深度优先搜索生成树。