算法-深度优先遍历求图中的联通分量(C++)_联通变量

联通分量是在图中的一种特殊的表现形式。
类似于这种

在这个图中这里有三个联通变量
求这种联通变量的方法
1、将所有节点都设置一个二维bool矩阵
2、开始遍历节点，如果当前节点没有被访问过的话，那么就进行一次深度遍历
3、当进行了深度遍历后，发现已经遍历完了，没地方去了的话。就将联通变量的值++
4、算法完成
下面是具体的实现代码

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;

template<class Graph>
class Complate{
private:
	Graph &G;
	bool *visited;  //记录是否被访问到了 
	int ccount;  //记录有多少个联通分量 
	int *id;  //每两个节点是否相连 (相连的节点id相同 不相连的节点的id不相同)
	
	void dfs(int v){ //将v 和与v相连接的所有节点都进行遍历 
		visited[v] = true; //遍历到了v节点 变为true 
		id[v]  = ccount;  //比如第一组联通变量都是1 那么只有第二个联通变量id[v]的值才会改变 
		typename Graph::adjIterator adj(G,v); //遍历G这张图，v这个节点的它所有的相邻节点 
		for(int i = adj.begin();!adj.end();i = adj.next()){ //将v的所有相邻节点都存放在了i里面 
			if(!visited){  //看一下获得的相邻的节点是不是被访问过 
				dfs(i);  //如果它没有被访问过的话 就接着去访问它相邻的节点就可以了 
			}
		}
		
	}
public:
	Complate(Graph &graph):G(graph){
		visited = new bool[G.V()]; //指针开空间，有多少个节点就开多少个空间 
		id = new int[G.V()]; // new 一个新空间 
		ccount = 0; // 0 
		for(int i = 0;i<G.V();i ++){
			visited[i] = false;  //visited 初始化   每一个元素都没有被访问过 
			id[i] = -1;  //统一的值 
			
		}
		for(int i = 0;i<G.V();i ++){
			if(!visited[i]){  //如果当前遍历的节点没有被访问过的话，那么就进行一次深度遍历 
				dfs(i); //深度遍历函数 deep first search 
				ccount ++;  //记录有多少个联通分量 
			}
		}
		
	}
	~Complate(){ //析构函数
		delete[] visted;
		delete[] id;
		
	}
	int count(){
		return ccount;
	}
	
	bool isConnected(int v,int w){
		assert(v>=0 && v<G.V());
		assert(w>=0 && w<G.V());
		return id[v] == id[w];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

运行效果