使用邻接矩阵或者邻接表创建一个如下所示的无向图,并采用深度优先搜索和广度优先搜索2种遍历算法对图进行遍历。
时间: 2023-12-29 14:24:56 浏览: 52
以下是使用邻接矩阵和邻接表创建无向图,并采用深度优先搜索和广度优先搜索进行遍历的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()
```
阅读全文