C++深度优先搜索的实现方法

本文实例讲述了图的遍历中深度优先搜索的C++实现方法，是一种非常重要的算法，具体实现方法如下：首先，深度优先搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想就是：如上图所示，从顶点2开始深度优先遍历图，结果为：2，0，1，3。对于一个有向图，假设从给定顶点可以访问到图的所有其他顶点，则DFS递归算法的C++代码实现：上面的代码是假设从给定顶点可以访问到图的所有其他顶点。如果没有这个假设，为了对图作一个完整的深度优先遍历，我们需要对每个顶点调用DFSUtil()。当然那之前需要先检查顶点是否已经访问过。所以我们只需要修改DFS()函数部分：对于无向图的深度优先搜索，只是邻接表不一样，其他的都是一样的。