图的深度优先遍历和联通分量_调用2次深度优先遍历算法才完成了对某图的遍历,说明某图有2个连通分量
赞
踩
目录
图的深度优先遍历和联通分量
前面已经探讨了图的两种表示方法:邻接表表示法和邻接矩阵表示法。这两种表示法分别用在不同的场景上。邻接矩阵表示法主要用在稠密图中，邻接表表示法主要用在稀疏图中。在上一次讨论中，我们为了能够遍历每个节点的与之相邻的所有节点，从而设计出了相应的迭代器，使得能更好的访问每个节点与之相邻的节点。那么，接下来我们就要讨论如何去完整的遍历一个图中所有的点呢？
深度优先遍历算法
首先来介绍一下深度优先遍历算法的具体解释：
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
再来看一下我的理解：所谓的深度遍历算法和前面所讲解的二叉树的深度遍历算法其实是同一个道理。但是二叉树的结构与树的结构又不同，所以图使用的深度优先遍历算法与二叉树的深度优先遍历算法还是由一点点小的区别的。那么区别在哪里呢？首先，二叉树一定存在叶子节点，也就是说深度搜索到一定的深度后，会因为到了叶子节点无路而走，从而返回上一节点重新进行深度遍历。但是图却不一样的，图不像树存在叶子节点，即可以让深度搜索结束的条件，再加上图中可能存在“环形结构”，将会导致深度搜索一直在“转圈圈”。例如下图所示：
那么，该如何去解决这问题呢？答案当然是有的，既然图的深度搜索可能会发生“转圈圈”，那么我们所需要解决的问题就是如何改进深度搜索算法，使其能够停止下来。这很容易实现，我们只需要在使用额外的一个辅助数组visited[ ]即可。假设当前访问了某一个节点i，我们就标记其状态为已经被访问状态，在辅助数组中表示为visited[i]=true。这样，当深度搜索在搜索前，先参考visited[ ]数组，判断要访问的节点是否已经被访问过了，如果被访问过了则跳过该节点继续进行深度搜索。
具体的搜索思路
下面我们来参照上图看一下具体的图的深度搜索思路，我们先把每个节点与之相连的节点给标出来，如下图所示：
首先，我们从0号节点进行进行搜索，查找辅助表visited发现visited[0]=false,即0号节点从未被搜索过，所以我们搜索完0号节点标记其visit状态为真，即修改辅助表visited【0】=true。接下来的任务是要遍历0号节点的所有的相邻节点，所以我们遍历1号节点，发现其visited状态为false，说明这个节点从未被遍历过，接下来我们就修改其visited状态为true,即visited[1]=true。之后，有些同学可能会想当然的遍历0号节点的第2个邻接点2号节点，这可是大错特错了！何为深度优先遍历算法，我认为其精髓就是这句话：尽可能深的搜索图的所有邻节点。（搜索条件：深度>广度）既然1号节点也存在着邻节点，那么我们就应该“钻牛角尖”，永不放弃，尽可能深的去搜索邻节点，所以搜索完1号节点，不能返回去搜索0号节点的其他邻节点，而是继续往深处去探索1号节点的邻节点。
而1节点再往深处搜，其只有一个邻节点：0号节点。显然，0号节点已经被搜索过了，即1号节点的所有邻节点已经都被搜索过了，那么我们在1号节点就不能往下“钻”了。已经满足了“深“这个条件，接下来就应该满足“广度”这个条件了。””然后我们返回上一层的0号节点，再来看0号节点其他的邻节点，2号节点未被访问，则访问2号节点，访问完后发现2号节点也存在邻节点，则应该先满足“深”的条件，继续对2号节点的邻节点搜索，发现2号节点的所有邻节点（其实只有一个0号节点已经被访问过了），那么我们完成了“广度”的条件。在返回上一层继续......总而言之，对于每个节点来说，能深度往下搜下去就尽量往深处搜，实在深不下去了，在返回上一层完成“广”的搜索，就这样一直递归下去，图中所有的节点一定会全部被访问到的。
联通分量的计算
对于深度遍历算法来说，有一个很好的优点，就是能够非常方便的计算图中的联通分量，例如在下图中：
其中，在一个图中，存在3个部分，在图论中，这三个小的部分我们就称作为3个联通分量。联通分量和联通分量之间没有任何边相连。那么如何通过深度遍历算法来计算一个图中的联通分量个数呢？首先，先定义一个ccount变量用来记录联通分量的数目和联通分量所属的序号，接下来我们从左上角的第一个点开始进行深度遍历，我们会发现，遍历4个点之后将会结束遍历，这说明这4个点属于同一个联通分量之中，因为是第一个联通分量，所以该联通分量的序号（该联通分量所有节点的序号）即为cccount的值：为0，既然找到了一个联通分量，则ccount++变成1,。接下来，我们在从所有的点中找出下一个未被访问过的点，在执行一深度遍历算法，直到算法停止，说明又找到一个联通分量,，这这个联通分量的序号为1（该联通分量所有节点的序号）。接下来又继续找一个未被访问过的点进行深度遍历操作，直到停止，联通分量数加一，联通分量序号加一.......。有了上面的基础工作，则判断量节点是否处于同一个联通分量就很简单了，只需要比较两个节点的分别对应的联通序号是不是一样的，就能得出两个节点是不是处于同一个联通分量中。
关键代码实现
- 深度搜索函数的类实现
- template <typename Graph>
- class ComPonent{//ComPonent为一个计算图联通分量有关的类
- private:
- Graph &G;//接受需要检测的图
- bool *visited;//visited数组用来记录节点是否被访问过
- int ccount;//记录联通分量的个数
- int *id;//id数组记录每个节点所在的联通分量的编号
-
- void dfs(int v){//dfs主函数
- visited[v]= true;
- id[v]=ccount;//给节点分配上相对应的联通分量的序号
- typename Graph::adjIterator adj(G,v);
- for(int i=adj.begin();!adj.end();i=adj.next()){//遍历节点的所有邻节点，并对其使用dfs深度算法
- if(!visited[i]){
- dfs(i);
- }
- }
- }
- public:
-
- ComPonent(Graph&graph):G(graph){
-
- visited=new bool[G.V()];
- id=new int[G.V()];
- ccount=0;
- for(int i=0;i<G.V();i++){//初始化visited数组，使所有的节点都为未访问状态
- visited[i]=false;
- id[i]=-1;//初始化所有节点的联通分量编号为-1
- }
- for(int i=0;i<G.V();i++){//对所有节点进行dfs操作
- if(!visited[i]){
- dfs(i);
- ccount++;
- }
- }
-
- }
-
- ~ComPonent(){
- delete[] visited;
- delete[] id;
- }
-
- int count(){//返回图中含有的联通分量的个数
- return ccount;
- }
-
- bool isConnect(int v,int w){//判断两个节点是否处于同一个联通分量上
- return id[v]==id[w];
- }
-
- };
- 主函数测试
- int main() {
- int N=20;
- int M=20;//生成一个有20个节点，100条边的图
- srand(time(NULL));
- DenseGraph g2(N, false);//生成一个无向的稠密图用来进行测试
- for(int i=0;i<M;i++){//随机的对图中的节点连接M条边
- int a=rand()%N;
- int b=rand()%N;
- g2.addEdge(a,b);
- }
- ComPonent<DenseGraph> ComPonent1(g2);
- cout<<"the graph has "<<ComPonent1.count()<<" Component(s)"<<endl;
- cout<<ComPonent1.isConnect(3,7);
-
- return 0;
- }
多次执行结果如下：
其中图中的点与点之间的边每次都是是随机连的，然后测试每次图中的联通分量个数，以及3和7节点是否处于同一个联通分量中。
完整代码获取
如果需要获取整个工程的所有文件，欢迎访问我的GitHub，点击此处移步。
博客文章版权说明
第一条 本博客文章仅代表作者本人的观点，不保证文章等内容的有效性。
第二条 本博客部分内容转载于合作站点或摘录于部分书籍，但都会注明作/译者和原出处。如有不妥之处，敬请指出。
第三条 在征得本博客作者同意的情况下，本博客的作品允许非盈利性引用，并请注明出处：“作者：____转载自____”字样，以尊重作者的劳动成果。版权归原作/译者所有。未经允许，严禁转载。
第四条 对非法转载者，“扬俊的小屋”和作/译者保留采用法律手段追究的权利。
第五条 本博客之声明以及其修改权、更新权及最终解释权均属“扬俊的小屋”。
第六条 以上声明的解释权归“扬俊的小屋”所有。
