以邻接表为例，以字符串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