daggenerator.java

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

package twf.graph.directed;

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

public class DagGenerator {
	private Graph G;
	private int[]pre, post;
	private int cnt, bcnt;
	private void dagR(Edge e) {
		int v = e.v();
		int w = e.w();
		pre[w] = cnt++;
		AdjList A = G.getAdjList(w);
		for (int t = A.beg(); !A.end(); t = A.nxt()) {
			if (pre[t] == -1) {
				dagR(new Edge(v, t));
			} else if(post[t] == -1) {
				G.remove(w, t);
			}
		}
		post[w] = bcnt++;
	}
	public DagGenerator(Graph G) {
		this.G = G;
		pre = new int[G.V()];
		post = new int[G.V()];
		for (int i = 0; i < G.V(); i ++) {
			pre[i] = post[i] = -1;
		}
		for (int i = 0; i < G.V(); i++) {
			if (pre[i] == -1) {
				dagR(new Edge(i, i));
			}
		}
	}
}