图挑战：从子节点列表获取邻接表

Question

我有一个图，结构如下：

{'a':['b','c','d','e'],
'b':['d'],
'c':['d','e'],
'd':[],
'e':[],
'f':['i','j','c','e','d'],
'i':['c','e','d']
'j':['e']}

这个列表不是邻接列表，因为它包含了一个节点的所有子节点，而不仅仅是直接的子节点。

这个图应该长成这样：

        a       f     
       / \     / \
      b   \   i   j
       \   \ /   /    
        \   c   /
         \ / \ /
          d   e

所以邻接列表应该是这样的：

{'a':['b','c'],
'b':['d'],
'c':['d','e'],
'd':[],
'e':[],
'f':['i','j'],
'i':['c'],
'j':['e']}

我需要一个算法来实现这个。这个算法应该尽可能快，并且使用最少的额外空间。有没有人能解决这个问题？

谢谢！

Answer 1

这段话的意思是，虽然不是严格意义上的递归，但你可以逐个查看每个子节点，查找它们，然后把当前节点下的所有子节点都移除掉。

def get_adjacency(graph):
    graph = {node: set(children) for node, children in graph.items()}

    for node, children in graph.items():
        for child in children:
            children = children - graph[child]
        graph[node] = children

    return {node: list(children) for node, children in graph.items()}

c = {
    'a': ['b','c','d','e'],
    'b': ['d'],
    'c': ['d','e'],
    'd': [],
    'e': [],
    'f': ['i','j','c','e','d'],
    'i': ['c','e','d'],
    'j': ['e']
}

print get_adjacency(c)