Как найти путь от данного узла ко всем листовым узлам в Python - PullRequest
Новая
       52

Как найти путь от данного узла ко всем листовым узлам в Python

0 голосов
/ 01 апреля 2019

У меня есть словарь, в котором есть список родительских и дочерних узлов, связанных с каждым узлом (ссылка на словарь в коде). Я введу одну клавишу (для следующей части кода B это ключ). Я должен держать родительский узел во внимание. Для B мне нужны пути как [B, C, C1, X], [B, C, C2], [B, D, D1], [B, D, D2] .

Вывод для следующего куска кода, который я получаю: 

C ['C1', 'C2']

C1 ['X']

Также я получаю следующую ошибку:

Файл "", строка 7, в path_find если d [i] ['parent'] == [ключ]:

KeyError: 'X' 

def path_find(graph,key):

    x = d[key]['child'] 
    for i in x:
        if d[i]['parent'] == [key]:
            print(i,d[i]['child'])
            path_find(d,i)


d = {'B':{
 'parent' : ['A'],
  'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
        'D':{
 'parent' : ['B'],
  'child': ['D1','D2']},
    'C1':{
            'parent' : ['C'],
            'child': ['X']}}

key = 'B'
path_find(d,key)

Ожидаемый результат: [B, C, C1, X], [B, C, C2], [B, D, D1], [B, D, D2]

фактический вывод: 

C ['C1', 'C2']

C1 ['X']

1 Ответ

1 голос
/ 01 апреля 2019

В вашем коде есть несколько ошибок:

1) Вы не добавили информацию о X узле в ваш d = { ... }, поэтому вы получили KeyError.Я предполагаю, что это узел без дочерних элементов.

2) Вы не сохранили пути к текущему узлу, поэтому ваш вывод неверен.

Исправленный код (с моими комментариями): 

def path_find(graph, key, current_path, paths_list):  # graph, current node key, path to current node, all paths list
    if key not in d: # not in graph - no children
        paths_list.append(current_path)
        return
    children = d[key]['child'] 
    for child in children:  # check all children
        path_find(graph, child, current_path[:] + [child], paths_list)
    if not children:  # no children - finish search
        paths_list.append(current_path)


d = {'B':{
 'parent' : ['A'],
  'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
        'D':{
 'parent' : ['B'],
  'child': ['D1','D2']},
    'C1':{
            'parent' : ['C'],
            'child': ['X']}}

key = 'B'
paths_list = []
path_find(d, key, [key], paths_list)
print(paths_list)

Вывод:

[['B', 'C', 'C1', 'X'], ['B', 'C', 'C2'], ['B ',' D ',' D1 '], [' B ',' D ',' D2 ']]

...