DFS是对图进行遍历的最基本的算法，前面将对树的遍历的时候，曾经讲过先序遍历，即根-左子树-右子树，这里DFS和先序遍历比较像。

DFS有两种写法：递归，迭代。

各有各的好处：递归写法比较简单，但是性能低一些； 迭代写法稍微复杂些，但是性能高一些。大家随情况进行抉择。

 

递归算法：

DFS(G,  v)    visited[ v ] ← yes    for  each all w in adjacency( G, v )        IF  visited[w]  ≠  yes            DFS(G, w)

 

 

迭代算法：

STACK svisited[ ]DFS(v)     push( s, v )     while not isEmpty( s )               v ← pop(s)              if not visited[v]                   visit( v )                   for each w in adjacency( v )                      if not visited[w]                                  push(s, w)

 

 

大家可以比较下DFS的迭代算法与BFS算法，步骤几乎一模一样，除了stack换成了queue