图的深度优先搜索类似于树的先根次序遍历;图的广度优先搜索类似于图的层次遍历。首先利用邻接矩阵作存储结构,编写图的深度优先搜索和广度优先搜索。 测试数据: 6 10 //顶点数 边数 ABCDEF //顶点 (0,1),( 0,2),(0,3),( 0,4),( 1,2),( 1,3),( 2,3),( 2,5),( 3,4),( 3,5), //边 输出该图深度优先搜索和广度优先搜索访问顺序。
时间: 2023-08-16 22:04:26 浏览: 72
图的深度优先搜索和广度优先搜索
好的,我明白了。以下是基于邻接矩阵的图的深度优先搜索和广度优先搜索的代码实现:
```python
# 邻接矩阵存储图
class Graph:
def __init__(self, vertices):
self.vertices = vertices
self.adj_matrix = [[0] * vertices for i in range(vertices)]
def add_edge(self, u, v):
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1
def dfs(self, start):
visited = [False] * self.vertices
stack = [start]
while stack:
vertex = stack.pop()
if not visited[vertex]:
visited[vertex] = True
print(chr(vertex + 65), end=" ")
for i in range(self.vertices-1, -1, -1):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
stack.append(i)
def bfs(self, start):
visited = [False] * self.vertices
queue = [start]
visited[start] = True
while queue:
vertex = queue.pop(0)
print(chr(vertex + 65), end=" ")
for i in range(self.vertices):
if self.adj_matrix[vertex][i] == 1 and not visited[i]:
visited[i] = True
queue.append(i)
```
接下来是测试代码:
```python
g = Graph(6)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(0, 3)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(3, 5)
print("DFS: ", end="")
g.dfs(0)
print("\nBFS: ", end="")
g.bfs(0)
```
输出结果如下:
```
DFS: A B C D E F
BFS: A B C D E F
```
注意,这里采用了 Python 中的列表来模拟栈和队列,pop(0) 表示从列表的头部弹出元素,pop() 表示从列表的尾部弹出元素。另外,由于题目中顶点的标号是大写字母,因此在输出时需要将整数转化为对应的字母。
阅读全文