编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-05 18:13:32 浏览: 24
以下是 Python 代码实现,实现了上述功能:
```python
from collections import defaultdict, deque
class Graph:
def __init__(self, n):
self.n = n
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, traversal):
visited.add(v)
traversal.append(v)
for neighbor in self.adj[v]:
if neighbor not in visited:
self.dfs(neighbor, visited, traversal)
def bfs(self, s):
visited = set()
traversal = []
q = deque()
q.append(s)
visited.add(s)
while q:
v = q.popleft()
traversal.append(v)
for neighbor in self.adj[v]:
if neighbor not in visited:
q.append(neighbor)
visited.add(neighbor)
return traversal
def dfs_traversal(self):
visited = set()
traversal = []
for v in range(self.n):
if v not in visited:
self.dfs(v, visited, traversal)
return traversal
def bfs_traversal(self):
return self.bfs(0)
if __name__ == '__main__':
n = int(input("请输入无向图的顶点数:"))
m = int(input("请输入无向图的边数:"))
graph = Graph(n)
print("请依次输入每一条边的顶点对:")
for i in range(m):
u, v = map(int, input().split())
graph.add_edge(u, v)
print("深度优先搜索遍历:")
print(graph.dfs_traversal())
print("广度优先搜索遍历:")
print(graph.bfs_traversal())
```
使用方法:
1. 运行上述代码
2. 输入无向图的顶点数和边数
3. 依次输入每一条边的顶点对
4. 输出深度优先搜索遍历和广度优先搜索遍历序列
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)