Python - использование словаря для определения графа и поиска путей

Question

Я определил график следующим образом:

adj_matrix = {'1': set('2'),
              '2': set('3'),
              '3': set(['4', '5']),
              '4': set(''),
              '5': set('6'),
              '6': set('7'),
              '7': set('8'),
              '8': set(['9', '14']),
              '9': set(['10', '11']),
              '10': set(''),
              '11': set(['12', '13']),
              '12': set(''),
              '13': set(''),
              '14': set('15'),
              '15': set('16'),
              '16': set('17'),
              '17': set(['18', '19']),
              '18': set(''),
              '19': set('')}

И я использую следующее, чтобы найти путь между различными узлами:

def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if start not in graph:
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None

Проблема в том, что функция работает только для узлов от 1 до 14. Например, когда я звоню p = find_path(adj_matrix, '3', '14'), он работает как брелок и дает мне ['3', '5', '6', '7', '8', '14'] в качестве ответа, но когда я пытаюсь, например, p = find_path(adj_matrix, '3', '15'), он возвращает None. Есть идеи, что происходит и как я могу это исправить?

Answer 1

Если вы измените свой ввод на

adj_matrix = {'1': set('2'),
          '2': set('3'),
          '3': set(['4', '5']),
          '4': set(''),
          '5': set('6'),
          '6': set('7'),
          '7': set('8'),
          '8': set(['9', '14']),
          '9': set(['10', '11']),
          '10': set(''),
          '11': set(['12', '13']),
          '12': set(''),
          '13': set(''),
          '14': set(['15']),
          '15': set(['16']),
          '16': set(['17']),
          '17': set(['18', '19']),
          '18': set(''),
          '19': set('')}

(я просто добавил, поместил '15', '16' и '17' в список.) Тогда это работает.Ваша проблема связана с тем фактом, что двухзначные числа, когда они одни в наборе, интерпретируются как строка в строке for node in graph[start]:, а затем вы перебираете ['1', '5']

Также обратите внимание, что в качестве альтернативы вы могли бы просто использовать целые числа без кавычек вокруг каждого числа, и это решило бы и эту проблему, я думаю.

Answer 2

для ошибочного случая, когда вы достигаете '14', доступные маршруты отображаются как '1' и '5', а не как '15'.Вы должны установить список для каждого set, чтобы вы могли выполнять итерации по фактическим значениям.

adj_matrix = {'1': set(['2']),
              '2': set(['3']),
              '3': set(['4', '5']),
              '4': set(''),
              '5': set(['6']),
              '6': set(['7']),
              '7': set(['8']),
              '8': set(['9', '14']),
              '9': set(['10', '11']),
              '10': set(''),
              '11': set(['12', '13']),
              '12': set(''),
              '13': set(''),
              '14': set(['15']),
              '15': set(['16']),
              '16': set(['17']),
              '17': set(['18', '19']),
              '18': set(''),
              '19': set('')}

, используя вышеуказанную adj_matrix, это дает правильный результат.

здесь ваша функция смои отладчики.Вы можете видеть, как код поступает из терминала:

def find_path(graph, start, end, path=[]):
        path = path + [start]
        print("st:%s, end:%s, path:%s" % (start,end,path))
        if start == end:
            return path
        if start not in graph:
            return None
        print("available routes: %s" % graph[start])
        for node in graph[start]:
            if node not in path:
                print("next node: %s" % node)
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None

Используя вашу ошибочную adj_matrix, она выдает консольный вывод следующим образом: (Внимательно следите, когда дело доходит до '14')

C:\Users\rapac\Desktop\stackoverflow>python adjgraph.py
st:3, end:15, path:['3']
available routes: {'5', '4'}
next node: 5
st:5, end:15, path:['3', '5']
available routes: {'6'}
next node: 6
st:6, end:15, path:['3', '5', '6']
available routes: {'7'}
next node: 7
st:7, end:15, path:['3', '5', '6', '7']
available routes: {'8'}
next node: 8
st:8, end:15, path:['3', '5', '6', '7', '8']
available routes: {'9', '14'}
next node: 9
st:9, end:15, path:['3', '5', '6', '7', '8', '9']
available routes: {'11', '10'}
next node: 11
st:11, end:15, path:['3', '5', '6', '7', '8', '9', '11']
available routes: {'13', '12'}
next node: 13
st:13, end:15, path:['3', '5', '6', '7', '8', '9', '11', '13']
available routes: set()
next node: 12
st:12, end:15, path:['3', '5', '6', '7', '8', '9', '11', '12']
available routes: set()
next node: 10
st:10, end:15, path:['3', '5', '6', '7', '8', '9', '10']
available routes: set()
next node: 14
st:14, end:15, path:['3', '5', '6', '7', '8', '14']
available routes: {'5', '1'} <--- Here it is! We expect '15' here.
next node: 1
st:1, end:15, path:['3', '5', '6', '7', '8', '14', '1']
available routes: {'2'}
next node: 2
st:2, end:15, path:['3', '5', '6', '7', '8', '14', '1', '2']
available routes: {'3'}
next node: 4
st:4, end:15, path:['3', '4']
available routes: set()
None

Наконец, вот вывод, когда вы используете правильную версию adj_matrix:

C:\Users\rapac\Desktop\stackoverflow>python adjgraph.py
st:3, end:15, path:['3']
available routes: {'4', '5'}
next node: 4
st:4, end:15, path:['3', '4']
available routes: set()
next node: 5
st:5, end:15, path:['3', '5']
available routes: {'6'}
next node: 6
st:6, end:15, path:['3', '5', '6']
available routes: {'7'}
next node: 7
st:7, end:15, path:['3', '5', '6', '7']
available routes: {'8'}
next node: 8
st:8, end:15, path:['3', '5', '6', '7', '8']
available routes: {'9', '14'}
next node: 9
st:9, end:15, path:['3', '5', '6', '7', '8', '9']
available routes: {'11', '10'}
next node: 11
st:11, end:15, path:['3', '5', '6', '7', '8', '9', '11']
available routes: {'12', '13'}
next node: 12
st:12, end:15, path:['3', '5', '6', '7', '8', '9', '11', '12']
available routes: set()
next node: 13
st:13, end:15, path:['3', '5', '6', '7', '8', '9', '11', '13']
available routes: set()
next node: 10
st:10, end:15, path:['3', '5', '6', '7', '8', '9', '10']
available routes: set()
next node: 14
st:14, end:15, path:['3', '5', '6', '7', '8', '14']
available routes: {'15'} <-- Now we're good.
next node: 15
st:15, end:15, path:['3', '5', '6', '7', '8', '14', '15']
['3', '5', '6', '7', '8', '14', '15']

Теперь код ведет себя так, как вы ожидаете.Надеюсь, это поможет.