graphdfs.java

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

package twf.graph.directed;

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

public class GraphDFS {
	private Graph G;
	private int[] pre, post;
	private int cnt, cntP, depth;
	private void show(String s, Edge e) {
		for (int i = 0; i < depth; i++) {
			System.out.print("  ");
		}
		System.out.println(e.v() + "-" + e.w() + " " + s);
	}
	private void dfsR(Edge e) {
		int w = e.w(); show("tree", e);
	      pre[w] = cnt++; depth++;
	      AdjList A = G.getAdjList(w);
	      for (int t = A.beg(); !A.end(); t = A.nxt())
	        { Edge x = new twf.graph.Edge(w, t);
	          if (pre[t] == -1) dfsR(x);
	          else if (post[t] == -1) show("back", x);
	          else if (pre[t] > pre[w]) show("down", x);
	          else show("cross", x);
	        }
	      post[w] = cntP++; depth--;
	}
	public GraphDFS(Graph G) {
		this.G = G; depth = 0; cnt = 0; cntP = 0;
	      pre = new int[G.V()]; post = new int[G.V()];
	      for (int t = 0; t < G.V(); t++)
	        { pre[t] = -1; post[t] = -1; }
	      for (int t = 0; t < G.V(); t++)
	        if (pre[t] == -1) dfsR(new twf.graph.Edge(t, t));
	}
}