1 强联通分量解释
SCC(stronglyConnectedComponents) 对于G(v, e)的一个子图中，其任何两个顶点都存在一个path相互到达;
拓扑排序的核心思路还是利用深度优先搜索，排序的基本思想为深度优先搜索正好只会访问每个顶点一次，如果将dfs的参数顶点保存在一个数据结构中，遍历这个数据结构就能访问图中的所有顶点，而遍历的顺序取决于这个数据结构的性质以及是在递归调用之前还是递归调用之后保存。
- 1 前序： 在递归调用之前将顶点加入队列 —- pre()方法
- 2 后序： 在递归调用之后将顶点加入队列 —- post()方法
- 3 逆后序： 在递归调用之后将顶点压入栈 —- reversePost()方法
这里给出一个逆后序的例子：
其逆后序得到的一个栈为：(右侧为栈顶，代表最晚完成访问的节点) 6 4 2 5 3 1
逆后序获得代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
public class DepthFirstOrder {
private boolean[] marked;
private Queue<Integer> pre;
private Queue<Integer> post;
private Stack<Integer> reversePost;
public DepthFirstOrder(Digraph G){
pre = new Queue<Integer>();
post = new Queue<Integer>();
reversePost = new Stack<Integer>();
marked = new boolean[G.V()];
for(int v =0;v<G.V();v++)
if(!marked[v]) dfs(G,v);
}
private void dfs(Digraph G,int v){
pre.enqueue(v);
marked[v] = true;
for(int w:G.adj(v))
if(!marked[w])
dfs(G,w);
post.enqueue(v);
reversePost.push(v);
}
public Iterable<Integer> pre(){
return pre;
}
public Iterable<Integer> post(){
return post;
}
public Iterable<Integer> reversePost(){
return reversePost;
}
}
|
3 求解算法
3.1 kosaraju算法
https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm 伪代码:
- For each vertex u of the graph, mark u as unvisited. Let L be empty.
- For each vertex u of the graph do Visit(u), where Visit(u) is the recursive subroutine:
- If u is unvisited then:
- Mark u as visited.
- For each out-neighbour v of u, do Visit(v).
- Prepend u to L.
- Otherwise do nothing.
- For each element u of L in order, do Assign(u,u) where Assign(u,root) is the recursive subroutine:
- If u has not been assigned to a component then:
- Assign u as belonging to the component whose root is root.
- For each in-neighbour v of u, do Assign(v,root).
- Otherwise do nothing.
换句话说：
主要就是2次dfs：
- 1 获得G的逆图G’，对G做一遍dfs获得其逆后序的顶点访问序列
- 2 对于逆后序顶点访问序列，重复2.1即可
- 2.1 将最晚完成访问的顶点，在G’中访问，能够一遍到达的那些顶点，就是目标的连通分量，将相关顶点在逆后序访问序列中移除即可
3.2 Tarjan算法（待续）
参考： https://www.cnblogs.com/wuchanming/p/4138705.html
3.3 Gabow算法(待续)
参考： https://www.cnblogs.com/wuchanming/p/4138705.html
具体的例子：
4 实际题解
4.1 针对无向图连通分量求解
该解题方案实际上为有向图强联通分量求解的一个子集，无向图即为顶点和顶点之间的边均为双向边。
这里以kosaraju算法为例:
- 1 对于有向图，一开始我们需要获取dfs的逆序遍历栈，原因是，在第二次dfs也就是逆图中的遍历我们可以总是用最晚完成遍历的点去遍历，如此依赖，这样的一个遍历就能得到一个连通分量。
- 2 但是针对无向图，不需要这样，因为遍历到不能拓展新的节点，我们就获取到了一个连通分量。
https://leetcode-cn.com/problems/number-of-provinces/
其解法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| class Solution {
public:
void dfs(vector<vector<int>>& g, vector<int>& reversePost, vector<bool>& vis, int tarV) {
vis[tarV] = true;
for(int j = 0; j < g.size(); ++j) {
if(g[tarV][j] != 0) {
if(!vis[j]) {
dfs(g, reversePost, vis, j);
}
}
}
reversePost.emplace_back(tarV);
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<vector<int>> revIsConnected(isConnected);
vector<bool> vis(n, false);
vector<int> reversePost;
int ans = 0;
for(int j = 0; j < isConnected.size(); ++j) {
if(!vis[j]) {
dfs(isConnected, reversePost, vis, j);
ans ++;
}
}
return ans;
}
};
class Solution {
public int findCircleNum(int[][] isConnected) {
int provinces = isConnected.length;
int[] parent = new int[provinces];
for (int i = 0; i < provinces; i++) {
parent[i] = i;
}
for (int i = 0; i < provinces; i++) {
for (int j = i + 1; j < provinces; j++) {
if (isConnected[i][j] == 1) {
union(parent, i, j);
}
}
}
int circles = 0;
for (int i = 0; i < provinces; i++) {
if (parent[i] == i) {
circles++;
}
}
return circles;
}
public void union(int[] parent, int index1, int index2) {
parent[find(parent, index1)] = find(parent, index2);
}
public int find(int[] parent, int index) {
if (parent[index] != index) {
parent[index] = find(parent, parent[index]);
}
return parent[index];
}
}
|
4.2 针对有向图连通分量的求解
参考例子