如何在广度优先搜索中跟踪路径？

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.

如果搜索键11，则返回连接1到11的最短列表。

[1, 4, 7, 11]

5 个解决方案

#1

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

您应该首先查看http://en.wikipedia.org/wiki/Breadth-first_search。

---

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 adjacent 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, []):
            if node not in queue :
                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.

以上代码基于没有周期的假设。

#2

I liked qiao's first answer very much! The only thing missing here is to mark the vertexes as visited.

Why we need to do it?
Lets imagine that there is another node number 13 connected from node 11. Now our goal is to find node 13.
After a little bit of a run the queue will look like this:

我非常喜欢乔的第一个答案！这里唯一缺少的是将顶点标记为已访问。为什么我们需要这样做？让我们想象一下，从节点11连接了另一个节点号13.现在我们的目标是找到节点13.经过一段时间的运行后，队列将如下所示：

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

Note that there are TWO paths with node number 10 at the end.
Which means that the paths from node number 10 will be checked twice. In this case it doesn't look so bad because node number 10 doesn't have any children.. But it could be really bad (even here we will check that node twice for no reason..)
Node number 13 isn't in those paths so the program won't return before reaching to the second path with node number 10 at the end..And we will recheck it..

请注意，末尾有两个节点号为10的路径。这意味着将检查节点号10的路径两次。在这种情况下它看起来并不那么糟糕，因为节点号10没有任何子节点..但它可能非常糟糕（即使在这里我们将无缘无故地检查该节点两次..）节点号13不在这些路径所以程序在到达节点号为10的第二条路径之前不会返回。我们将重新检查它。

All we are missing is a set to mark the visited nodes and not to check them again..
This is qiao's code after the modification:

我们所缺少的是一个标记被访问节点的集合，而不是再次检查它们。这是修改后的qiao代码：

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)

The output of the program will be:

该计划的输出将是：

[1, 4, 7, 11, 13]

Without the unneccecery rechecks..

没有不必要的重新检查..

#3

I thought I'd try code this up for fun:

我以为我会尝试编写这个有趣的代码：

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

If you want cycles you could add this:

如果你想要循环，你可以添加：

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

#4

I like both @Qiao first answer and @Or's addition. For a sake of a little less processing I would like to add to Or's answer.

我喜欢@Qiao第一个回答和@ Or的补充。为了减少处理，我想添加Or的答案。

In @Or's answer keeping track of visited node is great. We can also allow the program to exit sooner that it currently is. At some point in the for loop the current_neighbour will have to be the end, and once that happens the shortest path is found and program can return.

在@ Or的答案中，跟踪被访问节点是很好的。我们还可以让程序尽快退出。在for循环中的某个时刻，current_neighbour必须是结束，一旦发生这种情况，就会找到最短路径并且程序可以返回。

I would modify the the method as follow, pay close attention to the for loop

我将修改方法如下，密切关注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)

The output and everything else will be the same. However, the code will take less time to process. This is especially useful on larger graphs. I hope this helps someone in the future.

输出和其他一切都是一样的。但是，代码处理的时间会更短。这在较大的图形上特别有用。我希望这能帮助将来的某个人。

#5

Very easy code. You keep appending the path each time you discover a node.

非常简单的代码。每次发现节点时都会继续附加路径。

graph1 = {
         'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])
         }
def retunShortestPath(graph, start, end):

    queue = [(start,[start])]
    visited = set()

    while queue:
        vertex, path = queue.pop(0)
        visited.add(vertex)
        for node in graph[vertex]:
            if node == end:
                return path + [end]
            else:
                if node not in visited:
                    visited.add(node)
                    queue.append((node, path + [node]))