BFS通过队列FIFO来访问顶点，而DFS通过(call)stack来实现FILO，每次访问到最深的的点。
1 BFS伪代码（可以先跳过这一节）
- DFS-TREE
- DFS-LOOP
2 时间复杂度
假设点|V|=n, 边|E|=m；
- DFS-TREE：
- DFS-LOOP：
DFS：
3 算法分析
输入样例：
graph_str = """\
U 7
1 2
1 5
1 6
2 3
2 5
3 4
4 5
"""
利用上一节-图的初始化(1)-将字符串转换为邻接表
a = adjacency_list(graph_str)
0 [[],
1 [(2, None), (5, None), (6, None)],
2 [(1, None), (3, None), (5, None)],
3 [(2, None), (4, None)],
4 [(3, None), (5, None)],
5 [(1, None), (2, None), (4, None)],
6 [(1, None)]]dfs(a, 1)
注意：
- state[]和parent[]在进入for循环之前被打印。 此外，state[]是在DFS函数返回（调用）之前打印的。
- 依照邻接表的顺序找点
步骤详解：
- 第一行：初始化，[1]入栈，并标记为Discovered；
- 第二行：找到与[1]相连的一个点[2]，入栈，标记为Discovered；并将[2]的parent设为1；
- 第三行：找到与[2]相连的一个点[3]，入栈，标记为Discovered；并将[3]的parent设为2；
- 第四行：找到与[3]相连的一个点[4]，入栈，标记为Discovered；并将[4]的parent设为3；
- 第五行：找到与[4]相连的一个点[5]，入栈，标记为Discovered；并将[5]的parent设为4；
- 第六行：与[5]相邻的点都被访问过了，将[5]标记为Processed，准备出栈；
- 第七行：[5]出栈，与[4]相邻的点都被访问过了，将[4]标记为Processed，准备出栈；
- 第八行：[4]出栈，与[3]相邻的点都被访问过了，将[3]标记为Processed，准备出栈；
- 第九行：[3]出栈，与[2]相邻的点都被访问过了，将[2]标记为Processed，准备出栈；
- 第十行：[2]出栈，与[1]相邻的点还有[6]没有被访问过，入栈，将[6]标记为Discovered；并将[6]的parent设为1；
- 第十一行：与[6]相邻的点都被访问过了，将[6]标记为Processed，准备出栈；
- 第十二行：[6]出栈，与[1]相邻的点都被访问过了，将[1]标记为Processed，准备出栈；
4 代码实现
现在比较合适回去看伪代码，继续抄伪代码就ok
def dfs_tree(adj_list, start):n = len(adj_list)state = ['U' for i in range(n)]parent = [None for i in range(n)]state[start] = 'D'dfs_loop(adj_list, start, state, parent)return parentdef dfs_loop(adj_list, u, state, parent):for edge in adj_list[u]:v = edge[0]if state[v] == 'U':state[v] = 'D'parent[v] = udfs_loop(adj_list, v, state, parent)state[u] = 'P'gstring = """\
U 5
0 1
1 2
1 3
3 4
4 0
"""
temp = adjacency_list(gstring)
for row in temp:print(row)
print(dfs_tree(temp, 4))