伪代码
Coddy 广度优先搜索:图算法 课程的第 4 课,共 9 课。
bfs(n, edges, start):
build adjacency (sort each list ascending)
visited = all false
queue = [start]; visited[start] = true
order = []
while queue not empty:
node = queue.dequeue() # take from the FRONT
order.add(node)
for nb in adj[node]:
if not visited[nb]:
visited[nb] = true
queue.enqueue(nb)
return order- 和 DFS 的唯一区别是容器:使用队列(先进先出,FIFO),而不是栈(后进先出,LIFO)。
- 编写队列的一种简单方法是使用带移动头部索引的数组:读取
queue[head],然后递增head,即可出队。
亲手试试
这节课没有代码挑战。
这节课包含一个小测验。开始学习即可作答,并记录你的进度。
广度优先搜索:图算法中的所有课
自己练习: C 在线编译器