DFS也是一种常见的图的搜索算法，与BFS不同，DFS不按层级遍历，而是从一条路径遍历到末尾，再返回原来的路径，选择另一路径继续相同的操作，直到全部遍历完成，或到达停止的条件，这一过程类似于走迷宫一样。因此我们还可以用递归的方法实现DFS算法。
在BFS算法中，我们借助了队列的数据结构，遵循先进先出原则，从而实现对每一层级的遍历。与之相反，在DFS，我们需要借助堆栈的数据结构，遵循后进先出原则，从而实现深度优先。
非递归方法的代码如下：
def dfs_1(graph, start): """ return:返回依次序遍历的顶点 """ visited, stack = set(), [start] while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) stack.extend(set(graph.get_connected_nodes(vertex)) - visited) return visited递归方法的代码如下：
def dfs_rec(graph, node, visited=None): """ return:返回依次序遍历的顶点 """ if visited is None: visited = [] if node not in visited: visited.append(node) for neighbour in graph.get_connected_nodes(node): dfs_rec(graph, neighbour, visited) return visited如果需要寻找两个顶点间的最短路径，可以采用类似在BFS中找最短路径的方法，代码结构基本一致，其中的细节需要做如下改动：
def dfs_path(graph, start, goal): """ :param graph: :param start: :param goal: :return: return the path from start to goal, when the goal is found, the programme will stop. """ pathlist=[(start,)] if start == goal: return [start] while len(pathlist) > 0: curr_path = pathlist.pop(0) curr_node = curr_path[-1] new_nodes = graph.get_connected_nodes(curr_node) if len(curr_path) > 1: new_nodes = [node for node in new_nodes if node not in curr_path] if goal in new_nodes: goal_path = curr_path + (goal, ) return goal_path new_paths = [curr_path + (node, ) for node in new_nodes] new_paths.extend(pathlist) pathlist = new_paths else: return []同时，如果需要找到所有的路径，基本思路与BFS的类似：
def dfs_all_path(graph, start, goal): """ :param graph: :param start: :param goal: :return: return the list of all the paths from start to goal """ stack = [(start, [start])] while stack: (vertex, path) = stack.pop() for next in set(graph.get_connected_nodes(vertex)) - set(path): if next == goal: yield path + [next] else: stack.append((next, path + [next]))