使用字典在python中打印图形中可能的所有路径

lyfkaqu1  于 2021-08-20  发布在  Java
关注(0)|答案(1)|浏览(416)

我尝试使用python制作一个图形程序,以打印从x到y的所有可能路径。我想显示从9到29的所有路径,但程序没有打印它。也许任何人都可以帮忙修理它。这是代码。

graph =     {'0': ['3', '10','1'],
             '1': ['10', '0','4'],
             '2': ['8','6','3'],
             '3': ['17','2','9','0'],
             '4': ['1','5'],
             '5': ['4','12','7'],
             '6': ['17','2'],
             '7': ['5','22'],
             '8': ['13','2'],
             '9': ['3','17','10'],
             '10': ['9','17','0','1','11'],
             '11': ['20','12'],
             '12': ['5','11'],
             '13': ['8','14','16'],
             '14': ['13'],
             '15': ['16','17'],
             '16': ['13','15','17'],
             '17': ['16','6','3','9','10','15','18','23','24'],
             '18': ['17','25','19'],
             '19': ['26','18','20'],
             '20': ['28','19','21'],
             '21': ['28','20','22'],
             '22': ['7'],
             '23': ['17','24'],
             '24': ['17','23','27'],
             '25': ['27','18','26'],
             '26': ['25','19'],
             '27': ['24','25','29'],
             '28': ['29','20','21'],
             '29': ['27','28']}

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
find_path(graph,'9','29')

我不确定用什么方法找到它。我需要你的意见我哪里做错了?。谢谢

balp4ylt

balp4ylt1#

如果你使用 networkx 包,问题就变得简单多了。即使你不想使用 networkx ,您还没有修复代码的解决方案。


# Python env: pip install networkx

# Anaconda env: conda install network

import networkx as nx

G = nx.from_dict_of_lists(graph)
all_paths = nx.all_simple_paths(G, '9', '29'))

for path in all_paths:  # <- # 1060 paths!!!
    print(path)
['9', '3', '0', '10', '1', '4', '5', '12', '11', '20', '19', '18', '17', '23', '24', '27', '29']
['9', '3', '0', '10', '1', '4', '5', '12', '11', '20', '19', '18', '17', '24', '27', '29']
['9', '3', '0', '10', '1', '4', '5', '12', '11', '20', '19', '18', '25', '27', '29']
['9', '3', '0', '10', '1', '4', '5', '12', '11', '20', '19', '26', '25', '18', '17', '23', '24', '27', '29']
['9', '3', '0', '10', '1', '4', '5', '12', '11', '20', '19', '26', '25', '18', '17', '24', '27', '29']
...
['9', '10', '11', '12', '5', '7', '22', '21', '28', '20', '19', '18', '25', '27', '29']
['9', '10', '11', '12', '5', '7', '22', '21', '28', '20', '19', '26', '25', '18', '17', '23', '24', '27', '29']
['9', '10', '11', '12', '5', '7', '22', '21', '28', '20', '19', '26', '25', '18', '17', '24', '27', '29']
['9', '10', '11', '12', '5', '7', '22', '21', '28', '20', '19', '26', '25', '27', '29']
['9', '10', '11', '12', '5', '7', '22', '21', '28', '29']

相关问题