[解決済み] Breadth-First Searchでパスをたどるには？

質問

次の例のような Breadth-First Search の経路をたどるにはどうしたらよいでしょうか。

キーを検索する場合 11 を返します。 最短の のリストを返す。

[1, 4, 7, 11]

どのように解決するのですか？

以下のサイトをご覧ください。 http://en.wikipedia.org/wiki/Breadth-first_search を最初に見てください。

以下は簡単な実装で、パスのキューを表現するためにリストのリストを使用しました。

# 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')

これは印刷します。 ['1', '4', '7', '11']

別のアプローチとして、各ノードからその親へのマッピングを維持し、隣接するノードを検査するときに、その親を記録することができます。検索が完了したら、親のマッピングに従ってバックトレースするだけです。

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

上記のコードは、サイクルがないことを前提にしています。