How can I use BFS to get a path containing some gi

问题:

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?

回答1:

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

• 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.

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']