求图的连通分量

求图的连通分量

什么是连通分量

无向图G的一个极大连通子图称为G的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。

实现代码

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
package GraphBasics;

/**
* @ Description: 求无全图的联通分量
* @ Date: Created in 12:37 2018/8/1
* @ Author: Anthony_Duan
*/
public class Components {

//图的引用
Graph G;
//激励dfs的过程中节点是否被访问
private boolean[] visited;
//记录联通分量个数
private int ccount;
//每个节点所对应的联通分量标记
private int[] id;

//图的深度优先遍历
void dfs(int v) {
visited[v] = true;
id[v] = ccount;
for (int i :
G.adj(v)) {
if (!visited[i]) {
dfs(i);
}
}
}

//构造函数,求出无全图的联通分量
public Components(Graph graph) {
//算法初始化
G = graph;
visited = new boolean[G.V()];
id = new int[G.V()];
ccount = 0;
for (int i = 0; i < G.V(); i++) {
visited[i] = false;
id[i] = -1;
}

//求图的联通分量
for (int i = 0; i < G.V(); i++) {
if (!visited[i]) {
dfs(i);
ccount++;
}
}
}

//返回图中联通分量的个数
int count() {
return ccount;
}


//查询v和w是否联通
boolean isConnected(int v, int w) {
assert v >= 0 && v < G.V();
assert w >= 0 && w < G.V();
return id[v] == id[w];
}
}
-------------End Of This ArticleThank You For Reading-------------