遍历图最常用的有两种方式，就是你常听到的 BFS 和 DFS.

  • BFS: Breadth First Search，广度优先搜索
  • DFS: Depdth First Search，深度优先搜索

    BFS

    BFS 类似于树的层序遍历，从第一个节点开始，先访问离 A 最近的点，接着访问次近的点。我们先来构造一个图：图的遍历 - 图1
  1. from collections import deque
  4. class Queue(object):
  5.     def __init__(self):
  6.         self._deque = deque()
  8.     def push(self, value):
  9.         return self._deque.append(value)
  11.     def pop(self):
  12.         return self._deque.popleft()
  14.     def __len__(self):
  15.         return len(self._deque)
  18. def bfs(graph, start):
  19.     search_queue = Queue()
  20.     search_queue.push(start)
  21.     searched = set()
  22.     while search_queue:   # 队列不为空就继续
  23.         cur_node = search_queue.pop()
  24.         if cur_node not in searched:
  25.             yield cur_node
  26.             searched.add(cur_node)
  27.             for node in graph[cur_node]:
  28.                 search_queue.push(node)
  32. if __name__ == '__main__':
  33.     GRAPH = {
  34.         'A': ['B', 'F'],
  35.         'B': ['C', 'I', 'G'],
  36.         'C': ['B', 'I', 'D'],
  37.         'D': ['C', 'I', 'G', 'H', 'E'],
  38.         'E': ['D', 'H', 'F'],
  39.         'F': ['A', 'G', 'E'],
  40.         'G': ['B', 'F', 'H', 'D'],
  41.         'H': ['G', 'D', 'E'],
  42.         'I': ['B', 'C', 'D'],
  43.     }
  44.     print('bfs:')
  45.     bfs(GRAPH, 'A')
  46. """
  47. bfs:
  48. A
  49. B
  50. F
  51. C
  52. I
  53. G
  54. E
  55. D
  56. H
  57. """

DFS

深度优先搜索(DFS)是每遇到一个节点，如果没有被访问过，就直接去访问它的邻居节点，不断加深。代码其实很简单：

  1. DFS_SEARCHED = set()
  4. def dfs(graph, start):
  5.     if start not in DFS_SEARCHED:
  6.         print(start)
  7.         DFS_SEARCHED.add(start)
  8.     for node in graph[start]:
  9.         if node not in DFS_SEARCHED:
  10.             dfs(graph, node)
  13. print('dfs:')
  14. dfs(GRAPH, 'A')  # A B C I D G F E H