【算法图解】——图、广度优先搜索并实现搜索

Connie ·

更新时间:2024-11-15

· 849 次阅读

文章目录图无向图和有向图广度优先算法问题解决步骤实现图实现广度优先搜索图节点（node）和边（edge）代表着一种连接关系解决的问题：最短路径，象棋中将对方将死最少步数 无向图和有向图

在这里插入图片描述
无向图互为邻居

广度优先算法

通过图的连接关系，一步一步搜索

问题解决步骤 使用图建立问题模型使用广度优先算法解决问题 实现图

利用字典实现图
在这里插入图片描述
注意：peggy是alice的邻居，但alice不是peggy的

"""实现图——字典"""
graph = {}
graph['you'] = ['alice', 'bob', 'claire']
graph['bob'] = ['anuj', 'peggy']
graph['alice'] = ['peggy']
graph['claire'] = ['thom', 'jonny']
graph['anuj'] = [] # 他们都没有邻居，因为他们没有指向别人
graph['peggy'] = []
graph['thom'] = []
graph['jonny'] = []

实现广度优先搜索

通过队列实现
在这里插入图片描述

创建双端队列将你要搜索对象的关系网拉入队列只要队列不空就搜索先获取网中第一个人判断是都检查过判断是否满足搜索条件不满足——将该人的关系网也加入到队列中，并将此人加入到判断过列表中循环

"""先判断是否检查过这个人"""
from collections import deque
def person_is_seller(name):
    return name[-1] == 'm' # 检查人的名字末尾是否为‘m’，是则return True，不是则return False
def search(name):
    search_queue = deque() # 创建双端队列
    search_queue += graph[name] # 将name的关系网（邻居）加入到队列中
    searched = [] # 这个数组用于记录检查过的人
    while search_queue:# 队列不空
        person = search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print("Find " + person)
            else:
                search_queue += graph[person] # 将person的邻居加入到队列中
                searched.append(person)
search('you')

Find thom

注意：一定要判断重复，除了减少重复检查，也避免无限循环

作者：我是小杨我就这样

广度优先搜索算法

1024 个赞