概要
来看下图的另外一个应用，深度优先算法。
深度优先，听名字就知道，一条道走到黑；然后回溯到之前的起始点，遍历下一个节点，循环。
这是我理解的，其中用到了回溯的思想，遍历节点。
例子
有个走迷宫的例子。这个就是用的深度优先。一个路口走到头，不能再往里走了，也就是没路了，然后回答起始位置，重新往下个节点，一直走到没路位置。
我觉得有点暴力的思想，遍历所有节点，一直往下，如果有路，总能找到；没路，就是走到最后也没路可走，回来了又。遍历完所有节点，结束。
看下代码，下边。
代码Python
递归写法代码模板。
递归
visited = set() def dfs(node, visited): if node in visited: # terminator # already visited return visited.add(node) # process current node here. ... for next_node in node.children(): if next_node not in visited: dfs(next_node, visited)
非递归
非递归写法
def DFS(self, tree): if tree.root is None: return [] visited, stack = [], [tree.root] while stack: node = stack.pop() visited.add(node) process (node) nodes = generate_related_nodes(node) stack.push(nodes)
小结
深度优先，图的应用
深度优先，很有趣的算法；代码也很经典，都值得学习。我记得最开始学的时候，给我的印象就是一条路走到黑，然后再走下一个节点。循环。跟广度优先不一样，先遍历跟它接触的所有节点，然后下一个，下一个。也挺好理解的。其实这么看。都是挺有趣的算法，还有快慢指针等等。
