python廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑
前言
之前一直寫不出來,這周周日花了一下午終于弄懂了, 順便放博客里,方便以后忘記了再看看。
要實(shí)現(xiàn)的是輸入一張 圖,起點(diǎn),終點(diǎn),輸出起點(diǎn)和終點(diǎn)之間的最短路徑。
廣度優(yōu)先搜索
適用范圍: 無權(quán)重的圖,與深度優(yōu)先搜索相比,深度優(yōu)先搜索法占內(nèi)存少但速度較慢,廣度優(yōu)先搜索算法占內(nèi)存多但速度較快
復(fù)雜度: 時(shí)間復(fù)雜度為O(V+E),V為頂點(diǎn)數(shù),E為邊數(shù)
思路
廣度優(yōu)先搜索是以層為順序,將某一層上的所有節(jié)點(diǎn)都搜索到了之后才向下一層搜索;
比如下圖:
從0結(jié)點(diǎn)開始搜索的話,一開始是0、將0加入隊(duì)列中;
然后下一層,0可以到達(dá)的有1,2,4,將他們加入隊(duì)列中;
接下來是1,1能到達(dá)的且未被訪問的是結(jié)點(diǎn)3
順序就是 0, 1,2,4, 3,這里用下劃線表示每一層搜索得到的結(jié)點(diǎn);
每一次用cur = que[head]取出頭指針指向的結(jié)點(diǎn),并搜索它能到達(dá)的結(jié)點(diǎn);因此,可以用一個(gè)隊(duì)列que來保存已經(jīng)訪問過的結(jié)點(diǎn),隊(duì)列有頭指針head以及尾指針tail,起點(diǎn)start與結(jié)點(diǎn)i有邊并且結(jié)點(diǎn)i未被訪問過,則將該結(jié)點(diǎn)加入隊(duì)列中,tail指針往后移動(dòng);當(dāng)tail等于頂點(diǎn)數(shù)時(shí)算法結(jié)束
對于每一次while循環(huán),head都加一,也就是往右邊移動(dòng),比如一開始head位置是0,下一層的時(shí)候head位置元素就為1,也就是搜索與結(jié)點(diǎn)1有邊的且未被訪問的結(jié)點(diǎn)
用一個(gè)數(shù)組book來標(biāo)識(shí)結(jié)點(diǎn)i是否已經(jīng)被訪問過;用字典來保存起點(diǎn)到各個(gè)點(diǎn)的最短路徑;
代碼如下:
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): """ 廣度優(yōu)先搜索 :param matrix_para 圖 :param start_point_para 起點(diǎn) :param end_point_para 終點(diǎn) :return: 返回關(guān)聯(lián)度 """ matrix = matrix_para start_point = start_point_para end_point = end_point_para vertex_num = len(matrix) # 頂點(diǎn)個(gè)數(shù) que = np.zeros(vertex_num, dtype=np.int) # 隊(duì)列, 用于存儲(chǔ)遍歷過的頂點(diǎn) book = np.zeros(vertex_num, dtype=np.int) # 標(biāo)記頂點(diǎn)i是否已經(jīng)被訪問,1表被訪問,0表未被訪問 point_step_dict = dict() # key:點(diǎn),value:起點(diǎn)到該點(diǎn)的步長 # 隊(duì)列初始化 head = 0 tail = 0 # 從起點(diǎn)出發(fā),將起點(diǎn)加入隊(duì)列 que[tail] = start_point # 等號(hào)右邊為頂點(diǎn)號(hào)(起點(diǎn)) tail += 1 book[start_point] = 1 # book[i] i為頂點(diǎn)號(hào) while head<tail: cur = que[head] for i in range(vertex_num): # 判斷從頂點(diǎn)cur到頂點(diǎn)i是否有邊,并判斷頂點(diǎn)i是否已經(jīng)被訪問過 if matrix[cur][i] == 1 and book[i] == 0: que[tail] = i # 將頂點(diǎn)i放入隊(duì)列中 tail += 1 # tail指針往后移 book[i] = 1 # 標(biāo)記頂點(diǎn)i為已經(jīng)訪問過 point_step_dict[i] = head + 1 # 記錄步長 if tail == vertex_num: # 說明所有頂點(diǎn)都被訪問過 break head += 1 for i in range(tail): print(que[i]) try: relevancy = point_step_dict[end_point] return relevancy except KeyError: # 捕獲錯(cuò)誤,如果起點(diǎn)不能到達(dá)end_point,則字典里沒有這個(gè)鍵,返回None return None result = bfs(ini_matrix, 1, 4) print("result:", result)
錯(cuò)誤
在經(jīng)同學(xué)的一番調(diào)整之后,我深刻意識(shí)到了這段代碼有個(gè)問題(不能用head記錄步長),就是對于有環(huán)的時(shí)候,可能得到的步長(迭代次數(shù))會(huì)比最短路徑還大;
比如,起點(diǎn)為4,終點(diǎn)為3:這里每一遍迭代都是一次while循環(huán)
第一遍迭代,隊(duì)列4,head指向4,步長為0
第二遍迭代,隊(duì)列4,0 , 2,head指向0, 步長為1
第三遍迭代,隊(duì)列4,0 , 2,1,head指向2,步長為2,
第四遍迭代,對于2,2周圍都被訪問過了,但此時(shí)head仍然+=1為3,這就導(dǎo)致了下一次的步長會(huì)比實(shí)際的步長多1
第五遍迭代, 3,步長為4
糾正
改進(jìn)的思路:用count記錄步長,flag用于標(biāo)識(shí)當(dāng)前搜索能到達(dá)的邊的該結(jié)點(diǎn)cur = que[head]周圍是否已經(jīng)被訪問過,F(xiàn)alse表示沒有,True表示該結(jié)點(diǎn)i周圍都被訪問過了;也就是,當(dāng)flag為False時(shí),表示對于cur周圍已經(jīng)都訪問過了,此時(shí)步長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): """ 廣度優(yōu)先搜索 :param matrix_para 圖 :param start_point_para 起點(diǎn) :param end_point_para 終點(diǎn) :return: 返回關(guān)聯(lián)度 """ matrix = matrix_para start_point = start_point_para end_point = end_point_para vertex_num = len(matrix) # 頂點(diǎn)個(gè)數(shù) que = np.zeros(vertex_num, dtype=np.int) # 隊(duì)列, 用于存儲(chǔ)遍歷過的頂點(diǎn) book = np.zeros(vertex_num, dtype=np.int) # 標(biāo)記頂點(diǎn)i是否已經(jīng)被訪問,1表被訪問,0表未被訪問 point_step_dict = dict() # key:點(diǎn),value:起點(diǎn)到該點(diǎn)的步長 # 隊(duì)列初始化 head = 0 tail = 0 # 迭代次數(shù) count = 0 # 從0號(hào)頂點(diǎn)出發(fā),將0號(hào)頂點(diǎn)加入隊(duì)列 que[tail] = start_point # 等號(hào)右邊為頂點(diǎn)號(hào)(起點(diǎn)) tail += 1 book[start_point] = 1 # book[i] i為頂點(diǎn)號(hào) while head<tail: flag = False # 用flag標(biāo)識(shí)結(jié)點(diǎn)i是否周圍都是被訪問過的 cur = que[head] for i in range(vertex_num): # 判斷從頂點(diǎn)cur到頂點(diǎn)i是否有邊,并判斷頂點(diǎn)i是否已經(jīng)被訪問過 if matrix[cur][i] == 1 and book[i] == 0: que[tail] = i # 將頂點(diǎn)i放入隊(duì)列中 tail += 1 # tail指針往后移 book[i] = 1 # 標(biāo)記頂點(diǎn)i為已經(jīng)訪問過 point_step_dict[i] = count + 1 # 記錄步長 flag = True if tail == vertex_num: # 說明所有頂點(diǎn)都被訪問過 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)
寫在后面
真的很抱歉, 第一次寫這種算法博客結(jié)果出了這么大的問題,之前都是一些記錄BUG的文章,還好同學(xué)及時(shí)和我說了,主要原因還是自己沒有做那么多測試的問題。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
python使用隱式循環(huán)快速求和的實(shí)現(xiàn)示例
這篇文章主要介紹了python使用隱式循環(huán)快速求和的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09Python使用psutil庫對系統(tǒng)數(shù)據(jù)進(jìn)行采集監(jiān)控的方法
利用psutil庫可以獲取系統(tǒng)的一些信息,如cpu,內(nèi)存等使用率,從而可以查看當(dāng)前系統(tǒng)的使用情況,實(shí)時(shí)采集這些信息可以達(dá)到實(shí)時(shí)監(jiān)控系統(tǒng)的目的。本文給大家介紹Python psutil系統(tǒng)監(jiān)控的相關(guān)知識(shí),感興趣的朋友一起看看吧2021-08-08Python lambda 匿名函數(shù)優(yōu)點(diǎn)和局限性深度總結(jié)
這篇文章主要為大家介紹了Python lambda 匿名函數(shù)的優(yōu)點(diǎn)和局限性深度總結(jié),有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-08-08