无向图,两点之间所有路径
时间: 2023-10-14 11:06:07 浏览: 127
无向图两点之间所有路径
要找出无向图中两点之间的所有路径,可以使用深度优先搜索(DFS)算法。下面是一份Python代码,可以实现该功能:
```python
MAXN = 100 # 最大顶点数
G = [[] for i in range(MAXN)] # 用列表存储图的邻接表
vis = [False] * MAXN # 标记数组,记录每个节点是否已被访问
res = [] # 存储所有路径的结果
def dfs(u, v, path):
if u == v: # 如果到达目标节点,将路径存入结果中
path.append(v)
res.append(path[:])
path.pop()
return
vis[u] = True # 标记当前节点已被访问
path.append(u) # 将当前节点加入路径中
for w in G[u]: # 遍历当前节点的所有邻居
if not vis[w]: # 如果邻居节点未被访问过
dfs(w, v, path) # 继续向下搜索
vis[u] = False # 回溯时取消标记
path.pop() # 回溯时将当前节点从路径中删除
n, m = map(int, input().split())
for i in range(m):
u, v = map(int, input().split())
G[u].append(v) # 添加一条边
G[v].append(u) # 由于是无向图,需要添加两条边
s, t = map(int, input().split())
path = []
dfs(s, t, path) # 搜索从 s 到 t 的所有路径
for p in res: # 输出所有路径
print(' '.join(map(str, p)))
```
在上面的代码中,我们使用邻接表来存储图。在 DFS 的过程中,我们使用一个标记数组 vis 来记录每个节点是否已被访问过,使用一个列表类型的 path 变量来存储当前路径。如果当前节点 u 到达目标节点 v,我们就将当前路径存入结果 res 中。在回溯时,我们需要将当前节点从路径中删除,并将其标记为未访问,以便在搜索其他路径时重新访问它。最后,我们遍历结果 res 中的所有路径,并输出它们。
阅读全文