tarjangraphsc.java

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

package twf.graph.directed;

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

public class TarjanGraphSC implements GraphSC{
    private Graph G;
    private int cnt, scnt;
    private int[] pre, id, low;
    private IntStack S;
    private void scR(int w) {
    	int t, min = pre[w] = low[w] = cnt++;
    	S.push(w);
    	AdjList A = G.getAdjList(w);
    	for (t = A.beg(); !A.end(); t = A.nxt()) {
    		if (pre[t] == -1) {
    			scR(t);
    		}
    		if (low[t] < min) min = low[t];
    	}
    	if (min < low[w]) {low[w] = min; return;}
    	do {
    		id[t = S.pop()] = scnt;
    		low[t] = G.V();
    	} while (t != w);
    	scnt++;
    }
    public TarjanGraphSC(Graph G) {    	
    	this.G = G;
    	S = new IntStack(G.V());
    	pre = new int[G.V()];
    	id  = new int[G.V()];
    	low = new int[G.V()];
    	for (int v = 0; v < G.V(); v++) {
    		pre[v] = -1;
    	}
    	for (int v = 0; v < G.V(); v++) {
    		if (pre[v] == -1) {
    			scR(v);
    		}
    	}
    }
    public int count() {
    	return scnt;
    }
    public int id(int v) {
    	return id[v];
    }
    public boolean stronglyreachable(int v, int w) {
    	return id[v] == id[w];
    }
}