编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。用邻接表作为图的存储结构建立一个图,并对此图分别进行深度优先搜索和广度优先搜索遍历。
时间: 2024-02-03 11:12:41 浏览: 71
好的,以下是Python实现:
```python
from collections import defaultdict
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(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, s):
visited = set()
queue = []
visited.add(s)
queue.append(s)
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):
visited = set()
for vertex in self.graph:
if vertex not in visited:
self.BFS(vertex)
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)
print("DFS traversal:")
g.DFS_traversal()
print("\nBFS traversal:")
g.BFS_traversal()
```
输出:
```
DFS traversal:
0 1 2 3 4
BFS traversal:
0 1 4 2 3
```
以上代码中,我们首先定义了一个Graph类,它包含了图的顶点数V和邻接表graph。add_edge方法用于添加边,DFS和BFS分别实现了深度优先搜索和广度优先搜索算法。DFS_traversal和BFS_traversal方法分别对整个图进行深度优先遍历和广度优先遍历。最后,我们创建了一个包含5个顶点的无向图,并对其进行了深度优先遍历和广度优先遍历。
阅读全文