0

我的问题是致幻剂的所有简单路径问题。我需要根据边而不是节点找到两个节点之间的所有路径

我发现这是一个解决方案，但考虑到我的实际图表的大小，这种方法太慢了。我想知道可以做哪些优化来改善这一点。我已经修改了链接中给出的代码以使用 deque() 这也没有太大帮助 

  g=nx.MultiGraph()
  g.add_edge(1,1,key='a')
  g.add_edge(1,2,key='b')
  g.add_edge(2,4,key='c')
  g.add_edge(2,4,key='d')
  g.add_edge(3,2,key='e')
  g.add_edge(3,3,key='f')
  g.add_edge(1,3,key='g')
  g.add_edge(1,5,key='h')
  g.add_edge(5,5,key='i')
all_path(1,4) 的答案： 

Path: 0 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'c')]
Path: 1 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'd')]
Path: 2 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 3 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 4 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 5 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]
Path: 6 --> [(1, 2, 'b'), (2, 4, 'c')]
Path: 7 --> [(1, 2, 'b'), (2, 4, 'd')]
Path: 8 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 9 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 10 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 11 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]

4

1 回答 1

0

尝试构建新图，将当前边转换为节点，如果我们可以在路径中使用它们相应的边，则两个节点之间存在边。之后，您可以使用 DFS 解决您的问题。

于 2011-04-07T10:33:20.510 回答