三种方法求图中连通分量的个数（BFS、DFS、并查集）

编程入门行业动态更新时间:2024-10-12 01:29:33

三种方法求图中连通分量的个数（BFS、DFS、并查集）

1. 连通分量是什么

无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。

2. 案例

2.1.图极其数据结构初始化

2.2.求连通分量的方法

从每个顶点出发，判断是否有连通分量
BFS[BFS](=1001.2014.3001.5501)
DFS[DFS](=1001.2014.3001.5501)
并查集（本篇主讲,实现步骤见下）

2.3 具体实现

/*
测试用例：
1 2
1 4
2 4
*/#include <vector>
#include <iostream>
#include <queue>
#include <unordered_map>using namespace std;/*
如果节点是相互连通的（从一个节点可以到达另一个节点），那么他们在同一棵树里，或者说在同一个集合里，或者说他们的祖先是相同的。
*/
//并查集的数据结构
class UnionFind {private:// 记录每一个节点的父节点father<当前节点下标,父节点下标>unordered_map<int, int> father;// 记录集合数量int num_of_sets = 0;public://找节点x的父节点int find(int x) {int root = x;while (father[root] != -1) {root = father[root];}//优化的点：如果我们树很深，那么每次查询的效率都会非常低。这一步把树的深度固定为二。while (x != root) {int original_father = father[x];father[x] = root;x = original_father;}return root;}bool is_connected(int x, int y) {return find(x) == find(y);}//将连通的两个节点合并为同一个祖先，同时并查集的数目--void merge(int x, int y) {int root_x = find(x);int root_y = find(y);if (root_x != root_y){father[root_y] = root_x;num_of_sets--;}}//将新节点添加到并查集中void add(int x) {if (!father.count(x)){father[x] = -1;num_of_sets++;}}//返回并查集个数int get_num_of_sets(){auto it = father.begin();while (it != father.end()){cout << it->first<<" ->"<<it->second << endl;it++;}return num_of_sets;}
};class Connectedcomponent:protected UnionFind
{
private:int vertice = 0;//顶点数int edge = 0;//边数vector<vector<int>> e;//因为dfs和bfs都会对其进行改变，所有设置两个bookvector<bool> book;//判断顶点j是否扩展过vector<bool> book1;//判断顶点j是否扩展过queue<int> qu;//DFS求连通分量个数void DFS_Alg(int current, int sum)//current当前所在的节点编号{sum++;if (sum == vertice)//所有的节点均已被访问{cout << current << endl;return;}else{cout << current << " ->";}for (int k = 1; k <= vertice; k++){if (e[current][k] != 0 && book[k] == 0){book[k] = 1;DFS_Alg(k, sum);}}}public:Connectedcomponent(int x, int y) :vertice(x), edge(y){//图的初始化从下标1开始e.resize(vertice + 1);//初始化二维数组的行for (int i = 0; i <= vertice; i++){e[i].resize(vertice + 1,0);//初始化二维数组的列}book.resize(vertice + 1);book1.resize(vertice + 1);}//图的初始化void Init_tu(){for (int i = 0; i <= vertice; i++){for (int j = 0; j <= vertice; j++){if (i == 0 || j == 0){e[i][j] = 0;}if (i == j){e[i][j] = 0;}else{e[i][j] = INT_MAX;}}}}//读入图的边，并且根据边的信息初始化数组dis，数组bookvoid GetEdgeInfo(){cout << "输入边的信息（节点1，节点2）：" << endl;int e1 = 0, e2 = 0, weigth = 0;for (int i = 1; i <= edge; i++)//无向图{cin >> e1 >> e2;e[e1][e2] = 1;e[e2][e1] = 1;}        }//打印void Print(){for (int i = 1; i <= vertice; i++){for (int j = 1; j <= vertice; j++){cout << e[i][j] << "    ";}cout << endl;}cout << endl;}int DFS_Num(){int num = 0;for (int i = 1; i <= vertice; i++){if (book[i] == false){DFS_Alg(i,0);cout <<"end" <<endl;num++;}               }return num;}//BFS求连通分量个数int BFS_Num(){     int num = 0;for (int i = 1; i <= vertice; i++)//遍历每个节点，查看是否从该节点出发是否有连通分量{if (book1[i] == false){qu.push(i);while (!qu.empty()){int v = qu.front();qu.pop();book1[v] = true;cout << v << "->";for (int i = 1; i <= vertice; i++)//循坏找节点v的相邻节点{if (e[v][i] != 0 && book1[i] == false){qu.push(i);book1[i] = true;}}}num++;}            cout << "end" << endl;}return num;       }//并查集求连通分量的个数/*每个节点会记录它的父节点。*/int UnionFindSet(){UnionFind uf;for (int i = 1; i <= vertice; i++){uf.add(i);for (int j = 1; j < i; j++){if (e[i][j] == 1){uf.merge(i, j);}}}return uf.get_num_of_sets();}
};int main()
{int num1 = 0, num2 = 0,num3 = 0;Connectedcomponent Conn(5, 3);Conn.GetEdgeInfo();cout << "初始信息：" << endl;Conn.Print();cout << "DFS:::" << endl;num1 = Conn.DFS_Num();cout << "BFS:::" << endl;num2 = Conn.BFS_Num();cout << "Union Find Set:::" << endl;num3 = Conn.UnionFindSet();cout << num1 << "  " << num2 <<"   "<<num3<< endl;return 0;
}