深度优先遍历-软考在线

深度优先遍历



考试要求：熟悉

知识路径： > 计算机科学基础 > 数据结构与算法基本概念 > 数据结构与算法 > 图 > 图的遍历

深度优先搜索（Depth-First Search）的基本思想是：对于给定的图G=（V，E），首先将V中每一个顶点都标记为未被访问，然后，选取一个源点将v标记为已被访问，再递归地用深度优先搜索方法，依次搜索v的所有邻接点w。若w未曾访问过，则以w为新的出发点继续进行深度优先遍历。如果从v出发有路的顶点都已被访问过，则从v的搜索过程结束。此时，如果图中还有未被访问过的顶点（该图有多个连通分量或强连通分量），则再任选一个未被访问过的顶点，并从这个顶点开始做新的搜索。上述过程一直进行到V中所有顶点都已被访问过为止。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5