|
|
知识路径: > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 > 图的遍历 >
|
相关知识点:2个
|
|
|
|
深度优先搜索(Depth-First Search)的基本思想是:对于给定的图G=(V,E),首先将V中每一个顶点都标记为未被访问,然后,选取一个源点将v标记为已被访问,再递归地用深度优先搜索方法,依次搜索v的所有邻接点w。若w未曾访问过,则以w为新的出发点继续进行深度优先遍历。如果从v出发有路的顶点都已被访问过,则从v的搜索过程结束。此时,如果图中还有未被访问过的顶点(该图有多个连通分量或强连通分量),则再任选一个未被访问过的顶点,并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。
|
|
|
|
|
|
|
|