邻接矩阵存储图的广度优先搜索
时间: 2023-07-23 22:06:28 浏览: 43
邻接矩阵是图的一种存储方式,其中每个顶点和边都对应矩阵中的一个元素。如果顶点 i 和 j 之间有边,则矩阵第 i 行第 j 列的元素为 1,否则为 0。
广度优先搜索(BFS)是一种基于队列实现的图搜索算法,它从起始顶点开始,逐层遍历图中的顶点,直到找到目标顶点或者遍历整个图。
邻接矩阵存储图的 BFS 算法步骤如下:
1. 创建一个队列,将起始顶点加入队列。
2. 创建一个数组 visited,用于记录每个顶点是否被访问过,初始所有元素都为 false。
3. 当队列不为空时,执行以下操作:
a. 出队队首元素 v。
b. 将顶点 v 标记为已访问。
c. 遍历邻接矩阵中顶点 v 的所有邻接顶点 w,如果顶点 w 没有被访问过,则将其加入队列。
4. 重复步骤 3 直到找到目标顶点或者遍历整个图。
下面是邻接矩阵存储图的 BFS 算法的 Python 代码实现:
```python
def bfs(graph, start, target):
queue = [start]
visited = [False] * len(graph)
visited[start] = True
while queue:
v = queue.pop(0)
if v == target:
return True
for w in range(len(graph)):
if graph[v][w] == 1 and not visited[w]:
queue.append(w)
visited[w] = True
return False
```
其中,graph 为邻接矩阵,start 为起始顶点的编号,target 为目标顶点的编号。如果找到了目标顶点,则返回 True,否则返回 False。