生成代码(建立任意无向图,采用邻接矩阵存储,完成以下操作:对该图进行深度优先遍历,并输出遍历结果。对该图进行广度优先遍历,并输出遍历结果。)
时间: 2024-02-17 22:02:11 浏览: 61
以下是建立无向图并进行深度优先遍历和广度优先遍历的代码:
```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
self._dfs(start, visited)
def _dfs(self, curr, visited):
visited[curr] = True
print(curr, end=' ')
for i in range(self.vertices):
if self.adj_matrix[curr][i] == 1 and not visited[i]:
self._dfs(i, visited)
def bfs(self, start):
visited = [False] * self.vertices
queue = []
queue.append(start)
visited[start] = True
while queue:
curr = queue.pop(0)
print(curr, end=' ')
for i in range(self.vertices):
if self.adj_matrix[curr][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
print("DFS:")
g.dfs(0)
print("\nBFS:")
g.bfs(0)
```
解释一下代码:
1. 首先定义了一个图的类,需要传入顶点数初始化,同时使用邻接矩阵存储图。
2. `add_edge` 方法用于添加边,因为是无向图,所以需要同时在两个顶点之间添加边。
3. `dfs` 方法用于进行深度优先遍历,需要传入起点。
4. `_dfs` 方法是实际的递归函数,用来访问每个顶点,如果一个顶点没有被访问过,就将其标记为已访问,并输出它的编号。然后遍历与其相邻的未访问过的顶点。
5. `bfs` 方法用于进行广度优先遍历,需要传入起点。
6. 在 `bfs` 方法中,使用队列来存储每一层遍历到的顶点,先将起点加入队列中,并标记为已访问。然后从队列中取出一个顶点,输出其编号,并将其相邻的未访问过的顶点加入队列中。
最后运行程序,输出结果如下:
```
DFS:
0 1 3 2 4
BFS:
0 1 2 3 4
```
阅读全文