graph.java

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

package twf.weightedgraph.adjlist;

import twf.weightedgraph.AdjList;
import twf.weightedgraph.Edge;

public class Graph implements twf.weightedgraph.Graph{
    private int Vcnt, Ecnt;
    private boolean digraph;
    private class Node {
    	private Edge edge;
    	private Node next;
    	Node (Edge e, Node t) {
    		edge = e;
    		next = t;
    	}
    }
    private Node[] adj;
    public Graph (int count, boolean flag) {
    	Vcnt = count; Ecnt = 0;
    	digraph = flag;
    	adj = new Node[count];
    }
    public boolean directed() {
    	return digraph;
    }
    public int V() {
    	return Vcnt;
    }
    public int E() {
    	return Ecnt;
    }
    public void insert(Edge e) {
    	int v = e.v();
    	int w = e.w();
    	adj[v] = new Node(e, adj[v]);
    	if (!digraph) {
    		adj[w] = new Node(e, adj[w]);
    	}
    	Ecnt++;
    }
    public void remove(Edge e) {
    	int v = e.v();
    	int w = e.w();
    	if (v < 0 || v > V() || w < 0 || w > V()) return;
    	Node p = adj[v];
    	for (Node t = adj[v]; t != null; p = t, t = t.next) {
    		if (t.edge.w() == w) {
    			if (t == p) {
    				adj[v] = adj[v].next;
    				break;
    			}
    			p.next = t.next;
    			break;
    		}
    	}
    	if (!digraph) {
    		p = adj[w];
    		for (Node t = adj[w]; t != null; p = t, t = t.next) {
    			if (t == p) {
    				adj[w] = adj[v].next;
    				break;
    			}
    			p.next = t.next;
    			break;
    		}
    	}
    	Ecnt--;
    }
    public Edge edge(int v, int w) {    	
    	if (v < 0 || v > V() || w < 0 || w > V()) return null;
    	for (Node t = adj[v]; t != null; t = t.next) {
    		if (t.edge.w() == w) {    			
    			return t.edge;
    		}
    	}
    	return null;
    }
    public AdjList getAdjList(int v) {
    	return new AdjLinkedList(v);
    }
    private class AdjLinkedList implements AdjList {
    	private Node v, t;
    	public AdjLinkedList(int v) {
    		this.v = adj[v];
    	}
		public Edge beg() {
			t = v;
			return t == null ? null : t.edge;
		}

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

		public Edge nxt() {
			// TODO Auto-generated method stub
			if (t == null)
			    return null; 
			else t = t.next;
			return t == null ? null : t.edge;
		}
    	
    }
}