前言
之前一直写不出来,这周周日花了一下午终于弄懂了, 顺便放博客里,方便以后忘记了再看看。
要实现的是输入一张 图,起点,终点,输出起点和终点之间的最短路径。
广度优先搜索
适用范围: 无权重的图,与深度优先搜索相比,深度优先搜索法占内存少但速度较慢,广度优先搜索算法占内存多但速度较快
复杂度: 时间复杂度为O(V+E),V为顶点数,E为边数
思路
广度优先搜索是以层为顺序,将某一层上的所有节点都搜索到了之后才向下一层搜索;
比如下图:
从0结点开始搜索的话,一开始是0、将0加入队列中;
然后下一层,0可以到达的有1,2,4,将他们加入队列中;
接下来是1,1能到达的且未被访问的是结点3
顺序就是 0, 1,2,4, 3,这里用下划线表示每一层搜索得到的结点;
每一次用cur = que[head]取出头指针指向的结点,并搜索它能到达的结点;因此,可以用一个队列que来保存已经访问过的结点,队列有头指针head以及尾指针tail,起点start与结点i有边并且结点i未被访问过,则将该结点加入队列中,tail指针往后移动;当tail等于顶点数时算法结束
对于每一次while循环,head都加一,也就是往右边移动,比如一开始head位置是0,下一层的时候head位置元素就为1,也就是搜索与结点1有边的且未被访问的结点
用一个数组book来标识结点i是否已经被访问过;用字典来保存起点到各个点的最短路径;
代码如下:
import numpy as np ini_matrix = [ [0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0] ] def bfs(matrix_para, start_point_para, end_point_para): """ 广度优先搜索 :param matrix_para 图 :param start_point_para 起点 :param end_point_para 终点 :return: 返回关联度 """ matrix = matrix_para start_point = start_point_para end_point = end_point_para vertex_num = len(matrix) # 顶点个数 que = np.zeros(vertex_num, dtype=np.int) # 队列, 用于存储遍历过的顶点 book = np.zeros(vertex_num, dtype=np.int) # 标记顶点i是否已经被访问,1表被访问,0表未被访问 point_step_dict = dict() # key:点,value:起点到该点的步长 # 队列初始化 head = 0 tail = 0 # 从起点出发,将起点加入队列 que[tail] = start_point # 等号右边为顶点号(起点) tail += 1 book[start_point] = 1 # book[i] i为顶点号 while head<tail: cur = que[head] for i in range(vertex_num): # 判断从顶点cur到顶点i是否有边,并判断顶点i是否已经被访问过 if matrix[cur][i] == 1 and book[i] == 0: que[tail] = i # 将顶点i放入队列中 tail += 1 # tail指针往后移 book[i] = 1 # 标记顶点i为已经访问过 point_step_dict[i] = head + 1 # 记录步长 if tail == vertex_num: # 说明所有顶点都被访问过 break head += 1 for i in range(tail): print(que[i]) try: relevancy = point_step_dict[end_point] return relevancy except KeyError: # 捕获错误,如果起点不能到达end_point,则字典里没有这个键,返回None return None result = bfs(ini_matrix, 1, 4) print("result:", result)
错误
在经同学的一番调教之后,我深刻意识到了这段代码有个问题(不能用head记录步长),就是对于有环的时候,可能得到的步长(迭代次数)会比最短路径还大;
比如,起点为4,终点为3:这里每一遍迭代都是一次while循环
第一遍迭代,队列4,head指向4,步长为0
第二遍迭代,队列4,0 , 2,head指向0, 步长为1
第三遍迭代,队列4,0 , 2,1,head指向2,步长为2,
第四遍迭代,对于2,2周围都被访问过了,但此时head仍然+=1为3,这就导致了下一次的步长会比实际的步长多1
第五遍迭代, 3,步长为4
纠正
改进的思路:用count记录步长,flag用于标识当前搜索能到达的边的该结点cur = que[head]周围是否已经被访问过,False表示没有,True表示该结点i周围都被访问过了;也就是,当flag为False时,表示对于cur周围已经都访问过了,此时步长count不需要自增1;
import numpy as np ini_matrix = [ [0, 1, 1, 0, 1], [1, 0, 0, 1, 0], [1, 0, 0, 0, 1], [0, 1, 0, 0, 0], [1, 0, 1, 0, 0] ] def bfs(matrix_para, start_point_para, end_point_para): """ 广度优先搜索 :param matrix_para 图 :param start_point_para 起点 :param end_point_para 终点 :return: 返回关联度 """ matrix = matrix_para start_point = start_point_para end_point = end_point_para vertex_num = len(matrix) # 顶点个数 que = np.zeros(vertex_num, dtype=np.int) # 队列, 用于存储遍历过的顶点 book = np.zeros(vertex_num, dtype=np.int) # 标记顶点i是否已经被访问,1表被访问,0表未被访问 point_step_dict = dict() # key:点,value:起点到该点的步长 # 队列初始化 head = 0 tail = 0 # 迭代次数 count = 0 # 从0号顶点出发,将0号顶点加入队列 que[tail] = start_point # 等号右边为顶点号(起点) tail += 1 book[start_point] = 1 # book[i] i为顶点号 while head<tail: flag = False # 用flag标识结点i是否周围都是被访问过的 cur = que[head] for i in range(vertex_num): # 判断从顶点cur到顶点i是否有边,并判断顶点i是否已经被访问过 if matrix[cur][i] == 1 and book[i] == 0: que[tail] = i # 将顶点i放入队列中 tail += 1 # tail指针往后移 book[i] = 1 # 标记顶点i为已经访问过 point_step_dict[i] = count + 1 # 记录步长 flag = True if tail == vertex_num: # 说明所有顶点都被访问过 break if flag: count += 1 head += 1 for i in range(tail): print(que[i]) try: relevancy = point_step_dict[end_point] return relevancy except KeyError: return None result = bfs(ini_matrix, 3, 4) print("result:", result)
写在后面
真的很抱歉, 第一次写这种算法博客结果出了这么大的问题,之前都是一些记录BUG的文章,还好同学及时和我说了,主要原因还是自己没有做那么多测试的问题。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
python,最短路径
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新动态
- 群星.1999-上华世纪国语总冠军4CD【上华】【WAV+CUE】
- 叶丽仪.1992-仙鹤神针电视剧原声音乐专辑【星传真】【WAV+CUE】
- 陈柏宇.2011-QUINQUENNIUM【SONY】【WAV+CUE】
- 《51首热门当红歌曲 十大顶级发烧女声 3CD》[WAV+CUE][1.6GB]
- 《赵传 深受摇滚迷青睐的台湾音乐人 约定》[WAV+CUE][320MB]
- 《庄心妍 实力唱将 发烧音乐精选集》[WAV+CUE][380MB]
- [音展纪念碟]2006年《TAA台湾第十六届国际HI-ENDHI-FI音响展》2cd[WAV]
- 中国音乐地图之听见西藏山歌牧歌酒歌2020[WAV分轨]
- 王宏伟2017-永远的红飘带[太平洋影音][WAV+CUE]
- 费翔.1997-NOW现在【第一中国】【WAV+CUE】
- 新格合唱团.1981-我唱你和2辑(滚石新格民歌系列)【新格】【WAV+CUE】
- 陈柏宇.2011-QUINQUENNIUM【SONY】【WAV+CUE】
- 雨果唱片-《金唛系列-蔷薇依韵琼瑶》WAV
- 陈百强《凝望(2012华纳LPCD45限量版)[DMI]》[WAV整轨]
- 模拟之声慢刻CD《徐小凤45周年》[德国母带][低速原抓WAV+CUE]