基于邻接矩阵实现图的广度优先遍历
时间: 2023-12-24 13:02:01 浏览: 28
邻接矩阵是图的一种表示方法,可以用矩阵的形式表示图的结构。邻接矩阵中的行和列都表示图中的节点,矩阵中的值表示两个节点之间是否存在边。如果节点 i 和节点 j 之间存在边,则邻接矩阵中第 i 行第 j 列的值为 1,否则为 0。
广度优先遍历是一种图的遍历算法,用于遍历图中的所有节点。广度优先遍历从图中的某个节点开始,首先访问该节点,然后访问该节点的所有邻居节点,再访问邻居节点的邻居节点,直到遍历完所有节点。
邻接矩阵实现图的广度优先遍历可以使用队列来实现。具体步骤如下:
1. 创建一个队列,将起始节点加入队列中。
2. 创建一个数组 visited,用于记录每个节点是否已经被访问过,将起始节点标记为已访问。
3. 从队列中取出一个节点,访问该节点,并将该节点的所有未访问过的邻居节点加入队列中。
4. 如果队列不为空,重复步骤 3,直到队列为空。
下面是基于邻接矩阵实现图的广度优先遍历的 Python 代码示例:
```python
def bfs(graph, start):
queue = [start]
visited = [False] * len(graph)
visited[start] = True
while queue:
node = queue.pop(0)
print(node, end=' ')
for i in range(len(graph)):
if graph[node][i] == 1 and not visited[i]:
queue.append(i)
visited[i] = True
```
其中,graph 是邻接矩阵,start 表示起始节点。调用 bfs 函数即可进行广度优先遍历。