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