scc.java

Java实现的图的强连通分支算法

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

public class SCC {    // 测试运行类
	private LinkedList<Edge> eg = new LinkedList<Edge>();
	private static LinkedList<Component> com = new LinkedList<Component>();
	private Stack<Vertex> s = new Stack<Vertex>();
	private static Vertex[] v;
	private int n;
	private static int ccomponent;
	private int DFS_N;
	private void read() {    // 读取文件内容
		try {
			FileReader freader = new FileReader("data4.dat");
			BufferedReader breader = new BufferedReader(freader);
			n = Integer.parseInt(breader.readLine());
			v = new Vertex[n];
			for(int t = 0; t < n; t++) {
				Vertex y = new Vertex(t);
				v[t] = y;
			}
			String res = breader.readLine();
			while(res != null) {
				int i = 1;
				while(res.charAt(i) != ',') i++;
				Edge e = new Edge();
				e.setstart(v[Integer.parseInt(res.substring(1, i))]);
				e.setend(v[Integer.parseInt(res.substring(i+1, res.length()-1))]);
				eg.add(e);
				res = breader.readLine();
			}
			breader.close();
			freader.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	private void run() {    // 运行函数
		for(int i = 0; i < n; i++) {
			v[i].setnum(0);
			v[i].setcom(0);
		}
		ccomponent = 0;
		DFS_N = n;
		for(int j = 0; j < n; j++) {
			if(v[j].getnum() == 0) SC(v[j]);
		}
	}
	
	private void SC(Vertex v) {    // 构造强连通分量函数
		v.setnum(DFS_N);
		DFS_N = DFS_N - 1;
		s.push(v);
		v.sethigh(v.getnum());
		for(int h = 0; h < eg.size(); h++) {
			if(eg.get(h).getstart() == v) {
				Vertex w = eg.get(h).getend();
				if(w.getnum() == 0) {
					SC(w);
					if(v.gethigh() >= w.gethigh()) v.sethigh(v.gethigh());
					else v.sethigh(w.gethigh());
				} else {
					if(w.getnum() > v.getnum() && w.getcom() == 0) {
						if(v.gethigh() >= w.getnum()) v.sethigh(v.gethigh());
						else v.sethigh(w.getnum());
					}
				}
			}
		}
		if(v.gethigh() == v.getnum()) {
			ccomponent = ccomponent + 1;
			Component newcom = new Component();
			Vertex x;
			while(true) {
				x = s.pop();
				x.setcom(ccomponent);
				newcom.add(x.getid());
				if(x == v) break;
			}
			com.add(newcom);
		}
	}
	
	public static void BubbleSort(LinkedList<Component> R) {    // 冒泡排序函数
		int i,j;
		Boolean exchange;
		for(i = 0; i < R.size() - 1; i++){
			exchange = false;
			for(j = R.size() - 2; j >= i; j--)
				if(R.get(j+1).getsize() < R.get(j).getsize()) {
					Component temp = new Component();
					temp = R.get(j+1);
					R.set(j+1, R.get(j));
					R.set(j, temp);
					exchange = true;
				}
			if(!exchange)
				return;
		}  
	}
	
	public static void main(String[] args) {    // 主函数
		SCC s = new SCC();
		String answer = null;
		s.read();
		s.run();
		try {
			FileWriter fwriter = new FileWriter("result4.dat");
			BufferedWriter bwriter = new BufferedWriter(fwriter);
			String res = Integer.toString(ccomponent);
			bwriter.write(res);
			bwriter.newLine();
			bwriter.flush();
			BubbleSort(com);
			for(int i = 0; i < com.size(); i++) {
				answer = com.get(i).write();
				bwriter.write(answer);
				bwriter.newLine();
				bwriter.flush();
			}
			bwriter.close();
			fwriter.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}