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