图-最大强连通子图-在线编程-K6K4.com

在有向图G中，如果两个顶点间至少存在一条路径，称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。给定有向图A的邻接矩阵表示，若顶点i,j之间有边则A[i][j]=1 , 否则A[i][j]=0，求最大强连通子图，返回该最大强连通子图的顶点，按顶点值由小到大排列。
约定：
（1）最大连通子图唯一

输入、输出描述

输入：

A：有向图的邻接矩阵表示，若顶点i,j之间有边则A[i][j]=1, 否则A[i][j]=0
n：顶点的个数，顶点编号为：0，1，2...n-1

输出：

最大强连通子图中的顶点构成的数组，按顶点值由小到大排列。

Example

输入：

A:
0,0,1,0,0
0,0,0,0,0
0,0,0,1,1
0,0,0,0,1
1,0,1,0,0

n:5

输出：

0,2,3,4

修改

使用Tarjan算法来搜索有向图中的所有强连通子图，然后取节点数最多的即为最大强连通子图。

Tarjan算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

定义DFN[u]来记录搜索到点u的时间，也就是第几个搜索u的。Low[u]为u或u的子树能够追溯到的最早的栈中节点的次序号。

算法伪代码如下：

tarjan(u)

{

DFN[u]=Low[u]=++Index // 为节点u设定次序编号和Low初值

Stack.push(u) // 将节点u压入栈中

for each (u, v) in E // 枚举每一条边

if (v is not visted) // 如果节点v未被访问过

tarjan(v) // 继续向下找

Low[u] = min(Low[u], Low[v])

else if (v in S) // 如果节点v还在栈内

Low[u] = min(Low[u], DFN[v])

if (DFN[u] == Low[u]) // 如果节点u是强连通分量的根

repeat

v = S.pop // 将v退栈，为该强连通分量中一个顶点

print v

until (u== v)

}

代码：

import java.util.*;

public class Main {
  private int numOfNode;
  private List< ArrayList<Integer> > graph;//图的List表示
  private List< ArrayList<Integer> > result;//保存所有强连通子图
  private boolean[] inStack;
  private Stack<Integer> stack;
  private int[] dfn;
  private int[] low;
  private int time;
  
  public int[] solution(int[][] A,int n) {
    graph = null;
    //根据邻接矩阵将图用List形式表示，List的每个元素记录该顶点的所有直接后驱节点
    List< ArrayList<Integer> > g = new ArrayList<ArrayList<Integer>>();
    for(int i=0;i<n;i++)
      g.add(new ArrayList<Integer>());
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (A[i][j] == 1)
          g.get(i).add(j);
      }
    }
    
    graph = g;
    numOfNode = n;
    inStack = new boolean[numOfNode];
    stack = new Stack<Integer>();
    dfn = new int[numOfNode];
    low = new int[numOfNode];
    Arrays.fill(dfn, -1);//将dfn所有元素都置为-1，其中dfn[i]=-1代表i还有没被访问过
    Arrays.fill(low, -1);
    
    result = new ArrayList<ArrayList<Integer>>();
    for(int i=0;i<numOfNode;i++){
      if(dfn[i]==-1)
        tarjan(i);
    }
    
    ArrayList<Integer> subTemp = new ArrayList<>();
    for (ArrayList<Integer> sub : result) {
      if (subTemp.size()<sub.size()) {
        subTemp = sub;
      }
    }
    int [] subArray = new int[subTemp.size()];
    int i = 0;
    for (int integer : subTemp)
      subArray[i++] = integer;
    
    Arrays.sort(subArray);//排序
    return subArray;
  }
  
  public void tarjan(int current){
    dfn[current]=low[current]=time++;
    inStack[current]=true;
    stack.push(current);
    for(int i=0;i<graph.get(current).size();i++){
      int next = graph.get(current).get(i);
      if(dfn[next]==-1){//-1代表没有被访问
        tarjan(next);
        low[current]=Math.min(low[current], low[next]);
      }else if(inStack[next]){
        low[current]=Math.min(low[current], dfn[next]);
      }
    }
    
    if(low[current]==dfn[current]){
      ArrayList<Integer> temp =new ArrayList<Integer>();
      int j = -1;
      while(current!=j){
        j = stack.pop();
        inStack[j]=false;
        temp.add(j);
      }
      result.add(temp);
    }
  }
  
}