编写具体函数实现对无向图进行DFS和BFS
时间: 2024-05-07 13:17:39 浏览: 86
好的,下面是具体的函数实现:
DFS:
```python
def dfs(graph, start):
visited = set() # 存储已经访问过的节点
stack = [start] # 存储待访问的节点
while stack:
node = stack.pop() # 取出一个节点
if node not in visited:
visited.add(node) # 加入已访问集合
print(node, end=' ')
# 将当前节点的邻居节点加入待访问栈中
stack.extend(set(graph[node]) - visited)
```
BFS:
```python
def bfs(graph, start):
visited = set() # 存储已经访问过的节点
queue = [start] # 存储待访问的节点
while queue:
node = queue.pop(0) # 取出一个节点
if node not in visited:
visited.add(node) # 加入已访问集合
print(node, end=' ')
# 将当前节点的邻居节点加入待访问队列中
queue.extend(set(graph[node]) - visited)
```
以上是 Python 语言实现的 DFS 和 BFS 算法,其中 graph 是一个字典类型的无向图表示,start 表示遍历的起点节点。这两个算法的时间复杂度都是 O(V+E),其中 V 表示节点数量,E 表示边数量。
阅读全文