graph.java

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

package twf.graph.adjmatrix;

import twf.adt.graph.AdjList;
import twf.adt.graph.Edge;
/**
 * 
 * @author Administrator
 * @version 1.0
 * @see twf.adjlist.Network
 */
public class Graph implements twf.adt.graph.Graph{
	private int Vctn;
	private int Ectn;
	private boolean digraph;
	private int adj[][];
	public Graph(int v, boolean flag) {
		Vctn = v;
		digraph = flag;
		adj = new int[v][v];
	}
	public int V() {
		return Vctn;
	}
	public int E() {
		return Ectn;
	}
	public boolean directed() {
		return digraph;
	}
	public boolean edge(int v,int w) {
		return adj[v][w] > 0;
	}
	public void insert(Edge e) {
		adj[e.v()][e.w()] = e.weight();
		if (!digraph) {
			adj[e.w()][e.v()] = e.weight();
		}
	}
	public void change(int v, int w, int weight) {
		adj[v][w] = weight;
		if (!digraph) {
			adj[w][v] = weight;
		}
	}
	public void remove(int v, int w) {
		adj[v][w] = 0;
		if (!digraph) {
			adj[w][v] = 0;
		}
	}
	public AdjList getAdjList(int v) {
		return new AdjArray(v);
	}
	private class AdjArray implements AdjList {
		private int i , v ;
		public AdjArray(int v) {
			this.v  = v;
			i = -1;
		}
		public int beg() {
			// TODO Auto-generated method stub
			i = -1;
			return nxt();
		}

		public boolean end() {
			// TODO Auto-generated method stub
			return i >= V();
		}

		public int nxt() {
			// TODO Auto-generated method stub
			for (i++; i < V(); i++) {
				if (edge(v, i)) {
					return i;
				}
			}
			return -1;
		}

		public int weight() {
			// TODO Auto-generated method stub
			if (i > -1 && i < V()) {
				return adj[v][i];
			}
			return 0;
		}	
		
	}
}