0

次のサンプル Python コードを Java に移植しようとしています。

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

問題は、再帰を停止する基本ケースです。

if start == end:
    return [path]

A と N の両方を同じノードにするという私の要件をサポートしていません。

例えば:

次の有向グラフがある場合:

A -> [B, C], 
B -> [C, E], 
C -> [D, A]

そして、A と A の間のすべてのパスが必要です。結果は次のようになります。

A -> B -> C -> A

上記のpythonコードは私に与えるだけです:

A
4

1 に答える 1

3

A から A へのパスは、A のネイバーを通過する必要があります。したがって、これを実装する 1 つの方法は、外側のネイバーをすべて列挙することです。

[[["A"]+y for y in find_all_paths(G,x,"A")] for x in graph["A"]]

グラフの場合、結果は次のようになります

[[['A', 'B', 'C', 'A']], [['A', 'C', 'A']]]
于 2013-10-25T05:55:32.767 に答える