欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2019年01月17日 08:34:19   作者:冬天飲雪水  
這篇文章主要為大家詳細(xì)介紹了python廣度優(yōu)先搜索得到兩點(diǎn)間最短路徑,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

前言

之前一直寫不出來,這周周日花了一下午終于弄懂了, 順便放博客里,方便以后忘記了再看看。
要實(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)文章

最新評(píng)論