编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-16 11:00:03 浏览: 17
好的,我可以为您提供这个功能的 Python 实现。以下是代码:
```python
from collections import defaultdict
class Graph:
def __init__(self, n):
self.graph = defaultdict(list)
self.n = n
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def dfs_util(self, v, visited, res):
visited.add(v)
res.append(v)
for i in self.graph[v]:
if i not in visited:
self.dfs_util(i, visited, res)
def dfs(self, start):
visited = set()
res = []
self.dfs_util(start, visited, res)
return res
def bfs(self, start):
visited = set()
queue = []
res = []
visited.add(start)
queue.append(start)
while queue:
s = queue.pop(0)
res.append(s)
for i in self.graph[s]:
if i not in visited:
visited.add(i)
queue.append(i)
return res
n = int(input("请输入顶点数:"))
m = int(input("请输入边数:"))
g = Graph(n)
for i in range(m):
u, v = map(int, input("请输入第{}条边的顶点对:".format(i+1)).split())
g.add_edge(u, v)
print("DFS遍历序列:", g.dfs(0))
print("BFS遍历序列:", g.bfs(0))
```
运行时,您需要按照提示输入顶点数,边数以及每条边的顶点对。程序将会输出DFS和BFS的遍历序列。
请注意:此实现仅适用于无向图。