图的连通性

图的连通性判断方法主要有：并查集、DFS、BFS、WARSHALL

一、并查集

使用并查集维护所有边，如果 parent 数组中只有一个 根节点 那么，此图是联通图。

若不是一个根节点，那么连通分支数为 根节点个数
int parent[maxn];
int find_root (int n) {
return parent[n] == -1 ? n : parent[n] = find_root(parent[n]);
}

//连通分支数 = parent 中 -1 个数
bool union_solve() {
memset(parent, -1, sizeof(parent));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (mapp[i][j]) {
int r1 = find_root(i), r2 = find_root(j);
if (r1 != r2)
parent[j] = r1;
}
}
}

//如果parent 中只有一个 根节点 那么就连通

int cnt = 0;

for (int i = 0; i < n; i++)

    if (parent[i] == -1)

        cnt++;

return cnt == 1 ? true : false; }

二、DFS

如果 vis 数组都是 true 说明是一个连通图. 否则 连通分支数 = 对图中所有点进行 dfs，运行了几次，说明就有几个连通分支数

bool vis[maxn];
void dfs(int x) {
vis[x] = true;
for (int i = 0; i < n; i++) {
if (mapp[x][i] && !vis[i])
dfs(i);
}
}

bool dfs_solve() {
memset(vis, 0, sizeof(vis));
dfs(0);
for (int i = 0; i < n; i++)
if (!vis[i])
return false;
return true;
}

三、BFS

如果 cnt 等于 n 那么就是一个连通图，否则连通分支数 = 对图中所有点进行 dfs，运行了几次，说明就有几个连通分支数
bool bfs_solve() {
int cnt = 0;
memset(vis, 0, sizeof(vis));
queue q;
q.push(0);
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = true;
cnt++;
for (int i = 0; i < n; i++)
if (mapp[x][i] && !vis[i]) {
q.push(i);
vis[i] = true; //保证cnt==n时访问全部点，防止一个节点被加入队列两次
}
}
return cnt == n;
}

四、WARSHALL 算法

这个算法主要是利用求解传递闭包的思想，如果图是连通图那么 这个连通矩阵是一个 全1 矩阵。如果不是连通图，那么在主对角线上，有几个 全1 矩阵那么就是几个连通分支

1. 连通图的连通矩阵为，例如 4 个点

1 1 1 1

1 1 1 1

1 1 1 1

1 1 1 1

1. 两个连通分支 连通矩阵为： 例如 4 个点

1 1 0 0

1 1 0 0

0 0 1 1

0 0 1 1

bool warshall_solve() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
mapp[i][j] = mapp[i][j] || (mapp[i][k] && mapp[k][j]);
mapp[i][i] = 1; //自己和自己连通
}
}

//矩阵中全为 1， 即表示连通图

for (int i = 0; i < n; i++)

    for (int j = 0; j < n; j++)

        if (!mapp[i][j])

            return false;

return true; }