编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-13 14:05:32 浏览: 86
以下是 Python 代码实现,具体步骤如下:
1. 输入无向图的顶点数、边数及各条边的顶点对
2. 建立用邻接表表示的无向图
3. 对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列
```python
from collections import defaultdict, deque
class Graph:
def __init__(self, V):
self.V = V
self.adj = defaultdict(list)
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
def DFS(self, v, visited, result):
visited[v] = True
result.append(v)
for i in self.adj[v]:
if not visited[i]:
self.DFS(i, visited, result)
def BFS(self, s):
visited = [False] * self.V
result = []
queue = deque([s])
visited[s] = True
while queue:
s = queue.popleft()
result.append(s)
for i in self.adj[s]:
if not visited[i]:
queue.append(i)
visited[i] = True
return result
if __name__ == '__main__':
V = int(input("请输入无向图的顶点数:"))
E = int(input("请输入无向图的边数:"))
graph = Graph(V)
for i in range(E):
u, v = map(int, input("请输入第{}条边的顶点对(用空格隔开):".format(i + 1)).split())
graph.add_edge(u, v)
print("邻接表表示的无向图:")
for i in range(V):
print(i, end=" -> ")
for j in graph.adj[i]:
print(j, end=" ")
print()
visited = [False] * V
DFS_result = []
print("深度优先搜索遍历结果:")
for i in range(V):
if not visited[i]:
graph.DFS(i, visited, DFS_result)
print(DFS_result)
BFS_result = graph.BFS(0)
print("广度优先搜索遍历结果:")
print(BFS_result)
```
运行示例:
```
请输入无向图的顶点数:5
请输入无向图的边数:6
请输入第1条边的顶点对(用空格隔开):0 1
请输入第2条边的顶点对(用空格隔开):0 2
请输入第3条边的顶点对(用空格隔开):0 3
请输入第4条边的顶点对(用空格隔开):1 4
请输入第5条边的顶点对(用空格隔开):2 3
请输入第6条边的顶点对(用空格隔开):3 4
邻接表表示的无向图:
0 -> 1 2 3
1 -> 0 4
2 -> 0 3
3 -> 0 2 4
4 -> 1 3
深度优先搜索遍历结果:
[0, 1, 4, 2, 3]
广度优先搜索遍历结果:
[0, 1, 2, 3, 4]
```
阅读全文
相关推荐
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![txt](https://img-home.csdnimg.cn/images/20241231045021.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)