编写一个网络宽度优先遍历程序
时间: 2024-05-15 10:19:35 浏览: 10
以下是Python语言实现的网络宽度优先遍历程序:
```python
from collections import deque
# 定义一个节点类,包含节点的值和邻居节点列表
class Node:
def __init__(self, value):
self.value = value
self.neighbors = []
# 定义网络宽度优先遍历函数
def bfs(start):
# 使用队列来存储待遍历的节点
queue = deque([start])
# 使用集合来存储已遍历的节点
visited = set([start])
# 遍历队列中的所有节点,直到队列为空
while queue:
# 取出队列中的第一个节点
node = queue.popleft()
print(node.value)
# 遍历该节点的所有邻居节点
for neighbor in node.neighbors:
# 如果邻居节点没有被遍历过,则将其加入队列和已遍历集合中
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# 示例网络
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.neighbors = [node2, node3]
node2.neighbors = [node1, node4, node5]
node3.neighbors = [node1, node4]
node4.neighbors = [node2, node3, node5]
node5.neighbors = [node2, node4]
# 从节点1开始进行网络宽度优先遍历
bfs(node1)
```
输出结果为:
```
1
2
3
4
5
```