graphcycle.java

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

package twf.weightedgraph.undirected;

import twf.weightedgraph.AdjList;
import twf.weightedgraph.Edge;
import twf.weightedgraph.Graph;
import twf.weightedgraph.Path;

public class GraphCycle {
	private Graph G;
	private int cnt, st, ed;
	private int[] pre;
	private boolean hasCycle;
	private Path cycle;
	private void cycleR(int w, int v) {
		pre[v] = cnt++;
		AdjList A = G.getAdjList(v);
		for (Edge e = A.beg(); !A.end(); e = A.nxt()) {
			if (hasCycle) return;
			if (pre[e.w()] == -1) {
				cycleR(v, e.w());
			} else if (e.w() != w && pre[v] > pre[e.w()]) {//back edge
				st = e.w();
				ed = v;
				hasCycle = true;
				System.out.println("st " + st + " ed " + ed);
				return;
			}			
		}
	}
	private void findCycle() {
		for (int i = 0; i < G.V(); i++) {
			pre[i] = -1;
		}		
		cnt = 0;
		pre[st] = cnt++;
		AdjList A = G.getAdjList(st);
		for (Edge e = A.beg(); !A.end(); e = A.nxt()) {
			if (e.w() == ed) {
				continue;
			}
			Path p = null;
			if ((p = path(e.w())) != null) {
				p = new Path(new Edge(st, e.w(), 1), p);				
				cycle = p;
				return;
			}
		}
	}
	private Path path(int m) {
		pre[m] = cnt++;
		if (m == ed) {
			return new Path(new Edge(ed, st, 1), null);
		}		
		AdjList A = G.getAdjList(m);
		for (Edge e = A.beg(); !A.end(); e = A.nxt()) {
			Path p = null;
			if (pre[e.w()] == -1 && ((p = path(e.w())) != null)) {
				return new Path(new Edge(m, e.w(), 1), p);
			}
		}
		return null;
	}
	public GraphCycle(Graph G) {
		this.G = G;
		hasCycle = false;
		pre = new int[G.V()];
		for (int v = 0; v < G.V(); v++) pre[v] = -1;
		for (int v = 0; v < G.V(); v ++) {
			if (!hasCycle && pre[v] == -1) {
				cycleR(v, v);
			} else if (hasCycle) {
				findCycle();
				break;
			}
		}
	}
	public boolean hasCycle() {
		return hasCycle;
	}
	public Path cycle() {
		return cycle;
	}
}