广度优先搜索可以帮助你找到两样东西的最短距离

总结

  • BFS 指出是否存在从A到B的路径
  • BFS 将找出最短路径
  • 寻找最短路径时，可尝试使用图来建立模型，BFS求解
  • 有向图中的边为箭头，箭头的方向指定了关系的方向，即箭头可理解为动作（verb. A->B A欠B钱）
  • 无向图表示关系的是双向的
  • 队列FIFO，from collection import deque
  • BFS需要设定队列和已检查过目标的数组

**

1. 图 Graph

图由节点（node）和边（edge）组成，一个节点可能与多个节点直接连接，这些节点被称为邻居
**
图用于模拟不同东西是如何相关联的

举例：欠债
A -> B -> C
A欠B钱，B欠C钱

2. 广度优先搜索 BFS

两类问题：

  • 从节点A出发，有前往节点B的路径吗
  • 从节点A出发，前往节点B的那条路径最短

例：你有芒果销售商的联系方式吗？
（第一类问题）
将你的朋友加入到朋友列表中遍历，如果有芒果商则输出，如果没有，则将该朋友的朋友加入到朋友列表中尾部（朋友列表以queue方式遍历）

2.1 查找最短路径

（第二类问题）那个芒果销售商与你的关系最近

  • 在广度优先搜索过程中，先检查一度关系，再检查二度关系，搜索范围从起点开始逐渐向外延伸
  • BFS不仅可查找到从A到B的路径，而且是最短路径
  • 因为我们需要根据添加顺序进行元素遍历，所以需要使用队列（queue）数据结构

2.2 队列 queue

  • 不能随机访问队列元素（类似于栈）
  • 先进先出 FIFO
  • 支持两种操作：入队和出队

3. Python实现

利用散列表实现节点连接的关系，类似“你 -> Bob, Alice”，图表示的是一系列节点和边，更大的图，只需要增加散列表的k-v对即可，对添加顺序无要求

  1. graph = {}
  2. graph['you'] = ['alice', 'bob', 'claire']
  3. graph['alice'] = []

此外，我们需要使用一个searched的数组记录已访问的用户，否则可能出现多次访问一个用户，或形成死循环

  1. from collections import deque
  3. def search(name):
  4.     search_queue = deque()
  5.     search_queue += graph[name]
  6.     searched = []
  7.     while search_queue:
  8.         person = search_queue.popleft()
  9.         if person not in searched:
  10.             if person_is_seller(person):
  11.                 print("Yes!")
  12.                 return True
  13.             else:
  14.                 search_queue += graph[person]
  15.                 searched.append(person)
  16.     return False

运行时间
BigO = O(Vertice + Edge)