kosarajugraphsc.java

个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF遍历,

package twf.graph.directed;

import twf.adt.graph.AdjList;
import twf.adt.graph.Graph;

public class KosarajuGraphSC implements GraphSC{
	private int cnt, scnt;
	private int []id, postR, postI;
	private void dfsR(Graph G, int w) {
		id[w] = scnt;
		AdjList A = G.getAdjList(w);
		for (int v = A.beg(); !A.end(); v = A.nxt()) {
			if (id[v] == -1) {
				dfsR(G, v);
			}
		}
		postI[cnt++] = w;
	}
	public KosarajuGraphSC(Graph G) {
		Graph R = GraphUtilities.reverse(G);
		id = new int[G.V()];
		postR = new int[G.V()];
		postI = new int[G.V()];
		cnt = 0;
		for (int i = 0; i < G.V(); i ++) {
			id[i] = postI[i] = -1; 
		}
		for (int v = 0; v < G.V(); v++) {
			if (id[v] == -1) {
				dfsR(R, v);
			}
		}
		for (int v = 0; v < G.V(); v++) {
			postR[v] = postI[v];
		}
		cnt = 0; scnt = 0;
		for (int v = 0; v < G.V(); v++) {
			id[v] = postI[v] = -1;
		}
		for (int v = G.V() - 1; v >= 0; v--) {
			if (id[postR[v]] == -1) {
				dfsR(G, postR[v]);
				scnt++;
			}
		}
	}
	public boolean stronglyreachable(int v, int w) {
		return id[v] == id[w];
	}
	public int count() {
		return scnt; 
	}
	public int id(int v) {
		return id[v];
	}
}