graphtc.java

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

package twf.graph.directed;

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

public class GraphTC {
	private Graph G;
	private DenseGraph T;
	private void tcR(Edge e) {
		T.insert(e);
		AdjList A = G.getAdjList(e.w());
		for (int i = A.beg(); !A.end(); i = A.nxt()) {
			if (!T.edge(e.v(), i)) {
				tcR(new Edge(e.v(), i));
			}
		}
	}
	public GraphTC(Graph G)
    { this.G = G; T = GraphUtilities.densecopy(G);
      	for (int v = 0; v < T.V(); v++) tcR(new Edge(v, v)); }
	public	boolean reachable(int v, int w)
    { return T.edge(v, w); }

}