bicongraph.java

输入为一个无向图

package ex2_biconnected_components;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class BiconGraph {
	static int number;
	static int DFS_N;
	static Vertice[] V;
	static Stack<Integer> stack = new Stack<Integer>();
	static int codenum = 0;
	static ArrayList<Integer> code = new ArrayList<Integer>();
	static ArrayList<ArrayList<Integer>> branch = new ArrayList<ArrayList<Integer>>();
	static int count = 0;


	public static void sort(ArrayList<Integer> A) {
		for (int j = 0; j < A.size() - 1; j++) {
			for (int i = 0; i < A.size() - j - 1; i++)
				if (A.get(i) > A.get(i + 1)) {
					int tem;
					tem = A.get(i);
					A.remove(i);
					A.add(i, A.get(i));
					A.remove(i + 1);
					A.add(i + 1, tem);
				}

		}

	}

	public void getBranch(ArrayList<ArrayList<Integer>> f) {
		for (int i = 0; i < f.size(); i++) {

			int count = 0;
			for (int m = 0; m < code.size(); m++) {
				if (f.get(i).contains(code.get(m)))
					count++;

			}
			f.get(i).add(0, count);

		}
		for (int j = 0; j < branch.size() - 1; j++) {
			for (int i = 0; i < branch.size() - j - 1; i++)
				if (branch.get(i).get(0) > branch.get(i + 1).get(0)) {
					ArrayList<Integer> tem;
					tem = branch.get(i);
					branch.remove(i);
					branch.add(i, branch.get(i));
					branch.remove(i + 1);
					branch.add(i + 1, tem);
				}

		}

		for (int i = 0; i < f.size(); i++)
			f.get(i).remove(0);

	}

	public void BC(Vertice v) {

		v.DFSnumber = DFS_N;
		DFS_N--;
		stack.push(v.id);
		v.High = v.DFSnumber;
		for (int i = 0; i < v.edge.size(); i++) {
			Vertice w = V[v.edge.get(i)];
			int isprarent = 0;
			for (int n = 0; n < v.DFSedge.size(); n++) {
				if (v.DFSedge.get(n) == w.id) {
					if (w.DFSnumber > v.DFSnumber)
						isprarent = 1;
				}
			}
			if (isprarent == 0) {
				if (w.DFSnumber == 0) {
					BC(w);
					if (w.High <= v.DFSnumber) {
						codenum++;
						code.add(v.id);
						ArrayList<Integer> A = new ArrayList<Integer>();
						int pop;
						String s = "";
						do {
							pop = stack.pop();
							A.add(pop);
						} while (pop != v.id);
						stack.push(pop);

						sort(A);

						A.trimToSize();
						branch.add(A);

						for (int m = 0; m < A.size(); m++)
							s = s + " " + A.get(m);

					}

					v.High = Math.max(v.High, w.High);

				}

				else
					v.High = Math.max(v.High, w.DFSnumber);

			}
		
		}

	}

	public void DFStree(Vertice v) {
		v.DFSnumber = 1;
		for (int i = 0; i < v.edge.size(); i++) {
			Vertice w = V[v.edge.get(i)];
			if (w.DFSnumber == 0) {
				v.DFSedge.add(w.id);
				w.DFSedge.add(v.id);
				DFStree(w);

			}

		}
	}

	

	public void readFile(String filename) throws Exception {
		FileInputStream fis = new FileInputStream(filename);
		InputStreamReader isr = new InputStreamReader(fis);
		BufferedReader br = new BufferedReader(isr);
		String s;

		number = Integer.parseInt(br.readLine());

		V = new Vertice[number];
		for (int i = 0; i < number; i++) {
			V[i] = new Vertice();
		}

		while ((s = br.readLine()) != null) {

			s = s.substring(1, s.length() - 1);

			String[] a = new String[2];
			a = s.split(",");

			int x = Integer.parseInt(a[0]);
			int y = Integer.parseInt(a[1]);

			V[x].edge.add(y);
			V[y].edge.add(x);

		}
		for (int i = 0; i < number; i++) {
			V[i].edge.trimToSize();
		}

		br.close();

	}

	public void writefile(String filename) throws Exception {
		FileOutputStream fos = new FileOutputStream(filename);
		OutputStreamWriter osw = new OutputStreamWriter(fos);
		BufferedWriter bw = new BufferedWriter(osw);
		bw.write(count + "\r\n");
		for (int j = 0; j < branch.size(); j++) {
			String s = "";
			for (int m = 0; m < branch.get(j).size(); m++)
				s = s + branch.get(j).get(m) + ",";
			s = s.substring(0, s.length() - 1);
			bw.write("(" + s + ")");
			bw.newLine();
		}

		bw.close();

	}
	
	
	public void process(String fileName)throws Exception{
		readFile(fileName);
		System.out.println("DFS树的邻接链表：");
		for (int i = 0; i < number; i++) {
			V[i].DFSnumber = 0;
			V[i].id = i;
		}
		DFStree(V[0]);

		for (int i = 0; i < number; i++) {
			String s = "顶点序号" + "(" + i + ")" + ":";
			for (int j = 0; j < V[i].DFSedge.size(); j++)
				s = s + V[i].DFSedge.get(j) + " ";
			System.out.println(s);
			V[i].DFSnumber = 0;

		}

		for (int i = 0; i < number; i++) {
			V[i].DFSnumber = 0;

		}
		DFS_N = number;


		System.out.println("双连通分支：");

		BC(V[0]);
		getBranch(branch);
		for (int j = 0; j < branch.size(); j++) {
			String s = "";
			for (int m = 0; m < branch.get(j).size(); m++)
				s = s + " " + branch.get(j).get(m);
			System.out.println(s);
			count++;
		}
		
	}
	
	
	public static void main(String[] args) throws Exception {
		BiconGraph bc=new BiconGraph();
		bc.process("data_ex2_bc\\data3.txt");
		bc.writefile("data_ex2_bc\\result3.txt");
	}
	
	
	

}