| 从图G中任一个顶点v出发，深度优先遍历（DFS）的算法步骤如下。
|
|
|
|
|
| （2）访问p顶点，并使p指向与p顶点相邻接的且尚未被访问过的顶点。
|
|
|
| （3）若p不空，则重复步骤（2）；否则执行步骤（4）。
|
|
|
| （4）沿着刚才访问的次序、方向回溯到一个尚有邻接顶点且未被访问过的顶点，并使p指向这个未被访问的邻接顶点，然后重复步骤（2），直至所有的顶点均被访问为止。
|
|
|
| 这个算法的特点是尽可能先对纵深方向搜索，因此可以很容易得到其遍历的递归算法。
|
|
|
| 深度优先遍历图的过程实质上是对某个顶点查找其邻接节点的过程，其耗费的时间取决于所采用的存储结构。当图用邻接矩阵表示时，查找所有顶点的邻接点所需时间为O(n2)。若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。因此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。
|
|
|
