如何跟踪在广度优先搜索的路径？ [英] How to trace the path in a Breadth-First Search?

问题描述

你如何跟踪的广度优先搜索的路径，例如，在下面的例子：

如果搜索键 11 ，返回最短列表中连接1至11。

  [1，4，7，11]
 

解决方案

您应该看看<一href="http://en.wikipedia.org/wiki/Breadth-first_search">http://en.wikipedia.org/wiki/Breadth-first_search第一。

---

下面是一个快速的实现，其中，我使用的列表的列表重新present的路径队列中。

 ＃图是在相邻的列表重新presentation
图= {
        '1'：['2'，'3'，'4']，
        '2'：['5'，'6']，
        '5'：['9'，'10']，
        '4'：['7'，'8']，
        '7'：['11'，'12']
        }

高清BFS（图，开始，结束）：
    ＃保持路径的队列
    队列= []
    ＃推第一路径到队列
    queue.append（[开始]）
    而队列：
        ＃从队列获取第一路径
        PATH = queue.pop（0）
        ＃获取从路径的最后一个节点
        节点=路径[-1]
        ＃路径发现
        如果节点==结束：
            返回路径
        ＃枚举所有的相邻节点，构建一个新的路径，并推入队列
        为在相邻的graph.get（节点，[]）：
            new_path =列表（路径）
            new_path.append（相邻）
            queue.append（new_path）

打印BFS（曲线图中，'1'，'11'）
 

---

另一种方法是将保持从每个节点映射到其父，并且当检查ajacent节点，记录它的父。当搜索完成后，只需根据父映射回溯。

 图= {
        '1'：['2'，'3'，'4']，
        '2'：['5'，'6']，
        '5'：['9'，'10']，
        '4'：['7'，'8']，
        '7'：['11'，'12']
        }

高清回溯（父母，开始，结束）：
    路径= [结束]
    而路径[-1] =启动！
        path.append（父[路径[-1]]）
    path.reverse（）
    返回路径


高清BFS（图，开始，结束）：
    父= {}
    队列= []
    queue.append（开始）
    而队列：
        节点= queue.pop（0）
        如果节点==结束：
            返回回溯（父母，开始，结束）
        为在相邻的graph.get（节点，[]）：
            家长[相邻] =节点＃＆LT;＆LT;＆LT;＆LT;＆LT;记录它的父
            queue.append（相邻）

打印BFS（曲线图中，'1'，'11'）
 

C $ CS上面$是基于这样的假设，有没有循环

How do you trace the path of a Breadth-First Search, such that in the following example:

If searching for key 11, return the shortest list connecting 1 to 11.

[1, 4, 7, 11]

解决方案

You should have look at http://en.wikipedia.org/wiki/Breadth-first_search first.

---

Below is a quick implementation, in which I used a list of list to represent the queue of paths.

# 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')

---

Another approach would be maintaining a mapping from each node to its parent, and when inspecting the ajacent node, record its parent. When the search is done, simply backtrace according the parent mapping.

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, []):
            parent[adjacent] = node # <<<<< record its parent 
            queue.append(adjacent)

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

The above codes are based on the assumption that there's no cycles.

这篇关于如何跟踪在广度优先搜索的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！