Javaでグラフの連結成分を求める
Pythonで書いた
findConnectedComponentsの連結成分を求めている部分をJavaに移植したもの。ほぼ同じですね。誰の言葉か忘れたのだけどもJava1.5はLLのようです。
Python版と一番大きく異なるのは型の情報があることで、たとえばPython版では僕の頭の中にしか「componentsは頂点のリストのリスト」という情報がなかったのが、Java版では「Vector<Vector<IVertex>> components」と明記されています。とすると、Java版の方がアルゴリズムの理解のしやすさは上なのかも知れないですね…。むむむ。Pythonでアルゴリズムを書くときもコメントか何かで型を書いておいた方がいいのかなぁ？
// 隣接リストを作る
Hashtable<IVertex, Vector> adjDict = new Hashtable();
for(IVertex v: vertexDict.values()){
adjDict.put(v, new Vector());
}
for(IEdge e: edgeDict.values()){
IVertex v1 = e.getV1();
IVertex v2 = e.getV2();
adjDict.get(v1).add(v2);
adjDict.get(v2).add(v1);
}
// 連結成分を求める
Vector<IVertex> visited = new Vector();
Vector<Vector<IVertex>> components = new Vector();
for(IVertex v: vertexDict.values()){
if(visited.contains(v)){
continue;
}
Vector<IVertex> aComp = new Vector();
Vector<IVertex> queue = new Vector();
queue.add(v);
while(queue.size() > 0){
Vector<IVertex> newQueue = new Vector();
for(IVertex current: queue){
visited.add(current);
aComp.add(current);
Vector<IVertex> neighbors = adjDict.get(current);
for(IVertex neighbor: neighbors){
if(!visited.contains(neighbor) && !newQueue.contains(neighbor)){
newQueue.add(neighbor);
}
}
}
queue = newQueue;
}
components.add(aComp);
}
