v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v2 v3
v7
v1 v2 v3
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
0
1 v1 v2
v1
2 v2 v1
v2
பைடு நூலகம்
v3
3 V3 v1
v4
v5
v6
4 V4 v2
v7 5 v5
v2
v8
6 v6 v3
7 v7 v3
8 v8 v4
图广度优先遍历
v3 v4 v5 v6 v7 v8 v8 v7 v6 v5
演示开始，以v1为遍历的起点
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3 v4 v5
v7
v1 v2 v3 v4 v5
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3
v7
v2
v1 v2 v3 v4
V2的邻接点v4没 有被访问过，访 问之，且入队列
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3 v4
队列 v1
v5 v7
V1入队列
v1
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5 v7
v1 v1
图广度优先遍历
取队头元素
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5 v7
v1 访问v1
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v2 v3
v7
v1
v1 v2 v3
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v7
v2
v1 v2 v3 v4
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3 v4
v7
v2
v1 v2 v3 v4 v5
V2的邻接点v5没 有被访问过，访 问之，且入队列
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5 v7
v1 v1 v2
图广度优先遍历
V1的邻接点v2没 有被访问过，访 问之，且入队列
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3
v7
v2
v1 v2 v3
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3
v7
v2
v1 v2 v3
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
7.3.2.连通图的广度优先遍历
图广度优先遍历
算法描述:
1.广度优先遍历以x开始的连通图
① 访问X，且x入队列 ② 若队列不空，重复以下步骤 ③ 取队头元素并放入v中 ④ 考察v的各个邻接点，若未访问，
则先访问，然后放在队列尾部 ⑤ 返回步骤②
图广度优先遍历
2.算法演示
图广度优先遍历
例图及其邻接表表示
队列
v5
v2
v7
v1
v1 v2
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v2
v7
v1
v1 v2 v3
图广度优先遍历
V1的邻接点v3没 有被访问过，访 问之，且入队列
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3
v7
v2
v1 v2 v3
图广度优先遍历
V2的邻接点v1已 经被访问过不再
访问
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v4 v5
v7
v3
v1 v2 v3 v4 v5
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v4 v5
v7
v3
v1 v2 v3 v4 v5
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8
v2 v3 v1 v4 v1 v6 v2 v8 v2 v8 v3 v7 v3 v6 v4 v5
队列
v5
v3 v4 v5
v7
v2
v1 v2 v3 v4 v5
图广度优先遍历
0 1 v1 2 v2 3 V3 4 V4 5 v5 6 v6 7 v7 8 v8