写一个完整的深度优先和广度优先搜索图
时间: 2024-03-21 10:41:31 浏览: 13
好的,下面是一个完整的深度优先和广度优先搜索图的Python代码:
```python
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(set)
def add_edge(self, u, v):
self.graph[u].add(v)
self.graph[v].add(u)
def dfs(self, start):
visited = set()
def dfs_util(node):
visited.add(node)
print(node, end=' ')
for neighbor in self.graph[node]:
if neighbor not in visited:
dfs_util(neighbor)
dfs_util(start)
def bfs(self, start):
visited = set()
queue = []
visited.add(start)
queue.append(start)
while queue:
node = queue.pop(0)
print(node, end=' ')
for neighbor in self.graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
def print_graph(self):
for node in self.graph:
print(node, ':', ', '.join(str(x) for x in self.graph[node]))
# Example usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print('Graph:')
g.print_graph()
print('DFS:')
g.dfs(2)
print()
print('BFS:')
g.bfs(2)
print()
```
在这个例子中,我们首先定义了一个`Graph`类来表示一个无向图。该类包含三个方法:`add_edge`用于添加边,`dfs`用于实现深度优先搜索,`bfs`用于实现广度优先搜索。我们还定义了一个`print_graph`方法,用于打印图的邻接表表示。
在例子中,我们创建了一个无向图,并添加了一些边。然后我们使用`print_graph`方法打印了图的邻接表表示。接着,我们使用`dfs`方法和`bfs`方法分别实现了深度优先搜索和广度优先搜索,并打印了搜索结果。