biconnected_components.java

Java实现的双连通分支算法

import java.io.*;
import java.util.*;

public class Biconnected_Components {
	public static int DFS_N;
	public static Vertex[] V; //顶点邻接表首节点
	public static int component=0; //双连通分支数量
	public static Stack<Integer> sta = new Stack<Integer>();
	public static LinkedList<Bi_Component> bl = new LinkedList<Bi_Component>();
	
	/**
	 * I/O Input Function
	 */
	public static void Input() throws Exception {
		File f = new File("data3.dat");	/*获取文件输入*/
		FileReader fis = new FileReader(f);
		BufferedReader dis = new BufferedReader(fis);
		
		String s = dis.readLine();
		DFS_N = Integer.parseInt(s);
		V = new Vertex[DFS_N];
		for (int i=0;i<DFS_N;i++) V[i] = new Vertex();
		
		/*获取图中的边*/
		int comma, v1, v2;
		s = dis.readLine();
		while(s!= null) { 
			comma = s.indexOf(",");
			v1 = Integer.parseInt(s.substring(1, comma));
			v2 = Integer.parseInt(s.substring(comma+1, s.length()-1));
			V[v1].Edge.add(v2);
			V[v2].Edge.add(v1);
			s = dis.readLine();
		}
		
		dis.close();
		fis.close();
	}
	
	/**
	 * DFS Tree Function
	 */
	public static void DFS_Tree(int v) {
		V[v].mark = true;
		int w;
		Iterator<Integer> l = V[v].Edge.iterator();
		while(l.hasNext()) {
			w = l.next();
			if(!V[w].mark) {
				V[w].parent = v;
				DFS_Tree(w);
			}
		}
	}
	
	/**
	 * 取最大数函数
	 **/
	public static int Max (int a, int b){
		if(a>b) return a;
		else return b;
	}
	
	/**
	 * 双连通按节点数排序函数
	 */
	public static void BC_Sort(Bi_Component b) {
		ListIterator<Bi_Component> sort = bl.listIterator();
		while(sort.hasNext()) {
			if(sort.next().node_num>b.node_num) {
				sort.previous();
				sort.add(b);
				break;
			}
		}
		if(!sort.hasNext()) sort.add(b);
	}
	
	/**
	 * Biconnected Components Function
	 */
	public static void BC(int v) {
		V[v].DFS_Num = DFS_N;
		DFS_N = DFS_N - 1;
		sta.push(v);
		V[v].High = V[v].DFS_Num; //初始值
		Iterator<Integer> l = V[v].Edge.iterator();
		while(l.hasNext()) { //对各条边开始访问
			int w = l.next();
			if(V[v].parent!=w) {
				if(V[w].DFS_Num==0) {
					BC(w);
					if (V[w].High<=V[v].DFS_Num) { //找到双连通分支
						component++;
						Bi_Component bc = new Bi_Component(); //记录该双连通分支用的类
						int node = 1; //双连通分支中的节点数
						int i = sta.pop();
						while(i!=v) {
							node++;
							bc.member = ", " + i + bc.member;
							i = sta.pop();
						}
						bc.member = "(" + v + bc.member;
						bc.node_num = node;
						BC_Sort(bc);
						sta.push(v);
					}
					V[v].High = Max(V[v].High, V[w].High);
				}
				else //(v,w)是一条后退边或一条前向边
					V[v].High = Max(V[v].High, V[w].DFS_Num);
			}
		}
	}
	
	/**
	 * Main Function
	 */
	public static void main(String[] args) throws Exception {
		Input(); //文件输入
		DFS_Tree(0);
		BC(0); //从根节点寻找双连通分支
		
		/*结果写入文件*/
		File f = new File("result3.dat");
		if(f.exists()) f.delete();
		FileWriter fw = new FileWriter(f);
		BufferedWriter bw = new BufferedWriter(fw);
		
		bw.write(Integer.toString(component));
		bw.newLine();
		ListIterator<Bi_Component> l = bl.listIterator();
		while(l.hasNext()) {
			bw.write(l.next().member);
			bw.newLine();
		}
		bw.flush();
		bw.close();
		fw.close();
		System.out.println("Finish");
	}

}