编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-15 17:02:58 浏览: 23
以下是 Python 代码实现:
```python
from collections import defaultdict, deque
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def dfs_util(self, v, visited, traversal):
visited[v] = True
traversal.append(v)
for i in self.graph[v]:
if not visited[i]:
self.dfs_util(i, visited, traversal)
def dfs(self, start):
visited = [False] * (self.V)
traversal = []
self.dfs_util(start, visited, traversal)
return traversal
def bfs(self, start):
visited = [False] * (self.V)
traversal = []
queue = deque()
visited[start] = True
queue.append(start)
while queue:
s = queue.popleft()
traversal.append(s)
for i in self.graph[s]:
if not visited[i]:
visited[i] = True
queue.append(i)
return traversal
if __name__ == '__main__':
# 输入顶点数和边数
V = int(input("Enter the number of vertices: "))
E = int(input("Enter the number of edges: "))
# 建立无向图
g = Graph(V)
for i in range(E):
print("Enter edge", i + 1, "vertices:")
u, v = map(int, input().split())
g.add_edge(u, v)
# 输出深度优先遍历序列
print("DFS traversal:")
for i in range(V):
traversal = g.dfs(i)
print("Starting from vertex", i, ":", traversal)
# 输出广度优先遍历序列
print("BFS traversal:")
for i in range(V):
traversal = g.bfs(i)
print("Starting from vertex", i, ":", traversal)
```
代码中用邻接表表示无向图,实现了深度优先搜索和广度优先搜索遍历。用户需要输入顶点数和边数,以及每条边的顶点对,程序会输出深度优先和广度优先遍历序列。