已知邻接矩阵,求从起点到终点的所有连通路径
时间: 2024-03-15 08:47:39 浏览: 63
这个问题可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来解决。
下面以DFS算法为例,给出一种解决方法:
1. 定义一个visited数组,用于标记每个节点是否被访问过,初始化为false。
2. 定义一个空的路径列表path,用于记录搜索过程中经过的路径。
3. 从起点开始,将起点标记为已访问。
4. 对于每一个与起点相邻的未访问过的节点,进行如下操作:
a. 将当前节点添加到path列表中。
b. 如果当前节点是终点,则将path列表中的所有节点组成的路径加入到结果列表result中。
c. 否则,以当前节点为起点,递归调用DFS算法。
d. 回溯时,将当前节点从path列表中移除,并将其标记为未访问过。
5. 返回结果列表result。
具体实现可以参考以下代码:
```python
def find_all_paths(graph, start, end):
visited = [False] * len(graph)
paths = []
dfs(graph, start, end, visited, [start], paths)
return paths
def dfs(graph, cur, end, visited, path, paths):
visited[cur] = True
if cur == end:
paths.append(list(path))
else:
for neighbor in graph[cur]:
if not visited[neighbor]:
path.append(neighbor)
dfs(graph, neighbor, end, visited, path, paths)
path.pop()
visited[cur] = False
```
其中,graph为邻接矩阵,start为起点,end为终点,paths为结果列表。
阅读全文