Problem6937--学习系列 —— 图的连通性

6937: 学习系列 —— 图的连通性

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

【基本概念】

1. 连通图与连通分量

1）连通图：无向图 $G$ 中，若对任意两点，从顶点 $V_i$ 到顶点 $V_j$ 有路径，则称 $V_i$ 和 $V_j$ 是连通的，图 $G$ 是一连通图。

2）连通分量：无向图 $G$ 的连通子图称为 $G$ 的连通分量
    任何连通图的连通分量只有一个，即其自身，而非连通的无向图有多个连通分量。

以上图为例，总共有四个连通分量，分别是：ABCD、E、FG、HI。

2. 强连通图与强连通分量

1）强连通图：有向图 $G$ 中，若对任意两点，从顶点 $V_i$ 到顶点 $V_j$，都存在从 $V_i$ 到 $V_j$ 以及从 $V_j$ 到 $V_i$ 的路径，则称 $G$ 是强连通图。
2）强连通分量：有向图 $G$ 的强连通子图称为 $G$ 的强连通分量。
    强连通图只有一个强连通分量，即其自身，非强连通的有向图有多个强连通分量。

以上图为例，总共有三个强连通分量，分别是：abe、fg、cdh

【判断图的连通性】

判断图的连通性的常见方法有三种：DFS、BFS 和并查集。

DFS

深度优先遍历得到的是图的一个连通分量。

算法流程 

(1). 从某个结点 v 出发，访问结点 v，并令 vis[v] = 1；
(2). 查找 v 的所有邻接点 i，若结点 i 并未被访问过（vis[i] = 0），则从结点 i 出发，深度优先遍历图，转至步骤 (1)。
(3). 递归结束后，遍历 vis 数组，若数组中有一个值不为 1，则说明该点未被访问，图不连通。

BFS

算法流程 

(1). 从某个结点 v 出发，将结点 v 放入队列 q 中；
(2). 队列不空时，弹出队首结点 v；
    (2.1). 如果结点 v 没被访问过，查找 v 的所有邻接点 i；
        (2.1.1). 如果结点 i 没被访问过，放入队列 q 中；
        (2.1.2). 如果结点 i 已被访问，跳过。
    (2.2). 如果结点 v 已被访问，跳过。
    (2.3). 标记结点 v 已被访问（容易遗漏！！！）。
(3). 队列为空时，遍历 vis 数组，若数组中有一个值不为 1，则说明该点未被访问，图不连通。

并查集

并查集可以简单理解为找根结点，使用 fa 数组记录每个结点的根节点。

算法流程 

(1). 初始化每个结点的根节点为结点本身；（可使用 iota() 函数）
(2). 从某个结点 v 开始，查找 v 的所有邻接点 i，如果结点 v 和结点 i 的根节点不同（fa[v] != fa[i]），则把两个结点的根节点设为下标较小的根节点（fa[v] = fa[i] = min(fa[v], fa[i])）。
(3). 循环结束时，遍历 fa 数组，若数组中有一个值不为 0，则说明该点的根节点并不是 0 号结点，图不连通。

Warshell

并。

tarjan

并。

比较

  1. DFS 和 BFS 都是记录结点是否已访问，而并查集是记录每个结点的根节点。
  2. 三种算法都需要查询当前结点的所有邻接点，因而建议以邻接表的形式存储图。
  3. 三种算法的时间复杂度和空间复杂度如下表所示，其中 $E$ 为边的数目，$V$ 为结点的数目。

时间复杂度 空间复杂度
DFS $O(E)$ $O(V)$
BFS $O(E)$ $O(V)$
并查集 $O(E)$ $O(V)$

参考代码 


#include <iostream>
#include <numeric>
#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> g;
int n;
vector<int> vis;
vector<int> father;

void dfs(int v) {
	cout << v << " ";
	vis[v] = 1;
	for (int i = 0; i < g[v].size(); i++) {
		if (!vis[g[v][i]]) {
			dfs(g[v][i]);
		}
	}
}

void bfs() {
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int v = q.front();
		cout << v << " ";
		q.pop();
		if (!vis[v]) {
			for (int i = 0; i < g[v].size(); i++) {
				if (!vis[g[v][i]]) {
					q.push(g[v][i]);
				}
			}
		}
		vis[v] = 1;
	}
}

int Find(int x) {
	int a = x;
	while (x != father[x]) {
		x = father[x];
	}
	while (a != father[a]) {
		int z = a;
		a = father[a];
		father[a] = x;
	}
	return x;
}

void Union(int a, int b) {
	int fA = Find(a);
	int fB = Find(b);
	father[a] = father = min(fA, fB);
}

int main() {
	n = 6;
	g = vector<vector<int>>(n, vector<int>());
	// 插入 6 条边（双向）
	g[0].push_back(1);
	g[0].push_back(2);
	g[0].push_back(5);
	g[1].push_back(0);
	g[2].push_back(0);
	g[2].push_back(3);
	g[3].push_back(2);
	g[3].push_back(4);
	g[3].push_back(5);
	g[4].push_back(3);
	g[5].push_back(0);
	g[5].push_back(3);
	
	// DFS
	vis = vector<int>(n, 0);
	dfs(0);
	cout << endl;
	//0 1 2 3 4 5

	// BFS
	vis = vector<int>(n, 0);
	bfs();
	cout << endl;
	//0 1 2 5 3 3 4
	
	// Union-Find Set
	father = vector<int>(n);
	iota(father.begin(), father.end(), 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < g[i].size(); j++) {
			if (father[i] != father[g[i][j]]) {
				cout << i << " " << g[i][j] << endl;
				Union(i, g[i][j]);
			}
		}
	}
	//0 1
	//0 2
	//0 5
	//2 3
	//3 4
	
	// 可通过求和判断数组内所有元素是否都为 0：
	cout << (accumulate(father.begin(), father.end(), 0) == 0) << endl;	//1
	return 0;
}

Input

https://blog.csdn.net/u011815404/article/details/83217012

Source/Category

 
Submit