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

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

這篇文章主要為大家詳細(xì)介紹了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í)有所幫助，也希望大家多多支持腳本之家。