使用邻接矩阵或者邻接表创建一个如下所示的无向图,并采用深度优先搜索和广度优先搜索2种遍历算法对图进行遍历
时间: 2023-12-29 12:25:49 浏览: 51
以下是使用邻接矩阵和邻接表创建无向图,并采用深度优先搜索和广度优先搜索进行遍历的示例代码:
1. 使用邻接矩阵创建无向图:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * self.V for _ in range(self.V)]
def add_edge(self, u, v):
self.graph[u][v] = 1
self.graph[v][u] = 1
def dfs(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in range(self.V):
if self.graph[v][i] == 1 and not visited[i]:
self.dfs(i, visited)
def bfs(self, v):
visited = [False] * self.V
queue = []
visited[v] = True
queue.append(v)
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in range(self.V):
if self.graph[v][i] == 1 and not visited[i]:
visited[i] = True
queue.append(i)
# 创建一个无向图
g = Graph(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
# 深度优先搜索
print("深度优先搜索结果:")
visited = [False] * g.V
g.dfs(0, visited)
print()
# 广度优先搜索
print("广度优先搜索结果:")
g.bfs(0)
```
2. 使用邻接表创建无向图:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def dfs(self, v, visited):
visited[v] = True
print(v, end=" ")
for i in self.graph[v]:
if not visited[i]:
self.dfs(i, visited)
def bfs(self, v):
visited = [False] * (max(self.graph) + 1)
queue = []
visited[v] = True
queue.append(v)
while queue:
v = queue.pop(0)
print(v, end=" ")
for i in self.graph[v]:
if not visited[i]:
visited[i] = True
queue.append(i)
# 创建一个无向图
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(3, 5)
g.add_edge(4, 5)
# 深度优先搜索
print("深度优先搜索结果:")
visited = [False] * (max(g.graph) + 1)
g.dfs(0, visited)
print()
# 广度优先搜索
print("广度优先搜索结果:")
g.bfs(0)
```