|
|
知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 >
|
|
考试要求：熟悉
相关知识点：3个
|
|
|
|
|
给定图G=（V，E）和V （G）中的某一顶点v，从v出发访问G中其余顶点，且使每个顶点位置仅被访问一次，这一过程称为图的遍历。
|
|
|
|
深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法，它们对无向图和有向图均适用。
|
|
|
|
|
|
深度优先搜索（Depth-First Search）的基本思想是：对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历。如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。
|
|
|
|
|
|
图的广度优先遍历的基本思想是：给定图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，对其中未访者进行访问并将其入队。这种方法是将每个已访问的顶点入队，保证了每个顶点至多只有一次入队。
|
|
|
