Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’[1]) and explores the neighbor nodes first, before moving to the next level neighbors.–wiki

图

图由节点和边组成。一个节点可能与众多节点直接相连，这些节点被称为邻居。一般我们把顶点用V缩写，把边用E缩写。

广度优先搜索

广度优先搜索是一种用于图的查找算法，可帮助解决两类问题。

  1. 从节点A出发，有前往B的路径吗？
  2. 从节点A出发，前往节点B的哪条路径最短？

找出最短路径

在搜索过程中是由近及远的。在寻找最近路径时，需要按添加顺序进行检查，因此需要使用队列。

队列

和现实生活中的队列类似，是一种FIFO的数据结构。

实现图

图可用散列表实现。将键映射到值，可以描述我们需要描述的关系。

实现算法

建立关系图：

1
2
3
4
5
graph = {}
graph["you"] = ["alice", "bob", "charlie"]
graph["bob"] = ["peggy"]
graph["peggy"] = []
...

BFS搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def search(name):
  search_queue = deque()
  search_queue += graph[name]
  searched = []
  while search_queue:
    person = search_queue.popleft()
    if person not in searched:
      if person_is_find(person):
        print person + "is find!"
        return true
      else:
        search_queue += graph[person]
        searched.append(person)
  return false

# 查找peggy
def person_is_find(name):
  return name == peggy

备注：以上使用BFS查找你的关系网中叫peggy的人。

运行时间

O(V+E)

参考书目：
[^1]: 《算法图解》【美】Aditya Bhargava. 编著