快捷導(dǎo)航

python廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑

更新時(shí)間：2019年01月17日 08:34:19 作者：冬天飲雪水

這篇文章主要為大家詳細(xì)介紹了python廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

前言

之前一直寫(xiě)不出來(lái)，這周周日花了一下午終于弄懂了，順便放博客里，方便以后忘記了再看看。
要實(shí)現(xiàn)的是輸入一張圖，起點(diǎn)，終點(diǎn)，輸出起點(diǎn)和終點(diǎn)之間的最短路徑。

廣度優(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)

寫(xiě)在后面

真的很抱歉，第一次寫(xiě)這種算法博客結(jié)果出了這么大的問(wèn)題，之前都是一些記錄BUG的文章，還好同學(xué)及時(shí)和我說(shuō)了，主要原因還是自己沒(méi)有做那么多測(cè)試的問(wèn)題。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。