| |
| 图的广度优先遍历的基本思想是：给定图G=（V，E），从图中某个源点v出发，在访问了顶点v之后，接着就尽可能先在横向搜索v的所有邻接点。在依次访问v的各个未被访问过的邻接点w1，w2，…，wk之后，分别从这些邻接点出发依次访问与w1，w2, …，wk邻接的所有未曾访问过的顶点。依此类推，直至图中所有和源点v有路径相通的顶点都已访问过为止，此时从v开始的搜索过程结束。若G是连通图，则遍历完成；否则，在图G中另选一个尚未访问的顶点作为新源点继续上述的搜索过程，直至图G中所有顶点均已被访问为止。采用广度优先搜索法遍历图的方法称为图的广度优先遍历。
|
|
|
| 为确保先访问的顶点其邻接点亦先被访问，在搜索过程中可使用队列来保存已访问过的顶点。当访问v和u时，这两个顶点相继入队，此后，当v和u相继出队时，分别从v和u出发搜索其邻接点v1，v2，…，vs和u1，u2, …，ut，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
|
|
|
|
|
|
|
|
|
|
|
|
京公网安备 11010502032051号 | 营业执照