以邻接表为例，以字符串ABCDE作为案例。
A, B, C, D, E = 'A', 'B', 'C', 'D', 'E'
my_graph = {
A: [B, C],
B: [A],
C: [A, D, E],
D: [],
E: [A, B, C, D],
}
广度优先遍历（BFS）
基本思路是：
- 用集合set保存已访问顶点，避免重复访问
- 用队列queue实现层级遍历（BFS）的顺序
具体做法是，只要访问了新顶点，就标记为已访问，并把它入队。这个操作记作（1）。
在进入邻接表下一行之前，出队，然后将“出队项”所对应的my_graph字典的值（也就是它认识的邻居），进入上述操作（1）。
具体实现中，还可以传递一个顶点作为参数，以表示可以从这个顶点开始遍历。
from collections import deque
A, B, C, D, E = 'A', 'B', 'C', 'D', 'E'
my_graph = {
A: [B, C],
B: [A],
C: [A, D, E],
D: [],
E: [A, B, C, D],
}
def bfs_traversal(graph, start=None):
visited = set()
queue = deque()
if start:
visited.add(start)
queue.append(start)
for vertex in graph:
if vertex not in visited:
visited.add(vertex)
queue.append(vertex)
while queue:
current = queue.popleft()
print(current)
for neighbour in graph[current]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
print('start=default'.center(30, '-'))
bfs_traversal(graph=my_graph) # ABCDE
print('start=C'.center(30, '-'))
bfs_traversal(graph=my_graph, start=C) # CADEB
print('start=B'.center(30, '-'))
bfs_traversal(graph=my_graph, start=B) # BACDE
结果：
--------start=default---------
A
B
C
D
E
-----------start=C------------
C
A
D
E
B
-----------start=B------------
B
A
C
D
E
深度优先遍历（DFS）
深度优先遍历的基本思路与广度优先遍历相似，只不过这次是使用栈。
基本思路是：
- 仍然用集合set保存已访问顶点，避免重复访问
- 用栈(stack)来实现深度遍历的顺序
from collections import deque
A, B, C, D, E = 'A', 'B', 'C', 'D', 'E'
my_graph = {
A: [B, C],
B: [A],
C: [A, D, E],
D: [],
E: [A, B, C, D],
}
def dfs_traversal(graph, start=None):
visited = set()
stack = []
def dfs(begin_vertex):
if begin_vertex not in visited:
stack.append(begin_vertex)
visited.add(begin_vertex)
while stack:
current = stack.pop()
print(current)
for neighbour in reversed(graph[current]):
if neighbour not in visited:
stack.append(neighbour)
visited.add(neighbour)
if not start:
for vertex in graph.keys():
dfs(vertex)
else:
dfs(start)
for vertex in graph.keys():
dfs(vertex)
if __name__ == '__main__':
print('start=default'.center(30, '-'))
dfs_traversal(graph=my_graph)
print('start=C'.center(30, '-'))
dfs_traversal(graph=my_graph, start=C)
print('start=B'.center(30, '-'))
dfs_traversal(graph=my_graph, start=B)
结果：
--------start=default---------
A
B
C
D
E
-----------start=C------------
C
A
B
D
E
-----------start=B------------
B
A
C
D
E
