用Python实现广度优先搜索
发布日期：2022/9/18 17:40:39 浏览量：
图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的
图的实现形式有很多，最简单的方法之一就是用散列表
背景
图有两种经典的遍历方式：广度优先搜索和深度优先搜索。两者是相似的。
实现
1广度优先搜索算法需要用队列来记录后续要处理哪些顶点。
2该队列最初只含有起步的顶点
3处理顶点。我们将其移出队列，标为“已访问”，并记为当前顶点
|
1
2
3
4
5
6
7
8
9
|
class Bfs:
def __init__(self,from_v,json):
# 最初的顶点
self.from_v = from_v
# 已访问
self.visitList = [self.from_v]
# 需要一个队列来记录后续需要处理哪些顶点
self.vertexQ = queue.Queue()
self.json = json
|
核心步骤
(1) 找出当前顶点的所有邻接点。如果有哪个是没访问过的，就把它标为“已访问”，并且将它入队。（尽管该顶点并未作为“当前顶点”被访问过。）
(2) 如果当前顶点没有未访问的邻接点，且队列不为空，那就再从队列中移出一个顶点作为当前顶点。
(3) 如果当前顶点没有未访问的邻接点，且队列里也没有其他顶点，那么算法完成。
图解
1首先A会作为顶点，A被访问
2再去寻找A领接点B、D，依次加入队列
3A所有领接点都访问完成，开始访问B的领接点
4知道队列为空，算法结束
代码展示
|
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
26
27
28
29
30
31
32
33
34
35
|
class Bfs:
def __init__(self,from_v,json):
# 最初的顶点
self.from_v = from_v
# 已访问
self.visitList = [self.from_v]
# 需要一个队列来记录后续需要处理哪些顶点
self.vertexQ = queue.Queue()
self.json = json
def find_neighbor(self,currentVertex):
#寻找领接点
for neighbor in self.json[currentVertex]:
if neighbor not in self.visitList:
self.visitList.append(neighbor)
self.vertexQ.put(neighbor)
def checkTOV(self,currentVertex,to_v):
#检测要寻找的值（to_v）是否已经在当前currentVertex中
return to_v in self.json[currentVertex]
def searchV(self,to_v):
reverseList = [self.from_v]
self.find_neighbor(self.from_v)
while not self.vertexQ.empty():
currentVertex = self.vertexQ.get()
reverseList.append(currentVertex)
tmp_path = Reverse(currentVertex,self.json).reverseOrder(reverseList,currentVertex)
if currentVertex == to_v:
print(tmp_path)
else:
self.find_neighbor(currentVertex)
if self.checkTOV(currentVertex,to_v):
tmp_path.append(to_v)
print(tmp_path)
|
此外我们额外写了一个向上反向找寻路径的工具类（主要代码写好，不想动原来的结构了）
|
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
26
27
28
|
class Reverse:
def __init__(self,from_v,json):
self.from_v = from_v
self.json = json
def reverseOrder(self,reverseList:list,current_v):
indexReverseList = self.indexReverseList(reverseList)
res = [self.from_v]
tmp = current_v
while len(reverseList) > 0 :
# for _key in self.value2Key(current_v):
_key = self.value2Key(reverseList,tmp)
res.append(_key)
reverseList = reverseList[:indexReverseList[_key]]
tmp = _key
return res[::-1]
def value2Key(self,reverseList:list,current_v):
#根据值找json中的key
#这里我们每次都只取离我们最近的一个key
indexReverseList = self.indexReverseList(reverseList)
tmp = -1
for _key, _value in self.json.items():
if current_v in _value and _key in reverseList and (index := indexReverseList[_key]) > tmp:
tmp = index
return reverseList[tmp]
def indexReverseList(self,reverseList:list):
return {value: index for index, value in enumerate(reverseList)}
|
运行结果
|
1
2
3
|
json = {"A":["B","D"],"B":["C"],"C":["E","D"],"D":["E"],"E":["B"]}<br>#从A出发找B
b=Bfs("A",json)
b.searchV("B")
|
作者： yetangjian
出处： https://www.cnblogs.com/yetangjian/p/16653129.html
业务实施流程 马上咨询： 如果您有业务方面的问题或者需求，欢迎您咨询！我们带来的不仅仅是技术，还有行业经验积累。
QQ: 39764417/308460098 Phone: 13 9800 1 9844 / 135 6887 9550 联系人：石先生/雷先生