我如何使用BFS来获取包含某些给定节点的路径？
我有一个带有未加权边缘的图形，其中每个节点都标有字母'a'到'z'。
我想修改BFS算法以获得包含字母'c'，'o'，'d'，'e'的最短路径。 这四者之间可能还有其他字母。 你有起始节点'a'和结束节点'b'。 您可以假定这总是一个包含这四个字母的路径。 我如何修改BFS以满足这种情况？
如果您知道如何使用BFS在两个节点之间找到最短路径，那么问题可以通过以下方式解决：
以下是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])
代码中创建的图形如下所示：
输出是：
['a', 'b', 'c', 'b', 'o', 'f', 'd', 'f', 'e', 'b']
上一篇: How can I use BFS to get a path containing some given nodes in order?