python如何實(shí)現(xiàn)廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑

這篇文章給大家分享的是有關(guān)python如何實(shí)現(xiàn)廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

廣度優(yōu)先搜索

適用范圍： 無(wú)權(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)開(kāi)始搜索的話，一開(kāi)始是0、將0加入隊(duì)列中；
然后下一層，0可以到達(dá)的有1,2,4,將他們加入隊(duì)列中；
接下來(lái)是1，1能到達(dá)的且未被訪問(wèn)的是結(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來(lái)保存已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn),隊(duì)列有頭指針head以及尾指針tail,起點(diǎn)start與結(jié)點(diǎn)i有邊并且結(jié)點(diǎn)i未被訪問(wèn)過(guò)，則將該結(jié)點(diǎn)加入隊(duì)列中,tail指針往后移動(dòng)；當(dāng)tail等于頂點(diǎn)數(shù)時(shí)算法結(jié)束

對(duì)于每一次while循環(huán)，head都加一，也就是往右邊移動(dòng)，比如一開(kāi)始head位置是0，下一層的時(shí)候head位置元素就為1，也就是搜索與結(jié)點(diǎn)1有邊的且未被訪問(wèn)的結(jié)點(diǎn)

用一個(gè)數(shù)組book來(lái)標(biāo)識(shí)結(jié)點(diǎn)i是否已經(jīng)被訪問(wèn)過(guò)；用字典來(lái)保存起點(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ǔ)遍歷過(guò)的頂點(diǎn)
  book = np.zeros(vertex_num, dtype=np.int) # 標(biāo)記頂點(diǎn)i是否已經(jīng)被訪問(wèn)，1表被訪問(wèn)，0表未被訪問(wèn)

  point_step_dict = dict() # key:點(diǎn)，value:起點(diǎn)到該點(diǎn)的步長(zhǎng)

  # 隊(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)被訪問(wèn)過(guò)
      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)訪問(wèn)過(guò)
        point_step_dict[i] = head + 1 # 記錄步長(zhǎng)
      if tail == vertex_num: # 說(shuō)明所有頂點(diǎn)都被訪問(wèn)過(guò)
        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，則字典里沒(méi)有這個(gè)鍵，返回None
    return None

result = bfs(ini_matrix, 1, 4)
print("result:", result)

錯(cuò)誤

在經(jīng)同學(xué)的一番調(diào)教之后，我深刻意識(shí)到了這段代碼有個(gè)問(wèn)題（不能用head記錄步長(zhǎng)），就是對(duì)于有環(huán)的時(shí)候，可能得到的步長(zhǎng)（迭代次數(shù)）會(huì)比最短路徑還大；
比如，起點(diǎn)為4，終點(diǎn)為3：這里每一遍迭代都是一次while循環(huán)
第一遍迭代，隊(duì)列4，head指向4，步長(zhǎng)為0
第二遍迭代，隊(duì)列4，0 ， 2，head指向0， 步長(zhǎng)為1
第三遍迭代，隊(duì)列4，0 ， 2，1，head指向2，步長(zhǎng)為2，
第四遍迭代，對(duì)于2，2周?chē)急辉L問(wèn)過(guò)了，但此時(shí)head仍然+=1為3，這就導(dǎo)致了下一次的步長(zhǎng)會(huì)比實(shí)際的步長(zhǎng)多1
第五遍迭代， 3，步長(zhǎng)為4

糾正

改進(jìn)的思路：用count記錄步長(zhǎng)，flag用于標(biāo)識(shí)當(dāng)前搜索能到達(dá)的邊的該結(jié)點(diǎn)cur = que[head]周?chē)欠褚呀?jīng)被訪問(wèn)過(guò)，F(xiàn)alse表示沒(méi)有，True表示該結(jié)點(diǎn)i周?chē)急辉L問(wèn)過(guò)了；也就是，當(dāng)flag為False時(shí)，表示對(duì)于cur周?chē)呀?jīng)都訪問(wèn)過(guò)了，此時(shí)步長(zhǎ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 起點(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ǔ)遍歷過(guò)的頂點(diǎn)
  book = np.zeros(vertex_num, dtype=np.int) # 標(biāo)記頂點(diǎn)i是否已經(jīng)被訪問(wèn)，1表被訪問(wèn)，0表未被訪問(wèn)

  point_step_dict = dict() # key:點(diǎn)，value:起點(diǎn)到該點(diǎn)的步長(zhǎng)

  # 隊(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是否周?chē)际潜辉L問(wèn)過(guò)的
    cur = que[head]
    for i in range(vertex_num):
      # 判斷從頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已經(jīng)被訪問(wèn)過(guò)
      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)訪問(wèn)過(guò)
        point_step_dict[i] = count + 1 # 記錄步長(zhǎng)
        flag = True
      if tail == vertex_num: # 說(shuō)明所有頂點(diǎn)都被訪問(wèn)過(guò)
        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)

感謝各位的閱讀！關(guān)于“python如何實(shí)現(xiàn)廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！