如何使用BFS获取包含某些给定节点的路径？ [英] How can I use BFS to get a path containing some given nodes in order?

问题描述

我有一个未加权边的图，其中每个节点都标有字母'a'到'z'。

I have a graph with unweighted edges where each node is marked with a letter 'a' to 'z'.

我想修改BFS算法以获得包含字母'c'，'o'，'d'，'e'的最短路径。这四个字母之间可能还有其他字母。您有起始节点 a和结束节点 b。您可以假定该路径始终是按该顺序包含这四个字母的路径。为了满足该条件，我该如何修改BFS？

I want to modify the BFS algorithm to get the shortest path that has contains the letters 'c','o','d','e' in that order. There could be other letters between those four. You have starting node 'a' and the ending node 'b'. You can assume that is always a path that contains those four letters in that order. How can I modify the BFS, in order to satisfy that condition?

推荐答案

如果您知道如何找到两者之间的最短路径具有BFS的节点，则可以按以下方式解决问题：

If you know how to find a shortest path between two nodes with BFS, then the problem can be solved as follows:

• 找到从 a 到 c


• 找到从 c 到 o

找到从 o 到 d 的最短路径

• 找到从 d 到的最短路径> e


• 找到从 e 到 b


• 的最短路径将以上5条路径串联起来，从而形成从 a 到 b 的一条路径。

• Find the shortest path from a to c
• Find the shortest path from c to o
• Find the shortest path from o to d
• Find the shortest path from d to e
• Find the shortest path from e to b
• Concatenate the above 5 paths, which results in one path from a to b.

这是Python的实现：

Here is an implementation in Python:

class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = []

    def link(self, node): 
        # The edge is undirected: implement it as two directed edges
        self.neighbors.append(node)
        node.neighbors.append(self)

    def shortestPathTo(self, target):
        # A BFS implementation which retains the paths
        queue = [[self]]
        visited = set()
        while len(queue):
            path = queue.pop(0) # Get next path from queue (FIFO)
            node = path[-1] # Get last node in that path
            for neighbor in node.neighbors:
                if neighbor == target:
                    # Found the target node. Return the path to it
                    return path + [target]
                # Avoid visiting a node that was already visited
                if not neighbor in visited:
                    visited.add(neighbor)
                    queue.append(path + [neighbor])

# Create the nodes of the graph (indexed by their names)
graph = {}
for letter in 'abcdefo':
    graph[letter] = Node(letter)

# Create the undirected edges
for start, end in ['ab','ae','bc','be','bo','df','ef','fo']:
    graph[start].link(graph[end])

# Concatenate the shortest paths between each of the required node pairs 
start = 'a'
path = [graph['a']]
for end in ['c','o','d','e','b']:
    path.extend( graph[start].shortestPathTo(graph[end])[1:] )
    start = end

# Print result: the names of the nodes on the path
print([node.name for node in path])

创建的图形在代码中看起来像这样：

The graph created in the code looks like this:

输出为：

['a', 'b', 'c', 'b', 'o', 'f', 'd', 'f', 'e', 'b']

这篇关于如何使用BFS获取包含某些给定节点的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！