我有一个很大的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]


完成这项工作的最有效方法是什么? (当前,我正在将其转换为一个邻接矩阵,因为我的地图很大,所以效率很低。)

最佳答案

您当前的表示形式(Map<String, Set<String>>)被称为adjacency list,非常适合标准遍历算法,例如广度优先或深度优先。

这样的事情应该做:

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)

10-05 17:53