assignment4.java

递归算法求一个有向图的强连通分量

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.lang.*;

class Vertex {
	private int dfsN;

	private int component;

	private int high;

	private boolean marked;

	private int father;

	Vertex() {
		dfsN = 0;
		component = 0;
		high = 0;
		father = 0;
		marked = false;
	}

	public boolean isMarked() {
		return marked;
	}

	public void setMarked() {
		marked = true;
	}

	public int getdfsN() {
		return dfsN;
	}

	public void setdfsN(int dfsN) {
		this.dfsN = dfsN;
	}

	public int getComponent() {
		return component;
	}

	public void setComponent(int component) {
		this.component = component;
	}

	public int getHigh() {
		return high;
	}

	public void setHigh(int high) {
		this.high = high;
	}

	public int getFather() {
		return father;
	}

	public void setFather(int father) {
		this.father = father;
	}

}

class Edge {
	private int start;

	private int end;

	private boolean isScanned;

	Edge(int start, int end) {
		this.start = start;
		this.end = end;
		isScanned = false;
	}

	public boolean isScanned() {
		return isScanned;
	}

	public void setScanned() {
		isScanned = true;
	}

	public int getStart() {
		return start;
	}

	public int getEnd() {
		return end;
	}

}

class Scc {
	private int nVertex;

	private int nEdge;

	private int adjMatrix[][];

	private Vertex[] vertex;

	private Edge[] edge;

	private int currentComponent;

	private int DFS_N;

	private Stack stack;

	private int w;

	private Stack scc;

	private Vector sccContainer;

	private Vector size;

	private int n;

	Scc(String filename) {
		initialize(filename);
	}
	/*读取文件data4.txt*/
	public void initialize(String filename) {
		try {
			StringBuffer sb = new StringBuffer();
			BufferedReader in = new BufferedReader(new FileReader(filename));
			String s = in.readLine();
			DFS_N = nVertex = Integer.parseInt(s);
			currentComponent = 0;
			n = w = 0;
			stack = new Stack();
			scc = new Stack();
			sccContainer = new Vector();
			size = new Vector();

			vertex = new Vertex[nVertex];
			adjMatrix = new int[nVertex][nVertex];
			Vector line = new Vector();

			for (int i = 0; i < nVertex; i++) {
				vertex[i] = new Vertex();
			}

			for (int i = 0; (s = in.readLine()) != null; i++) {
				filterInput(s.substring(1, s.length() - 1), line);
				nEdge = i + 1;
			}

			int[] tmp = new int[line.size()];
			vectorToInteger(line, tmp);
			edge = new Edge[nEdge];
			for (int i = 0; i < line.size(); i += 2) {
				adjMatrix[tmp[i]][tmp[i + 1]] = 1;
				edge[i / 2] = new Edge(tmp[i], tmp[i + 1]);
			}
			in.close();
		} catch (IOException e) {
			System.out.print("");
		}
	}

	public void scc() {
		for (int i = 0; i < nVertex; i++) {
			if (vertex[i].getdfsN() == 0) {
				scca(i);
			}
		}
		output();
	}

	public void scca(int v) {
		vertex[v].setdfsN(DFS_N);
		DFS_N--;
		stack.push(Integer.valueOf(v));
		vertex[v].setHigh(vertex[v].getdfsN());
		for (int i = 0; i < nEdge; i++) {
			if (edge[i].getStart() == v && (!edge[i].isScanned())) {
				if (vertex[edge[i].getEnd()].getdfsN() == 0) {
					scca(edge[i].getEnd());
					vertex[v].setHigh(java.lang.Math.max(vertex[v].getHigh(),
							vertex[edge[i].getEnd()].getHigh()));
				} else {
					if (vertex[edge[i].getEnd()].getdfsN() > vertex[v]
							.getdfsN()
							&& vertex[edge[i].getEnd()].getComponent() == 0) {
						vertex[v]
								.setHigh(java.lang.Math.max(
										vertex[v].getHigh(), vertex[edge[i]
												.getEnd()].getdfsN()));
					}
				}
			}
		}
		if (vertex[v].getHigh() == vertex[v].getdfsN()) {
			currentComponent++;
			int index;

			while (true) {
				index = Integer.parseInt(stack.pop().toString());
				scc.push(Integer.valueOf(index));
				vertex[index].setComponent(currentComponent);
				if (index == v)
					break;
			}
			Vector temp = new Vector();
			while (!scc.isEmpty()) {
				temp.addElement(scc.pop().toString());
				n++;
			}
			size.addElement(Integer.valueOf(v));
			n = 0;
			sccContainer.addElement(temp.toString());
		}
	}
	
	/*写为result4.txt*/
	private void output() {
		try {
			PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("result4.txt")));
			inssort();
			out.println("Scc number: "+ sccContainer.size());
			for (int i = 0; i < sccContainer.size(); i++) {
				String s = sccContainer.elementAt(i).toString();
				out.println("(" + s.substring(1, s.length() - 1) + ")");
			}
			out.close();
		} catch (IOException e) {
			System.out.print("");
		}
	}

	private void swap(int left, int right) {
		Vector temp = new Vector();
		Vector temp1 = new Vector();
		temp.addElement(size.elementAt(left));
		size.setElementAt(size.elementAt(right), left);
		size.setElementAt(temp.elementAt(0), right);
		temp1.addElement(sccContainer.elementAt(left));
		sccContainer.setElementAt(sccContainer.elementAt(right), left);
		sccContainer.setElementAt(temp1.elementAt(0), right);
	}

	public void inssort() {
		for (int i = 1; i < sccContainer.size(); i++) {
			for (int j = i; (j > 0)
					&& (Integer.parseInt(size.elementAt(j).toString()) > Integer
							.parseInt(size.elementAt(j - 1).toString())); j--) {
				swap(j - 1, j);
			}
		}
	}

	private void vectorToInteger(Vector line, int[] tmp) {
		for (int i = 0; i < line.size(); i++) {
			tmp[i] = Integer.parseInt(line.elementAt(i).toString());
		}
	}

	private void filterInput(String s, Vector line) {
		int start = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == ',') {
				line.add(s.substring(start, i));
				start = i + 1;
			}
			if (i == (s.length() - 1))
				line.add(s.substring(start, i + 1));
		}
	}

}

public class Assignment4 {
	public static void main(String[] args) {
		Scc test = new Scc("data4.txt");
		test.scc();
	}
}