使用邻接矩阵或者邻接表创建一个如下所示的无向图,并采用深度优先搜索和广度优先搜索2种遍历算法对图进行遍历。
时间: 2023-12-29 14:24:56 浏览: 46
邻接表或者邻接矩阵为存储结构实现连通无向图的深度优先和广度优先遍历
3星 · 编辑精心推荐
以下是使用邻接矩阵和邻接表创建无向图,并采用深度优先搜索和广度优先搜索进行遍历的Python代码:
1. 邻接矩阵实现:
```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(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for i in range(len(graph[start])):
if graph[start][i] and i not in visited:
dfs(graph, i, visited)
# 广度优先搜索
def bfs(graph, start):
visited, queue = set(), [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for i in range(len(graph[vertex])):
if graph[vertex][i] and i not in visited:
visited.add(i)
queue.append(i)
# 测试
print("邻接矩阵实现的无向图:")
for i in range(len(graph)):
print(i, ':', end=' ')
for j in range(len(graph[i])):
if graph[i][j]:
print(j, end=' ')
print()
print("深度优先搜索结果:")
dfs(graph, 0)
print()
print("广度优先搜索结果:")
bfs(graph, 0)
print()
```
2. 邻接表实现:
```python
# 定义邻接表
graph = {0: [1, 2],
1: [0, 3, 4],
2: [0, 4, 5],
3: [1, 5],
4: [1, 2, 5],
5: [2, 3, 4]}
# 深度优先搜索
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for i in graph[start]:
if i not in visited:
dfs(graph, i, visited)
# 广度优先搜索
def bfs(graph, start):
visited, queue = set(), [start]
visited.add(start)
while queue:
vertex = queue.pop(0)
print(vertex, end=' ')
for i in graph[vertex]:
if i not in visited:
visited.add(i)
queue.append(i)
# 测试
print("邻接表实现的无向图:")
for k, v in graph.items():
print(k, ':', v)
print("深度优先搜索结果:")
dfs(graph, 0)
print()
print("广度优先搜索结果:")
bfs(graph, 0)
print()
```
阅读全文