广度优先算法

Posted on | In

广度优先算法可以让你计算出A点到B点是否存在路径; 如果存在路径, 则计算出最短路径.
通过解决计算最短路径, 我们引入了图的概念. 图由点和边组成, 一个节点可以和多个节点直接相连, 这些节点之间称为邻居.

举例

你需要在你的人际网中找到一个芒果供应商
方法： 你先找遍你所有的朋友, 确认他们是否是供应商; 如果他们不是的话, 则再找他们的朋友. 你的朋友可以称为一度关系, 你的朋友的朋友则是二度关系. 因为我们要找最短路径, 所以只有确认你的朋友当中没有供应商, 才会再去确认朋友的朋友中有没有供应商(这里存在一个顺序关系, 可以用队列实现). 一直到遍历了所有的人际网, 没有的话表示你的人际网中没有供应商, 如果有的话, 你可以知道最少找几个人就可以找到这个供应商. 由于某些朋友的朋友是重复的, 所以问过的朋友要做标记.
如果要用代码来实现图, 我们可以用散列表来实现.

1
2
3
4
5
6
7
8
9
#用来实现图的数据结构
graph = {}
graph['you'] = ['alice', 'bob', 'chris']
graph['bob'] = ['peggy']
graph['alice'] = ['amy', 'peggy']
graph['chris'] = ['john']
graph['peggy'] = []
graph['amy'] = []
graph['john'] = []

A–>B, 但是B没有到A, 这个称为有向图
A–B, 这个是无向图, 和有向图的A–>B, B–>A是等价的

函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#deque是一种双向队列
from collections import deque
#这里通过判断名字中是否存在m, 来决定是否是需要找的人
def judge_person(name):
  if 'm' in name:
    return True
  else:
    return False
def search_person():
  check_list = deque(graph['you'])
  checked_list = []
  while check_list:
    for name in check_list:
      if name in checked_list:
        pass
      else:
        if judge_person(name):
          return name
        else:
          check_list.popleft()
          check_list.append(graph[name])
          checked_list.append(name)
  return 'no persion found'
if __name__ == __main__:
  print search_person()