How can I use BFS to get a path containing some given nodes in order?
I have a graph with unweighted edges where each node is marked with a letter 'a' to 'z'.
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?
If you know how to find a shortest path between two nodes with BFS, then the problem can be solved as follows:
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:
The output is:
['a', 'b', 'c', 'b', 'o', 'f', 'd', 'f', 'e', 'b']
上一篇: 在MySQL中查找重复值