這是一個廣度優先的搜索算法嗎？

Question

所以，我有這張圖，我想使用廣度優先搜索算法來查看是否存在從頂點到另一個頂點的路徑。

所以，我實現了Python中的功能取決於通路的存在，它返回true或false，和它的作品。那麼，它爲我做的測試工作。我想知道的是，如果這確實是一個呼吸優先的搜索算法。我以前沒有見過任何BFS算法，我只知道它的基本思想。聽說BFS遞歸實現，但我實現它反覆，這就是爲什麼我對it.So疑惑，這裏都是功能和我圖的表示：

outb = {1: [2, 3], 
    2: [4, 5], 
    3: [5, 11, 12], 
    4: [6, 7], 
    5: [7], 
    6: [9, 10], 
    7: [8], 
    11: [3], 
    12: [15, 14, 13], 
    13: [17], 
    14: [17], 
    15: [12, 5, 8, 16], 
    17: [18]} 

def BFS(v1, v2): 
    parsed = [] 
    toParse = [v1] 
    current = v1 

    while len(toParse) > 0: 

     while current in parsed: 
      current = toParse.pop(0) 

     if current not in outb: 
      return False 

     if v2 in outb[current]: 
      return True 

     toParse += outb[current] 
     parsed.append(current) 

    return False 

而且我是最後一個問題：從本質上講，BFS是否找到了從頂點到另一個頂點的最短路徑？我在網上閱讀這個東西，我想確定。

Answer 1

這是一個廣度優先搜索。它遵循相當典型的結構，將搜索邊界視爲隊列（儘管列表對於隊列來說是一個低效的選擇），並且它按照距離根的距離來排列節點，就像標準的廣度優先搜索一樣。

但是，這也是錯誤的。 0123'終止條件導致它wrongly output False像BFS(1, 18)搜索和while current in parsed: current = toParse.pop(0)循環可以耗盡toParse並拋出一個異常，當它試圖從一個空的列表中彈出，demonstrated here與略有不同的圖形。此外，您的outb與它應該表示的圖形圖片不匹配;它缺少一堆後端邊緣，例如6-> 4。

Answer 2

這是一個BFS算法，用於查找是否存在路徑，但它不會告訴您該路徑是什麼，也不會說明您的字典用於表示圖形的方式。

下面是上圖的BFS示例，它可以處理字典代表圖形的方式。它找到一個時返回路徑，當路徑不存在時返回False。如果你只是希望它返回True當它找到一個路徑，編輯一行19 return True

def BFS2(graph, v1, v2): 
    ''' 
    graph: a dictionary representing an unweighted graph 
    v1: a key in graph, representing the start node 
    v2: a key and value in graph, representing the end node 
    returns: a shortest path from v1 to v2, False if there is no path. 
    ''' 
    if v1 not in graph: 
     return False 
    path_start = [v1] 
    paths = [path_start] 
    while len(paths): 
     test_path = paths.pop(0) 
     last_node = test_path[-1] 

     for next_node in graph[last_node]: 
      if next_node not in test_path: 
       next_path = test_path + [next_node] 
       if next_node == v2: 
        paths.append(next_path) 
        return next_path 
       elif next_node in graph: 
        paths.append(next_path) 
    return False 

Answer 3

不，這不是一個BFS算法。 This image will show you how a BFS algorithm would work