graph.java

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

package twf.graph.adjlist;

import twf.adt.graph.AdjList;
import twf.adt.graph.Edge;
/**
 * 
 * @author Administrator
 * @version 1.0
 * 
 */
public class Graph implements twf.adt.graph.Graph{
	public static final int DEFAULT_WEIGHT = 1;
	private int Vctn, Ectn;
	private boolean digraph;
	private Node[] adj;
	public Graph (int Vctn, boolean digraph) {
		this.Vctn = Vctn;
		this.digraph = digraph;
		adj = new Node[Vctn];
	}
	/**
	 * Vertices
	 * @return the number of vertices of this graph
	 */
	public int V() {
		return Vctn;
	}
	/**
	 * Edges
	 * @return the number of edges of this graph
	 */
	public int E() {
		return Ectn;
	}
	/**
	 * Is this graph digraph?
	 * @return true if this is a digraph
	 */
	public boolean directed() {
		return digraph;
	}
	/**
	 * Is vertice v and w connected ?
	 * @param v 
	 * @param w
	 * @return true if the two vertices are connnected.
	 */
	public boolean edge(int v, int w) {
		for (Node t = adj[v]; t != null; t = t.next) {
			if (t.v == w) {
				return true;
			}
		}
		return false;
	}
	/**
	 * Insert a new Edge
	 * @param e edge to be inserted
	 */
	public void insert(Edge e) {
		int v  = e.v();
		int w = e.w();
		int weight = e.weight();
		adj[v] = new Node(w, adj[v], weight);
		if (!digraph) {
			adj[w] = new Node(v, adj[w], weight);
		}
		Ectn++;
	}
	/**
	 * Change the weight of a edge specified.
	 * @param v
	 * @param w
	 * @param weight
	 */
	public void change(int v, int w, int weight) {
		for (Node t = adj[v]; t != null; t = t.next) {
			if (t.v == w) {
				t.weight = weight;
				break;
			}
		}
		if (!digraph) {
			for (Node t = adj[w]; t != null; t = t.next) {
				if (t.v == v) {
					t.weight = weight;
					break;
				}
			}
		}
	}
	/**
	 * Remove edge between two vertices.
	 * @param v
	 * @param w
	 */
	public void remove(int v, int w) {
		Node p = adj[v];
		for (Node t = adj[v]; t != null; p = t,t = t.next) {
			if (t.v == w) {
			   if (p == t) {
				   adj[v] = t.next;				  
			   } else {
				   p.next = t.next;
			   }
			   break;
			}
		}
		if (!digraph) {
			p = adj[w];
			for (Node t = adj[w]; t != null; p = t, t = t.next) {
				if (t.v == v) {
					   if (p == t) {
						   adj[w] = t.next;
					   } else {
						   p.next = t.next;
					   }
					   break;
				}
			}
		}
		Ectn--;	
	}
	/**
	 * Get the adjacency list of a vertice.
	 * @param v
	 * @return
	 */
	public AdjList getAdjList(int v) {
		return new AdjLinkedList(v);
	}
	private class Node {
		int v;
		int weight;
		Node next;
		Node(int v, Node t, int weight) {
			this.v = v;
			next = t;
			this.weight = weight;
		}
	}
	private class AdjLinkedList implements AdjList {
		private int v; 
		private Node t;
		AdjLinkedList (int v) {
			this.v = v;
			t = null;
		}
		public int beg() {
			// TODO Auto-generated method stub
			t = adj[v];
			return t == null ? -1 : t.v;
		}

		public boolean end() {
			// TODO Auto-generated method stub
			return t == null;
		}

		public int nxt() {
			// TODO Auto-generated method stub
			if (t != null) {
				t = t.next;
			}
			return t == null ? -1 : t.v;
		}

		public int weight() {
			// TODO Auto-generated method stub
			return t == null ? 0 : t.weight;
		}
		
	}
}