用无权图的宽度优先的算法求源点到各个节点的最短路径长度,写出算法思想和伪代码实现。
时间: 2023-02-09 07:12:15 浏览: 91
最短路径算法dijkstra的matlab实现_dijkstra_最短路径算法_
5星 · 资源好评率100%
无权图的宽度优先搜索算法 (BFS, Breadth-First Search) 用于求源点到其他节点的最短路径。它通过顺序访问图中的节点,从而保证了只遍历源点到当前节点的最短路径。
算法思想:
1. 首先将源点加入队列,并将源点的距离标记为0。
2. 从队列中取出一个节点,并遍历它的所有邻接点。
3. 对于每个遍历到的邻接点,如果它没有被访问过,就将其标记为已访问,并将其加入队列。此时,还需要将当前节点到该邻接点的距离加入邻接点的距离标记中。
4. 重复步骤2和3,直到队列为空。
伪代码实现:
```
BFS(graph, source):
create a queue Q
create a vector dist[] and initialize all elements of dist[] as INFINITE
create a boolean array visited[] and initialize all elements as false
dist[source] = 0
visited[source] = true
Q.add(source)
while Q is not empty:
u = Q.front()
Q.pop()
for all neighbors v of u:
if visited[v] == false:
visited[v] = true
dist[v] = dist[u] + 1
Q.add(v)
return dist[]
```
阅读全文