编程实现图的遍历图算法(按图的深度优先搜索算法和广度优先搜索算法遍历)
时间: 2023-06-22 12:17:55 浏览: 113
好的,以下是Python实现图的深度优先搜索算法和广度优先搜索算法的代码示例:
```python
# 定义图的邻接矩阵表示法
graph = [
[0, 1, 1, 0, 0, 0],
[1, 0, 0, 1, 1, 0],
[1, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 1],
[0, 1, 1, 0, 0, 1],
[0, 0, 1, 1, 1, 0]
]
# 深度优先搜索算法
def dfs(v, visited):
visited[v] = True
print(v, end=' ')
for i in range(len(graph)):
if graph[v][i] == 1 and not visited[i]:
dfs(i, visited)
# 广度优先搜索算法
from collections import deque
def bfs(v, visited):
queue = deque([v])
visited[v] = True
while queue:
node = queue.popleft()
print(node, end=' ')
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
# 调用深度优先搜索算法和广度优先搜索算法遍历图
visited = [False] * len(graph)
print('深度优先搜索算法遍历结果:', end='')
for i in range(len(graph)):
if not visited[i]:
dfs(i, visited)
visited = [False] * len(graph)
print('\n广度优先搜索算法遍历结果:', end='')
for i in range(len(graph)):
if not visited[i]:
bfs(i, visited)
```
输出结果如下:
```
深度优先搜索算法遍历结果:0 1 3 4 2 5
广度优先搜索算法遍历结果:0 1 2 3 4 5
```
希望这个代码示例能够帮助您理解图的遍历算法。
阅读全文