一、连通分量
1.1 定义
连通分量是针对无向图的，无向图G的极大连通子图称为G的连通分量( Connected Component)。
任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。
连通分量的API定义：
1-1 连通分量的API定义
1.2 基本思想
求一幅无向图的连通分量步骤如下：
- 任意选取一个顶点，进行深度优先遍历；
遍历过程中遇到的所有顶点加入同一个连通分量。 - 然后选取其它未访问过的顶点，再进行深度优先遍历；
遍历过程中遇到的所有顶点加入另一个连通分量。 - 重复上述步骤，直到遍历完所有顶点。
1.3 源码实现
public class CC {
private boolean[] marked; // marked[v] = has vertex v been marked?
private int[] id; // id[v] = id of connected component containing v
private int[] size; // size[id] = number of vertices in given component
private int count; // number of connected components
/**
* Computes the connected components of the undirected graph {@code G}.
*
* @param G the undirected graph
*/
public CC(Graph G) {
marked = new boolean[G.V()];
id = new int[G.V()];
size = new int[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);
count++;
}
}
}
/**
* Computes the connected components of the edge-weighted graph {@code G}.
*
* @param G the edge-weighted graph
*/
public CC(EdgeWeightedGraph G) {
marked = new boolean[G.V()];
id = new int[G.V()];
size = new int[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);
count++;
}
}
}
// depth-first search for a Graph
private void dfs(Graph G, int v) {
marked[v] = true;
id[v] = count;
size[count]++;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
}
// depth-first search for an EdgeWeightedGraph
private void dfs(EdgeWeightedGraph G, int v) {
marked[v] = true;
id[v] = count;
size[count]++;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (!marked[w]) {
dfs(G, w);
}
}
}
/**
* Returns the component id of the connected component containing vertex {@code v}.
*
* @param v the vertex
* @return the component id of the connected component containing vertex {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int id(int v) {
validateVertex(v);
return id[v];
}
/**
* Returns the number of vertices in the connected component containing vertex {@code v}.
*
* @param v the vertex
* @return the number of vertices in the connected component containing vertex {@code v}
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int size(int v) {
validateVertex(v);
return size[id[v]];
}
/**
* Returns the number of connected components in the graph {@code G}.
*
* @return the number of connected components in the graph {@code G}
*/
public int count() {
return count;
}
/**
* Returns true if vertices {@code v} and {@code w} are in the same
* connected component.
*
* @param v one vertex
* @param w the other vertex
* @return {@code true} if vertices {@code v} and {@code w} are in the same
* connected component; {@code false} otherwise
* @throws IllegalArgumentException unless {@code 0 <= v < V}
* @throws IllegalArgumentException unless {@code 0 <= w < V}
*/
public boolean connected(int v, int w) {
validateVertex(v);
validateVertex(w);
return id(v) == id(w);
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
int V = marked.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
/**
* Unit tests the {@code CC} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
Graph G = new Graph(in);
CC cc = new CC(G);
// number of connected components
int m = cc.count();
StdOut.println(m + " components");
// compute list of vertices in each connected component
Queue<Integer>[] components = (Queue<Integer>[]) new Queue[m];
for (int i = 0; i < m; i++) {
components[i] = new Queue<Integer>();
}
for (int v = 0; v < G.V(); v++) {
components[cc.id(v)].enqueue(v);
}
// print results
for (int i = 0; i < m; i++) {
for (int v : components[i]) {
StdOut.print(v + " ");
}
StdOut.println();
}
}
}
二、强连通分量
2.1 定义
强连通分量是针对有向图的。
强连通性：
如果有向图中两个顶点是相互可达的，即w->v和v->w都是可达，则称它们是强连通的。
强连通分量：
将有向图中的顶点分成一些子集，每个子集内的所有顶点之间都是强连通的，那每个子集都是该有向图的强连通分量。
2-1-1 强连通分量示意图
强连通分量的API定义：
2-1-2 强连通分量的API定义
2.2 基本思想
采用Kosaraju算法实现
具体步骤：
进行两次遍历，第一次后序遍历是为了保证，在第二次的遍历中，先访问到的强连通分量不指向任何未被访问到的强连通分量。
- 对原图G取反，得到反向图GR；
- 采用DFS遍历反向图GR，得到一个逆后序排列；
- 按照逆后序排列中顶点的顺序，对每个顶点进行深度优先遍历，即dfs(G, s)，遍历过程中遇到的所有顶点属于同一个强连通分量，依次遍历直到所有顶点都遍历完成。
算法证明：
首先假设已经有一个逆后序排列，…,s,…,v,…。
- 调用dfs(G,s)过程中，遇到的任意顶点v，一定存在路径s->v。（对应GR中存在路径v->s）；
- 要证明s和v是强连通的，只需要证明G中存在路径v->s；
- 要证明G中存在路径v->s，只需要证明GR中存在路径s->v；
- 由于…,s,…,v,…是GR的一个逆后续排列，所以dfs(GR,v)肯定先于dfs(GR,s)结束。那么对dfs(GR,v)的调用只有两种情况：
①dfs(GR,v)在dfs(GR,s)前调用，并且在dfs(GR,s)开始前结束；
②dfs(GR,v)在dfs(GR,s)后调用，并且在dfs(GR,s)结束前结束。
第①种情况说明v->s之间没有路径，但是由1可知，GR中存在路径v->s，所以这种情况不可能。
第②种情况说明s->v之间有路径。
2.3 源码实现
public class KosarajuSharirSCC {
private boolean[] marked;
// id[v]表示顶点v所在的强连通分量标识
private int[] id;
// 强连通分量总数
private int count;
public KosarajuSharirSCC(Digraph G) {
//得到原图的反向图的逆后序排列
Iterable<Integer> revs=G.reverse().reversePost();
marked = new boolean[G.V()];
id = new int[G.V()];
for (int v : revs) {
if (!marked[v]) {
dfs(G, v);
count++;
}
}
}
private void dfs(Digraph G, int v) {
marked[v] = true;
id[v] = count;
for (int w : G.adj(v)) {
if (!marked[w])
dfs(G, w);
}
}
public boolean stronglyConnected(int v, int w) {
return id[v] == id[w];
}
}
2.4 性能分析
- 时间复杂度
O(V+E) - 空间复杂度
O(V+E)
