图论算法（6） --- Tarjan算法求强连通分量

注：此算法以有向图作为输入，并按照所在的强连通分量给出其顶点集的一个划分。graph中的每个节点只在一个强连通分量里出现，即使是单点。


任选一点开始进行深度优先搜索（若dfs结束后仍有未访问的节点，则再从中任选一点再从进行）。搜索过程中已访问的节点不再访问。搜索树的若干子树构成了图的强连通分量。


节点按照被访问的顺序存入栈中。从搜索树的子树返回至一个节点时，检查该节点是否是某一连通分量的根节点，并将其从栈中删除。如果某节点是强连通分量的根，则在它之前出栈且还不属于其他强连通分量的节点构成了该节点所在的强连通分量。


注：根节点的性质
算法的关键在于如何判定某节点是否是强连通分量的根。对于“强连通分量的根”这一说法仅针对此算法。事实上，强连通分量没有特定的“根”的。在这里根节点指深度优先搜索时强连通分量的节点构成了该节点所在的强连通分量。

为找到根结点，我们给每个结点v一个深度优先搜索标号v.index，表示它是第几个被访问的结点。此外，每个结点v还有一个值v.lowlink，表示从v出发经有向边可到达的所有结点中最小的index。显然v.lowlink总是不大于v.index，且当从v出发经有向边不能到达其他结点时，这两个值相等。v.lowlink在深度优先搜索的过程中求得，v是强连通分量的根当且仅当v.lowlink = v.index。

algorithm tarjan is
  input: 图 G = (V, E)
  output: 以所在的强连通分量划分的顶点集


  index := 0
  S := empty    // 置栈为空
  for each v in V do
    if (v.index is undefined)
      strongconnect(v)
    end if


  function strongconnect(v)
    // 将未使用的最小index值作为结点v的index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)


    // 考虑v的后继结点
    for each (v, w) in E do
      if (w.index is undefined) then
        // 后继结点w未访问，递归调用
        strongconnect(w)
        v.lowlink := min(v.lowlink, w.lowlink)
      else if (w is in S) then
        // w已在栈S中，亦即在当前强连通分量中
        v.lowlink := min(v.lowlink, w.index)
      end if


    // 若v是根则出栈，并求得一个强连通分量
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        add w to current strongly connected component
      until (w = v)
      output the current strongly connected component
    end if
  end function

变量index是深度优先搜索的结点计数器。S是栈，初始为空，用于存储已经访问但未被判定属于任一强连通分量的结点。注意这并非一个一般深度优先搜索的栈，结点不是在以它为根的子树搜索完成后出栈，而是在整个强连通分量被找到时。


最外层循环用于查找未访问的结点，以保证所有结点最终都会被访问。strongconnect进行一次深度优先搜索，并找到结点v的后继结点构成的子图中所有的强连通分量。


当一个结点完成递归时，若它的lowlink仍等于index，那么它就是强连通分量的根。算法将在此结点之后入栈（包含此结点）且仍在栈中的结点出栈，并作为一个强连通分量输出。


备注：


1.复杂度:对每个结点，过程strongconnect只被调用一次；整个程序中每条边最多被考虑两次。因此算法的运行时间关于图的边数是线性的，即O(|V|+|E|)。


2.判断结点v'是否在栈中应在常数时间内完成，例如可以对每个结点保存一个是否在栈中的标记。


3.同一个强连通分量内的结点是无序的，但此算法具有如下性质：每个强连通分量都是在它的所有后继强连通分量被求出之后求得的。因此，如果将同一强连通分量收缩为一个结点而构成一个有向无环图，这些强连通分量被求出的顺序是这一新图的拓扑序的逆序。

下面附上实现源代码：

/*
 * Author : YANG Xiangyu
 * 
 * Hint: tarjan scc
 * 
 * The Chinese University of *
 */
package cyclefinder;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.Vector;

public class TarjanSCC{
class Node{//内部类定义节点
Vector<Integer> adj;
}
Node[] graph;
Stack<Integer> stack;
int indices;
boolean[] inStack;
int[] index;
int[] lowLink;
int[] component;
Set<Integer> nodeset;
int numComponents;
int n,m;
public TarjanSCC(){
graph=new Node[16000];
inStack=new boolean[16000];
index=new int[16000];
lowLink=new int[16000];
component=new int[16000];
inStack=new boolean[16000];
stack=new Stack<Integer>();
nodeset=new HashSet<Integer>();
for(int i=0;i<component.length;++i){
component[i]=0xffffffff;
}
for(int i=0;i<graph.length;++i){
graph[i]=new Node();
graph[i].adj=new Vector<Integer>();
}
}

public void strongconnect(int v){
index[v]=indices;
lowLink[v]=indices;
indices++;
stack.push(v);
inStack[v]=true;
for(int j=0;j<graph[v].adj.size();++j){
int w=graph[v].adj.get(j);
if(index[w]==0){
strongconnect(w);
lowLink[v]=Math.min(lowLink[v],lowLink[w]);
}else if(inStack[w]){
lowLink[v]=Math.min(lowLink[v],index[w]);
}
}
if(lowLink[v]==index[v]){
int w=0;
do{
w=stack.pop();
component[w]=numComponents;
inStack[w]=false;
}while(v!=w&&!stack.empty());
numComponents++;
}
}
public void tarjanFunc(){
indices=1;
while(!stack.empty()){
stack.pop();
}
Object[] v=nodeset.toArray();
for(int i=0;i<v.length;++i){
lowLink[(int) v[i]]=0;
index[(int) v[i]]=0;
inStack[(int) v[i]]=false;
}
numComponents=0;
for(int i=0;i<v.length;++i){
if(index[(int) v[i]]==0){
strongconnect((int) v[i]);
}
}
}

public void input(String path) throws FileNotFoundException{
Scanner input=new Scanner(new File(path));
n=input.nextInt();
m=input.nextInt();
int a=0,b=0;
for(int i=0;i<m;++i){
a=input.nextInt();
b=input.nextInt();
graph[a].adj.add(b);
nodeset.add(a);
}
input.close();
}
public void prints(String path) throws FileNotFoundException
{
PrintStream output = new PrintStream(path);
for(int i=0;i<16000;++i){
output.print(component[i]+" "+i+" ");
for(int j=0;j<graph[i].adj.size();++j){
output.print(graph[i].adj.get(j)+" ");
}
output.println();
}
System.out.println(numComponents);
output.println(numComponents);
output.close();
}
public static void main(String[] args) throws FileNotFoundException{
TarjanSCC tarjanscc=new TarjanSCC();
tarjanscc.input("C:/circleOrderedId.txt");
tarjanscc.tarjanFunc();
tarjanscc.prints("C:/tarjansccresults.txt");
}
}

给一组测试数据：
7 9
1 2
2 3
3 1
4 2
3 4
3 5
5 6
6 7
7 5

第一行为点的个数和边的个数，剩下各行为某两点组成的边。

输出为：

1 1 2
1 2 3
1 3 1 4 5
1 4 2
0 5 6
0 6 7
0 7 5
2
代表1234（第二列）属于一个强连通分量（编号1，第一列），567（第二列）属于一个强连通分量（编号0，第一列），每个点的邻接点为后面跟着的数字（第三列及之后）。

最后一行为强两通分量个数2。

对于上面的代码实现用到了固定大小数组，扩展起来似乎并不是很方便，在java里这样来实现本身就是不太妥当的，所以下面再给出一个更新版本的代码实现：

package test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TarjanSCC<NodeType> {
int index;
Map<NodeType, LinkedList<NodeType>> graph;
Map<NodeType, Integer> indexMap;
Map<NodeType, Integer> lowLinkMap;
Stack<NodeType> stack;
List<List<NodeType>> result;

public TarjanSCC(Map<NodeType, LinkedList<NodeType>> graph) {
this.index = 0;
this.graph = graph;
this.indexMap = new HashMap<NodeType, Integer>();
this.lowLinkMap = new HashMap<NodeType, Integer>();
this.result = new ArrayList<List<NodeType>>();
}

public List<List<NodeType>> tarjan() {
this.index = 0;
stack = new Stack<NodeType>();
List<List<NodeType>> result = new ArrayList<List<NodeType>>();
for (NodeType v : this.graph.keySet()) {
if (indexMap.get(v) == null) {
result.addAll(this.strongConnect(v));
}
}
return result;
}

public List<NodeType> getSuccessors(NodeType v,Map<NodeType, LinkedList<NodeType>> graph) {
List<NodeType> successors = new ArrayList<NodeType>();
Set<NodeType> set = graph.keySet();
Iterator<NodeType> it = set.iterator();
while (it.hasNext()) {
NodeType node = it.next();
if (node.equals(v)) {
successors.addAll(graph.get(node));
break;
}
}
return successors;
}

public List<List<NodeType>> strongConnect(NodeType v) {
indexMap.put(v, index);
lowLinkMap.put(v, index);
index++;
stack.push(v);
for (NodeType w : getSuccessors(v, graph)) {
if (indexMap.get(w) == null) {
strongConnect(w);
lowLinkMap.put(v, Math.min(lowLinkMap.get(v), lowLinkMap.get(w)));
} else if (stack.contains(w)) {
lowLinkMap.put(v, Math.min(lowLinkMap.get(v), indexMap.get(w)));
}
}
if (lowLinkMap.get(v).equals(indexMap.get(v))) {
List<NodeType> sccList = new ArrayList<NodeType>();
while (true) {
NodeType w = stack.pop();
sccList.add(w);
if (w.equals(v)) {
break;
}
}
if (sccList.size() > 1) {
result.add(sccList);
}
}
return result;
}
}

下面是主函数调用代码：

package test;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class TestTarjan {
Map<Integer, LinkedList<Integer>> graph = new HashMap<Integer, LinkedList<Integer>>();
public TestTarjan(String path) {
try {
BufferedReader br = new BufferedReader(new FileReader(path));
String[] strArray;
String str;
while ((str = br.readLine()) != null) {
strArray = str.split("\\s");
int a = Integer.parseInt(strArray[0]);
int b = Integer.parseInt(strArray[1]);
if (graph.containsKey(a)) {
graph.get(a).add(b);
} else {
LinkedList<Integer> linkedlist = new LinkedList<Integer>();
linkedlist.add(b);
graph.put(a, linkedlist);
}
}
br.close();
} catch (IOException e) {
e.printStackTrace();
}
}

public List<List<Integer>> getResult(){
TarjanSCC<Integer> tarjanScc = new TarjanSCC<Integer>(graph);
return tarjanScc.tarjan();
}
public static void main(String[] args) {
TestTarjan testTarjan = new TestTarjan("c:/tarjan.txt");
System.out.println(testTarjan.getResult());
}
}

这里再赋上一组简单的测试数据：

1 2
2 3
3 1
4 2
3 4
3 5
5 6
6 7
7 5
7 8
8 9
9 10
10 8