|
|
知识路径: > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 > 图的遍历 >
|
相关知识点:2个
|
|
|
|
图的广度优先遍历的基本思想是:给定图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,对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队,保证了每个顶点至多只有一次入队。
|
|
|
|
|
|
|
|