graph.java

来自「个人学习图算法时写的源码 包括最小生成树, 最大网络流, DSF遍历, BSF」· Java 代码 · 共 65 行

package twf.weightedgraph.adjmatrix;

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

public class Graph implements twf.weightedgraph.Graph{
	private int Vcnt, Ecnt;
    private boolean digraph;
    private Edge adj[][];
    public Graph(int V, boolean flag)
      {
        Vcnt = V; Ecnt = 0; digraph = flag;
        adj = new Edge[V][V];
      }
    public int V() { return Vcnt; }
    public int E() { return Ecnt; }
    public boolean directed() { return digraph; }
    public void insert(Edge e)
      { int v = e.v(), w = e.w();
        if (adj[v][w] == null) Ecnt++;
        adj[v][w] = e;
        if (!digraph) adj[w][v] = e;
      }
    public void remove(Edge e)
      { int v = e.v(), w = e.w();
        if (adj[v][w] == null) Ecnt--;
        adj[v][w] = null;
        if (!digraph) adj[w][v] = null;
      }
    public Edge edge(int v, int w)
      { return adj[v][w]; }	
	
	public AdjList getAdjList(int v) {
		// TODO Auto-generated method stub
		return new AdjArray(v);
	}	
	private class AdjArray implements AdjList {
		private int t, v;
		public AdjArray(int v) {
			this.v = v;
		}
		public Edge beg() {
			// TODO Auto-generated method stub
			t = -1;
			return nxt();
		}

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

		public Edge nxt() {
			// TODO Auto-generated method stub
			for (t++; t < V(); t++)
		          if (edge(v, t) != null)
		            return edge(v, t);
		    return null;

		}
		
	}

}