1)无向图的建立(如图1),实现邻接表和邻接矩阵两种存储方式之间的转换,并输出图 2)运用深度优先求所有的路径(起点1, 终点4) 3)无向图的创建(图2),广度优先算法进行图的遍历求从0到4的最短路径和长度,输出遍历结果
时间: 2024-02-15 18:02:52 浏览: 47
好的,我来回答您的问题。
1. 无向图的建立实现邻接表和邻接矩阵两种存储方式之间的转换,可以参考下面的代码示例:
```python
# 邻接矩阵转邻接表
def matrix2list(matrix):
n = len(matrix)
nodes = [i for i in range(n)]
edges = {}
for i in range(n):
edges[i] = []
for j in range(n):
if matrix[i][j] != 0:
edges[i].append(j)
return nodes, edges
# 邻接表转邻接矩阵
def list2matrix(nodes, edges):
n = len(nodes)
matrix = [[0] * n for i in range(n)]
for i in range(n):
for j in edges[i]:
matrix[i][j] = 1
return matrix
```
2. 运用深度优先搜索求所有的路径(起点1,终点4),可以参考下面的代码示例:
```python
def dfs_paths(graph, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
paths = []
for node in graph[start]:
if node not in path:
newpaths = dfs_paths(graph, node, end, path)
for newpath in newpaths:
paths.append(newpath)
return paths
# 测试代码
graph = {0: [1, 2], 1: [3, 4], 2: [4], 3: [4], 4: []}
print(dfs_paths(graph, 1, 4))
```
输出结果为:
```
[[1, 3, 4], [1, 4]]
```
3. 无向图的创建(图2),广度优先算法进行图的遍历求从0到4的最短路径和长度,可以参考下面的代码示例:
```python
from collections import deque
def bfs_shortest_path(graph, start, end):
queue = deque([(start, [start])])
visited = set([start])
while queue:
(node, path) = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
if neighbor == end:
return path + [neighbor]
else:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
# 测试代码
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1, 4], 4: [1, 3]}
path = bfs_shortest_path(graph, 0, 4)
print("最短路径为:", path)
print("路径长度为:", len(path) - 1)
```
输出结果为:
```
最短路径为: [0, 1, 4]
路径长度为: 2
```
阅读全文