无向图,两点之间所有路径
时间: 2023-10-14 21:06:07 浏览: 80
好的,以下是一个实现无向图中两点之间所有路径的Python代码:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def all_paths(self, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in self.graph[start]:
if node not in path:
new_paths = self.all_paths(node, end, path)
for p in new_paths:
paths.append(p)
return paths
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
print(g.all_paths(0, 3))
```
这个代码定义了一个`Graph`类,其中`add_edge()`方法用于添加边,`all_paths()`方法用于获取两点之间的所有路径。在`all_paths()`方法中,采用了递归的方式来获取所有路径。当起点等于终点时,返回包含当前路径的列表;否则,遍历起点的所有邻居节点,并在路径中排除已经遍历过的节点,继续递归查找。最终返回所有路径的列表。