1. 连通分量是什么
无向图G的极大连通子图称为G的连通分量( Connected Component)。任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。
2. 案例
2.1.图极其数据结构初始化
2.2.求连通分量的方法
从每个顶点出发，判断是否有连通分量
BFS[BFS](https://blog.csdn.net/qq_44423388/article/details/127591933?spm=1001.2014.3001.5501)
DFS[DFS](https://blog.csdn.net/qq_44423388/article/details/127583096?spm=1001.2014.3001.5501)
并查集（本篇主讲,实现步骤见下）
文章来源：https://www.toymoban.com/news/detail-554345.html
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都会对其进行改变，所有设置两个book
vector<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，数组book
void 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;
}
文章来源地址https://www.toymoban.com/news/detail-554345.html
到了这里，关于三种方法求图中连通分量的个数（BFS、DFS、并查集）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
