dagtc.java

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

package twf.graph.directed;

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

public class DagTC {	
	private DenseGraph D;
	private int cnt;
	private int[] pre;
	  void tcR(int w)
	    {
	      pre[w] = cnt++;
	      AdjList A = D.getAdjList(w);
	      for (int t = A.beg(); !A.end(); t = A.nxt())
	      {
	        D.insert(new Edge(w, t));
	        if (pre[t] > pre[w]) continue;
	        if (pre[t] == -1) tcR(t);
	        for (int i = 0; i < D.V(); i++)
	         if (D.edge(t, i)) D.insert(new Edge(w, i));
	       }
	     }
	  public DagTC(Graph G)
	    { cnt = 0;
	      D = GraphUtilities.densecopy(G);
	      pre = new int[G.V()];
	      for (int v = 0; v < D.V(); v++) pre[v] = -1;
	      for (int v = 0; v < D.V(); v++)
	        if (pre[v] == -1) tcR(v);
	    }
	  public boolean reachable(int v, int w)
	    { return D.edge(v, w); }
 
}