编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-06 15:09:05 浏览: 60
以下是 Python 代码实现:
```python
from collections import defaultdict
# 用邻接表表示的无向图
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def DFS(self, v, visited):
visited.add(v)
print(v, end=' ')
for neighbour in self.graph[v]:
if neighbour not in visited:
self.DFS(neighbour, visited)
def BFS(self, start):
visited = set()
queue = []
queue.append(start)
visited.add(start)
while queue:
s = queue.pop(0)
print(s, end=' ')
for neighbour in self.graph[s]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
def DFS_traversal(self):
visited = set()
for vertex in self.graph:
if vertex not in visited:
self.DFS(vertex, visited)
def BFS_traversal(self, start):
self.BFS(start)
for vertex in self.graph:
if vertex not in visited:
self.BFS(vertex)
# 输入无向图的顶点数、边数及各条边的顶点对
V = int(input("Enter the number of vertices: "))
E = int(input("Enter the number of edges: "))
graph = Graph()
for i in range(E):
u, v = map(int, input("Enter the vertices for edge {}: ".format(i+1)).split())
graph.add_edge(u, v)
# 深度优先搜索遍历
print("Depth First Traversal:")
graph.DFS_traversal()
# 广度优先搜索遍历
print("\nBreadth First Traversal:")
graph.BFS_traversal(0)
```
这段代码中,我们首先定义了一个 Graph 类,其中包含 add_edge() 方法用于添加边,DFS() 和 BFS() 方法用于进行深度优先搜索和广度优先搜索,DFS_traversal() 和 BFS_traversal() 方法用于对整个图进行遍历并输出遍历序列。
在主函数中,我们首先输入无向图的顶点数、边数及各条边的顶点对,然后创建一个 Graph 对象,并使用 add_edge() 方法建立用邻接表表示的无向图。最后,分别调用 DFS_traversal() 和 BFS_traversal() 方法进行深度优先搜索和广度优先搜索,并输出遍历序列。
阅读全文