Задача графа: получить список смежности из списка дочерних узлов

У меня есть график, который имеет следующую структуру:

{'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']}

Мне нужен алгоритм, чтобы сделать это. Алгоритм должен быть настолько быстрым, насколько это возможно, используя минимальное дополнительное пространство. Кто-нибудь, кто может это решить?

Спасибо!


python graph algorithm data-structures adjacency-list
person akshitBhatia    schedule 17.04.2014    source источник
comment
Рекурсивный алгоритм для этого был бы высоко оценен. Спасибо!   -  person akshitBhatia    schedule 17.04.2014
comment
Вопрос в его нынешнем виде не соответствует теме этого сайта. Голосование за закрытие.   -  person devnull    schedule 17.04.2014
comment
Предполагается ли, что он ненаправленный и ациклический? Кроме того, было бы полезно, если бы вы опубликовали свою попытку, чтобы мы могли показать вам, как ее исправить. Мы здесь не просто для того, чтобы сделать за вас домашнее задание   -  person inspectorG4dget    schedule 17.04.2014
comment
Да. Он ненаправленный и ациклический.   -  person akshitBhatia    schedule 17.04.2014
comment
Если он ненаправленный, почему я не могу добраться до i из a?   -  person ooga    schedule 17.04.2014
comment
@ooga: я думаю, что dict перечисляет их в некотором порядке обхода   -  person inspectorG4dget    schedule 17.04.2014
comment
@devnull M извините, если это кажется не по теме. Я надеюсь, что я понял вопрос. Мои попытки сделать это были дорогостоящими с точки зрения пространства и времени. Я ищу эффективное решение. Спасибо.   -  person akshitBhatia    schedule 17.04.2014
comment
Виноват. Это родительско-детские отношения. Список смежности будет содержать прямых потомков узла. По этой аналогии это ориентированный граф, поскольку отношения родитель-потомок являются односторонними.   -  person akshitBhatia    schedule 17.04.2014
comment
@akshitBhatia: My attempts at this have been expensive in terms of space and time. Покажите нам свои попытки, и мы постараемся помочь вам их исправить.   -  person inspectorG4dget    schedule 17.04.2014

Ответы (1)


arrow_upward
1
arrow_downward

Не совсем рекурсивно, но вы можете пройтись по каждому дочернему элементу, найти его и удалить все его дочерние элементы из текущего узла:

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)
person Michael0x2a    schedule 17.04.2014