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)
并查集（本篇主讲,实现步骤见下）
2.3 具体实现
/*
测试用例：
1 2
1 4
2 4
*/
#include
#include
#include
#include
using namespace std;
/*
如果节点是相互连通的（从一个节点可以到达另一个节点），那么他们在同一棵树里，或者说在同一个集合里，或者说他们的祖先是相同的。
*/
//并查集的数据结构
class UnionFind {
private:
// 记录每一个节点的父节点father<当前节点下标,父节点下标>
unordered_map
// 记录集合数量
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++;
}
return num_of_sets;
}
};
class Connectedcomponent:protected UnionFind
{
private:
int vertice = 0;//顶点数
int edge = 0;//边数
vector
//因为dfs和bfs都会对其进行改变，所有设置两个book
vector
vector
queue
//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" < 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 <<" "< return 0; }