王道408图的广度优先遍历
时间: 2023-11-06 15:53:54 浏览: 38
你可以使用队列来实现图的广度优先遍历。首先,将起始节点放入队列中,并将其标记为已访问。然后,从队列中取出一个节点,访问它,并将其未访问过的邻居节点加入队列中。重复这个过程,直到队列为空。
下面是一个示例代码实现:
```python
def bfs(graph, start_node):
visited = set() # 用集合来记录已访问的节点
queue = [] # 用列表来实现队列
queue.append(start_node)
visited.add(start_node)
while queue:
node = queue.pop(0) # 取出队列的第一个节点
print(node, end=' ') # 访问节点
neighbors = graph[node] # 获取该节点的邻居节点
for neighbor in neighbors:
if neighbor not in visited: # 如果邻居节点未访问过,则加入队列并标记为已访问
queue.append(neighbor)
visited.add(neighbor)
```
假设图的数据结构是一个字典,键表示节点,值表示与该节点相邻的节点列表。例如,对于王道408图的邻接表表示如下:
```python
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
```
你可以调用 `bfs(graph, 'A')` 来执行广度优先遍历并打印结果。