【技术分享】图遍历算法之深度优先遍历算法

深度优先遍历算法是经典的图论算法，它的思想是：从一条路径的起始点开始追溯，直到到达路径的最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后的顶点，如此往复，直到没有路径为止。它的遍历过程如下：

（1）以图中的任一顶点V为起始点，首先访问顶点V，并将其标记为已被访问。

（2）从顶点V的任一个邻接点出发继续进行深度优先搜索，直至图中所有和顶点V连通的顶点都已被访问。

（3）若此时图中仍有未被访问的顶点，则选择一个未被访问的顶点作为新的出发点重复上述过程，直至图中所有顶点都已被访问为止。

深度优先遍历方法应用了堆栈这种数据结构的特点，这里以下图所示的无向图为例来介绍这个方法的遍历过程。

步骤 1 ：假设以顶点 A 为起点，将顶点 A 压入堆栈，如下图所示。

步骤 2 ：弹出顶点 A ，将顶点 A 的邻接点 B 和 C 压入堆栈，如下图所示。

步骤 3 ：根据堆栈“后进先出”的原则，弹出顶点 C ，再将与顶点 C 相邻并且未被访问过的顶点 B 、顶点 D 和顶点 E 压入堆栈，如下图所示。

步骤 4 ：弹出顶点 E ，将与顶点 E 相邻并且未被访问过的顶点 D 压入堆栈，如下图所示。

步骤 5 ：弹出顶点 D ，将与顶点 D 相邻并且未被访问过的顶点 B 和顶点 F 压入堆栈，如下图所示。

步骤 6 ：弹出顶点 F ，将与顶点 F 相邻并且未被访问过的顶点压入堆栈。由于顶点 F 的邻接点 D 已被访问过，所以无需压入堆栈，如下图所示。

步骤 7 ：弹出顶点 B ，将与顶点 B 相邻并且未被访问过的顶点压入堆栈。由于顶点 B 的邻接点都已被访问过，所以无需压入堆栈，如下图所示。

步骤 8 ：将堆栈中的顶点依次弹出，并判断是否已经访问过，直到堆栈中无顶点可以访问为止，如下图所示。

由此可知，对图进行深度优先遍历的顺序为：顶点 A 、顶点 C 、顶点 E 、顶点 D 、顶点 F 、顶点 B 。

用Python代码描述上述过程，则算法代码如下：

def  dfs (graph, start):

    stack = []  #  定义堆栈

     stack.append(start) #  将起始顶点压入堆栈

     visited =  set () #  定义集合

     while  stack:

        vertex = stack.pop() #  弹出栈顶元素

         if  vertex  not in  visited #  如果该顶点未被访问过

            visited.add(vertex) #  将该顶点放入已访问集合

             print (vertex, end  =  ' ' )  #  打印深度优先遍历的顶点

         for  w  in  graph[vertex] #  遍历相邻的顶点

             if  w  not in  visited  #  如果该顶点未被访问过

                stack.append(w)  #  把顶点压入堆栈