§06 图状结构
图的遍历
图的遍历是图算法的基础：从某顶点出发，沿边不重复地访问所有可达顶点。广度优先 （BFS）用队列逐层扩散，深度优先（DFS）用递归一路深入。观察顶点颜色变化，推演两种 遍历的访问顺序。
图的遍历
伪代码
1
procedure BFS(G, v0)
2
visited ← 全 false
3
queue ← empty queue
4
visited[v0] ← true; enqueue(queue, v0)
5
while queue not empty do
6
u ← dequeue(queue); visit(u)
7
for each neighbor w of u do
8
if not visited[w] then
9
visited[w] ← true; enqueue(queue, w)
10
end while
11
end procedure