1

私は大きな を持っています、HashMap<String,Set<String>>このように言います:

    {INDIANBATSMAN=[INDIAN, CRICKETER], COMPANY=[THING],
 INDIAN=[LIVING], LIVING=[THING], PERSON=[LIVING],
 CRICKETER=[PERSON], CANADIAN=[LIVING], SCANDINAVIAN=[LIVING]}

これは実際にはグラフ構造に対応しています。つまり、各キーとその値のセットの間にエッジがあります。各リンクをトラバースし、最初のノードから到達可能なすべてのノードをキーの値のセットとして見つけたいと考えています。

お気に入り、

INDIANBATSMAN=[INDIAN,LIVING,THING,CRICKETER,PERSON]

これを行うための最も効率的な方法は何ですか？(現在、隣接行列に変換していますが、これはマップが巨大なため非常に非効率的です。)

4

1 に答える 1

4

現在の表現 ( Map<String, Set<String>>) は隣接リストと呼ばれ、幅優先や深さ優先などの標準的なトラバーサル アルゴリズムに完全に適しています。

このようなことをする必要があります：

visited = empty set
q = empty list
q.add(startNode)
visited.add(startNode)
while (q is non-empty)
    Node n = q.removeFirst()
    process(n)
    Set<String> children = yourMap.get(n)
    for (Node child : children)
        if (! visited contains child)
            visited.add(n)
            q.add(child)
于 2012-04-18T05:21:54.270 に答える