如何在廣度優先搜索中追蹤路徑？

Question

你如何追蹤廣度優先搜索的路徑，使得在下面的例子：

如果搜索鍵11，該最短列表連接1回11

[1, 4, 7, 11] 

Answer 1

你應該先看看http://en.wikipedia.org/wiki/Breadth-first_search。

---

下面是一個快速實現，其中我使用列表列表來表示路徑隊列。

# graph is in adjacent list representation 
graph = { 
     '1': ['2', '3', '4'], 
     '2': ['5', '6'], 
     '5': ['9', '10'], 
     '4': ['7', '8'], 
     '7': ['11', '12'] 
     } 

def bfs(graph, start, end): 
    # maintain a queue of paths 
    queue = [] 
    # push the first path into the queue 
    queue.append([start]) 
    while queue: 
     # get the first path from the queue 
     path = queue.pop(0) 
     # get the last node from the path 
     node = path[-1] 
     # path found 
     if node == end: 
      return path 
     # enumerate all adjacent nodes, construct a new path and push it into the queue 
     for adjacent in graph.get(node, []): 
      new_path = list(path) 
      new_path.append(adjacent) 
      queue.append(new_path) 

print bfs(graph, '1', '11') 

---

另一種方法是保持從每個節點映射到它的父，並且檢查所述鄰接節點的情況下，記錄它的父。搜索完成後，根據父映射進行回溯。

graph = { 
     '1': ['2', '3', '4'], 
     '2': ['5', '6'], 
     '5': ['9', '10'], 
     '4': ['7', '8'], 
     '7': ['11', '12'] 
     } 

def backtrace(parent, start, end): 
    path = [end] 
    while path[-1] != start: 
     path.append(parent[path[-1]]) 
    path.reverse() 
    return path 


def bfs(graph, start, end): 
    parent = {} 
    queue = [] 
    queue.append(start) 
    while queue: 
     node = queue.pop(0) 
     if node == end: 
      return backtrace(parent, start, end) 
     for adjacent in graph.get(node, []): 
      if node not in queue : 
       parent[adjacent] = node # <<<<< record its parent 
       queue.append(adjacent) 

print bfs(graph, '1', '11') 

上述代碼基於沒有周期的假設。

Answer 2

我想我會嘗試代碼這件事的樂趣：

graph = { 
     '1': ['2', '3', '4'], 
     '2': ['5', '6'], 
     '5': ['9', '10'], 
     '4': ['7', '8'], 
     '7': ['11', '12'] 
     } 

def bfs(graph, forefront, end): 
    # assumes no cycles 

    next_forefront = [(node, path + ',' + node) for i, path in forefront if i in graph for node in graph[i]] 

    for node,path in next_forefront: 
     if node==end: 
      return path 
    else: 
     return bfs(graph,next_forefront,end) 

print bfs(graph,[('1','1')],'11') 

# >>> 
# 1, 4, 7, 11 

如果你想要週期，你可以補充一點：

for i, j in for_front: # allow cycles, add this code 
    if i in graph: 
     del graph[i] 

Answer 3

我喜歡喬的第一個答案非常感謝！ 這裏缺少的唯一東西是將頂點標記爲已訪問。

爲什麼我們需要這樣做？
讓我們想象一下，有從節點11連接的另一個節點13號現在我們的目標是要找到節點13
運行的一點點後，隊列將是這樣的：

[[1, 2, 6], [1, 3, 10], [1, 4, 7], [1, 4, 8], [1, 2, 5, 9], [1, 2, 5, 10]] 

注在結尾處有兩個節點號爲10的路徑。
這意味着來自節點號碼10的路徑將被檢查兩次。在這種情況下，它看起來不那麼糟糕，因爲節點號10沒有任何子節點。但它可能非常糟糕（即使在這裏，我們將無故查看該節點兩次。）
節點號13 isn' t，因此程序在到達第二條路徑之前將不會返回，並且結尾號爲10 ..我們將重新檢查它..

我們所缺少的是一組標記訪問節點，而不是再次檢查他們..
這是修改後的喬代碼：

graph = { 
    1: [2, 3, 4], 
    2: [5, 6], 
    3: [10], 
    4: [7, 8], 
    5: [9, 10], 
    7: [11, 12], 
    11: [13] 
} 


def bfs(graph_to_search, start, end): 
    queue = [[start]] 
    visited = set() 

    while queue: 
     # Gets the first path in the queue 
     path = queue.pop(0) 

     # Gets the last node in the path 
     vertex = path[-1] 

     # Checks if we got to the end 
     if vertex == end: 
      return path 
     # We check if the current node is already in the visited nodes set in order not to recheck it 
     elif vertex not in visited: 
      # enumerate all adjacent nodes, construct a new path and push it into the queue 
      for current_neighbour in graph_to_search.get(vertex, []): 
       new_path = list(path) 
       new_path.append(current_neighbour) 
       queue.append(new_path) 

      # Mark the vertex as visited 
      visited.add(vertex) 


print bfs(graph, 1, 13) 

該方案的輸出將是：

[1, 4, 7, 11, 13] 

沒有unneccecery rechecks ..

Answer 4

我喜歡@Qiao第一回答和@ Or的加法。爲了減少處理，我想添加Or的答案。

In @ Or的回答跟蹤訪問節點很棒。我們也可以讓程序儘早退出。在for循環中的某個點，current_neighbour必須是end，一旦發生這種情況，找到最短路徑並返回程序。

我想修改的方法如下，狠抓for循環

graph = { 
1: [2, 3, 4], 
2: [5, 6], 
3: [10], 
4: [7, 8], 
5: [9, 10], 
7: [11, 12], 
11: [13] 
} 


    def bfs(graph_to_search, start, end): 
     queue = [[start]] 
     visited = set() 

    while queue: 
     # Gets the first path in the queue 
     path = queue.pop(0) 

     # Gets the last node in the path 
     vertex = path[-1] 

     # Checks if we got to the end 
     if vertex == end: 
      return path 
     # We check if the current node is already in the visited nodes set in order not to recheck it 
     elif vertex not in visited: 
      # enumerate all adjacent nodes, construct a new path and push it into the queue 
      for current_neighbour in graph_to_search.get(vertex, []): 
       new_path = list(path) 
       new_path.append(current_neighbour) 
       queue.append(new_path) 

       #No need to visit other neighbour. Return at once 
       if current_neighbour == end 
        return new_path; 

      # Mark the vertex as visited 
      visited.add(vertex) 


print bfs(graph, 1, 13) 

輸出和一切將是相同的。但是，代碼將花費更少的時間來處理。這在更大的圖表上特別有用。我希望這可以幫助未來的人。