找出无向图中所有的连通子图
1 图的数据如下
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
2 C++代码如下
/* * CC.h * * Created on: 2014年6月3日 * Author: zhongchao * 计算无向图中的连通分量 */ #ifndef _CC_ #define _CC_ #include "Graph.h" class CC { private: bool* mark; int* _id; int num; Graph* _graph; hash_set<int> nodes; public: CC(Graph* graph, int n); ~CC(); bool connected(int a, int b); //节点a和b是否在同一连同子图中 int count(); int id(int a); //节点a所属于的连同子图的索引 void dfs(Graph* graph, int n); void printAllCC(); }; void dfsTest(); #endif /* _CC_*/
/* * CC.cpp * * Created on: 2014年6月3日 * Author: zhongchao */ /* * DFS.cpp * * Created on: 2014年6月1日 * Author: zhongchao */ #include "CC.h" CC::CC(Graph* graph, int n): _graph(graph),num(0) { mark = new bool[graph->v()]; for(int i = 0; i < graph->v(); i++) { mark[i] = false; } _id = new int[graph->v()]; hash_set<int> nodes = graph->getNodes(); for(hash_set<int>::iterator it = nodes.begin(); it != nodes.end(); it++) { if(mark[*it] != true) { dfs(graph, *it); num++; } } } void CC::dfs(Graph* graph, int n) { mark[n] = true; _id[n] = num; vector<int> ns = graph->getEdges(n); for(vector<int>::iterator it = ns.begin(); it != ns.end(); it++) { if(mark[*it] == true) continue; dfs(graph, *it); } } bool CC::connected(int a, int b) { return _id[a] == _id[b]; } int CC::id(int a) { return _id[a]; } void CC::printAllCC() { hash_set<int> nodes = _graph->getNodes(); for(hash_set<int>::iterator it = nodes.begin(); it != nodes.end(); it++) { cout<<*it<<" belong to "<<_id[*it]<<endl; } } int CC::count() { return num; } CC::~CC() { delete[] mark; } void ccTest() { string path("/home/zhongchao/worksapce/cpp/ComputeAlgorithms/data/tinyG.txt"); Graph* graph = new Graph(path); int n = 0; CC* cc = new CC(graph, n); cc->printAllCC(); }
/* * Run.cpp * * Created on: 2014年5月25日 * Author: zhongchao */ #include "Graph.h" #include "Prim.h" #include "Dijkstra.h" #include "DFS.h" #include "BFS.h" #include "CC.h" void bfsTest(); void dfsTest(); void ccTest(); void dfsTopological(); int main(int argc, char** argv) { ccTest(); return 1; }
3 连通子图如下
0 belong to 0
1 belong to 0
2 belong to 0
3 belong to 0
4 belong to 0
5 belong to 0
6 belong to 0
7 belong to 1
8 belong to 1
9 belong to 2
10 belong to 2
11 belong to 2
12 belong to 2
1 belong to 0
2 belong to 0
3 belong to 0
4 belong to 0
5 belong to 0
6 belong to 0
7 belong to 1
8 belong to 1
9 belong to 2
10 belong to 2
11 belong to 2
12 belong to 2