如何在给定的图中找到所有可能的简单路径？
如何在给定的图中找到所有可能的简单路径？
提问于 2022-02-05 19:39:04
我必须在两个节点之间找到所有可能的路径.
给定的线表示两个节点之间的边。我可以很容易地找到一条可能的路，但是如何找到剩下的路呢？
#边表示：
7->全边
1-3
1-4
2-3
2-4
5-6
6-7
3-5
graph={}
n=int(input())
for i in range(n):
l=list(map(int,input().split('-')))
if l[0] not in graph:
graph[l[0]]=[l[1]]
else:
graph[l[0]] += [l[1]]
def path(start,end,graph):
que=[]
que.append([start])
while que:
path=que.pop()
if path[-1]==end:
return path
for adj_node in graph.get(path[-1],[]):
new_path=list(path)
new_path.append(adj_node)
que.append(new_path)
print(path(1,6,graph))产出: 1、3、5、6
回答 1
Stack Overflow用户
发布于 2022-02-05 19:53:33
使用networkx
# Python env: pip install networkx
# Anaconda: conda install networkx
import networkx as nx
edges = [(1, 3), (1, 4), (2, 3), (2, 4), (5, 6), (6, 7), (3, 5)]
G = nx.from_edgelist(edges)
paths = nx.all_simple_paths(G, 1, 6)输出：
>>> list(paths)
[[1, 3, 5, 6],
[1, 4, 2, 3, 5, 6]]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/71001516
复制相关文章
相似问题
腾讯云开发者
