BFS

本文最后更新于：2023年2月28日 晚上

图

图源网络

图由节点和边构成。在计科中，一个图就是一些顶点的集合。

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。其中，顶集的元素被称为顶点(Vertex)，边集的元素被称为边(edge)。

广度优先搜索（BFS）

一种用于图的查找算法

通常用于解决：

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

运行时间

O(V+E)

V为顶点数 E为边数

是否存在路径的问题

假设需要寻找能解决编程问腿的大佬一名，首先在自己的朋友圈中查找。我的朋友圈

依次检查，他们三个是否会编程：

  • Chuck
  • Andy
  • Bobbie

假设他们都不会编程，那就要检查他们的朋友，是否有精通编程的。朋友的朋友圈

检查名单中的人时，如果他不会编程，就将他的朋友加入名单，等待检查。

  • Chuck 若Chuck 会编程，任务完成
  • Andy 若Chuck不会，将Chuck的所有朋友加入清单
  • Bobbie

————————————————————

  • Andy
  • Bobbie
  • sean
  • Zhang

重复过程，直到找出会编程的人。类似于上述算法搜遍我的人际网，直到找出会编程的人。即广度优先搜索算法。

最短路径问题

寻找离我关系最近的朋友。先寻找我的朋友，在寻找我朋友的朋友。广度优先搜索正是这样的过程。

正因如此，广度优先搜索不仅查找从A到B的路径，也是在寻找最短路径。

我们始终按添加顺序的检查清单上的人，这样才能实现广度优先搜索。实现这样目的的数据结构——队列

实现图

1
2
3
4
5
6
7
#先用散列表来实现图-字典
graph = {}
graph["me"] = ["Ahuck", "Andy", "Bobbie"]
graph["Chuck"] = ["sean", "Zhang"]
graph["Andy"] = ["sean", "David"]
graph["Bobbie"] = ["Alex"]
#以上就可以表示上面画的关系网了

实现算法

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque #python中使用deque创建队列
search_list = deque()
search_list += graph["me"]   #将我的朋友加入队列
searched = []#已经被查过的人
def he_is_programmer(name):
    '''检查他会不会编程'''
while search_list:#只要队列不空
    examined = search_list.popleft()#取出队列的第一个人
    if examined not in searched:
        if he_is_programmer(examined):
        	print("he is programmer")   #会编程
        	return true
    	else:
        	search_list += graph[examined]#不会编程
            seaeched.append(examined)
return False   #执行至此，没有人会编程

算法将一直运行，直到：

  • 找到一位会编程的
  • 队列为空

队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。 [1]

公交车排队一样，排在前面的先上车。

在查找过程中，先加入的人先出队接受检查。

队列是先进先出（FIFO）

栈是后进后先出(LIFO)