Java 实现了一个分解强连通分量算法及其中遇到的两个问题

起因是帮兄弟的忙,需要完成一个强连通分量算法。好久没写过这东西了,而且当年玩儿 ACM 时用的还是 C++,现在由于各方面原因需要使用 Java。在这个过程中,遇到了两个问题:无法创建泛型数组 和 递归太深导致栈溢出,再此记录下来。

强连通分量

首先说一下强连通分量的定义:

在一个有向图中,对于它的某个子集 S,如果在 S 内任取两个顶点 u 和 v,都能找到一条从 u 到 v 的路径,那么就说 S 是强连通的。如果在 S 中加入任意其他点集合,它都不在是强连通的,那么就说 S 是原图的一个强连通分量。

一个简单的算法就是两次 dfs,具体证明以后另开文章介绍,直接贴最终代码:

class Scc {
    HashMap<Integer, ArrayList<Integer>> G, rG;
    Stack<Integer> vs;
    HashSet<Integer> used, nodes;
    
    Scc() {
        nodes = new HashSet<Integer>();
        G = new HashMap<Integer, ArrayList<Integer>>();
        rG = new HashMap<Integer, ArrayList<Integer>>();
    }
    
    void addEdge(int from, int to) {
        if (G.get(from) == null)
            G.put(from, new ArrayList<Integer>());
        if (rG.get(to) == null)
            rG.put(to, new ArrayList<Integer>());
        
        G.get(from).add(to);
        rG.get(to).add(from);
        
        nodes.add(from);
        nodes.add(to);
    }
    
    void dfs(int u) {
        used.add(u);
        ArrayList<Integer> next = G.get(u);
        if (next != null) {
            for (int i = 0; i < next.size(); i++) {
                int v = next.get(i);
                if (!used.contains(v)) {
                    dfs(v);
                }
            }
        }
        vs.push(u);
    }
    
    void rdfs(int u) {
        used.add(u);
        ArrayList<Integer> next = rG.get(u);
        if (next != null) {
            for (int i = 0; i < next.size(); i++) {
                int v = next.get(i);
                if (!used.contains(v)) {
                    rdfs(v);
                }
            }
        }
    }
    
    int solve() {
        used = new HashSet<Integer>();
        vs = new Stack<Integer>();
        
        for (int u: nodes) {
            if (!used.contains(u))
                dfs(u);
        }
        
        used.clear();
        int k = 0;
        
        while (!vs.empty()) {
            int u = vs.pop();
            if (!used.contains(u)) {
                rdfs(u); k++;
            }
        }
        
        return k;
    }
}

无法创建泛型数组

首先在写这份代码的过程中就遇到一个问题,在 C++ 中,为了方便的实现一个邻接表,通常可以直接使用 vector:

vector<int> G[maxv];

然后添加一条边从 u 到 v 的有向边时,只需要这样:

G[u].push_back(v);

简单粗暴,不需要手写一个邻接表结构,而且效率上表现的也不错,关于邻接表的细节打算后面再写一篇文章介绍。

看了上面的代码,转用 Java 写时,很自然的写出下面的代码:

ArrayList<Integer>[] G = new ArrayList<Integer>[maxv];

然后直接收到了一个错误:Cannot create a generic array of ArrayList<Integer>

表示不解,于是翻阅资料后在 stackoverflow 上找到了这份解答:
https://stackoverflow.com/questions/4549192/create-an-array-of-arrayliststring-elements

所以,你没办法创建一个泛型数组,不过文章中介绍了几种解决方案:

  1. 使用 ArrayList<ArrayList<String>>
  2. 去掉泛型,改为:ArrayList<Integer>[] G = new ArrayList[maxv];
  3. 如果你一定要创建一个泛型数组的话,可以这样做:
public class StringArrayList extends ArrayList<String>{}

ArrayList<String> name[] = new StringArrayList[9];

而我在上面的代码中使用了 HashMap,刚好也符合邻接表的实现:

HashMap<Integer, ArrayList<Integer>> G = new HashMap<Integer, ArrayList<Integer>>();

递归太深导致爆栈

终于代码编译通过了,跑了几组数据也没问题,然而突然在某一组数据中爆炸:Exception in thread "main" java.lang.StackOverflowError

哈?第一反应是递归写矬了?后来仔细检查后认为递归没有问题,那就只有一个可能,是真的爆栈了,那么显然是 JVM 的递归栈太小了,如何调整栈的参数呢?

查找资料后有如下结论,只需要调整一下 -Xss 参数就可以了:

JDK5.0 以后每个线程堆栈大小为 1M,以前每个线程堆栈大小为 256K。在相同物理内存下,减小这个值能生成更多的线程。来自这篇文章:JVM系列三:JVM参数设置、分析

调整参数后在尝试一下:

java -Xss2M Main

这次终于可以正常运行了。

标签: java, 强连通

添加新评论