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
所以,你没办法创建一个泛型数组,不过文章中介绍了几种解决方案:
- 使用
ArrayList<ArrayList<String>>
- 去掉泛型,改为:
ArrayList<Integer>[] G = new ArrayList[maxv];
- 如果你一定要创建一个泛型数组的话,可以这样做:
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
这次终于可以正常运行了。
levitra 5mg cost register - cheaapest levitra - levitra 10 mg effectiveness replies
alternativen fur viagra viagra - viagra cheap - levitra vs viagra review messageboard.html