dagts.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 43 行

package twf.graph.directed;

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

public class DagTS {
	private Graph G;
	private int []pre, post, postI;
	private int cnt, bcnt;
	public DagTS(Graph G) {
		this.G = G;
		pre = new int[G.V()];
		post = new int[G.V()];
		postI = new int[G.V()];
		for (int i = 0; i < G.V(); i++) {
			pre[i] = -1;
			post[i] = -1;
			postI[i] = -1;
		}
		for (int i = 0; i < G.V(); i++) {
			if (pre[i] == -1) {
				tsR(i);
			}
		}
	}
	private void tsR(int v) {
		pre[v] = cnt++;
		AdjList A = G.getAdjList(v);
		for (int t = A.beg(); !A.end(); t = A.nxt()) {
			if (pre[t] == -1) {
				tsR(t);
			}
		}
		post[v] = bcnt; postI[bcnt++] = v;
	}
	public int order(int v) {
		return postI[v];
	}
	public int relabel(int v) {
		return post[v];
	}
}