用鄰接表實作無向圖

<pre name="code" class="java"><span style="font-size:18px;">import java.util.LinkedList;

/**
 * 用鄰接表(其實就是前面部落格實作的哈希表)實作無向圖
 * @author xxxu
 *
 */
public class Graph {
	private final int V;//頂點數目
	private int E;    //邊的數目
	private LinkedList<Integer>[] adj; //鄰接表(其實就是前面部落格實作的哈希表)
	/**
	 * 根據頂點初始化圖
	 * @param V
	 */
	public Graph(int V){ 
		this.V=V;
		this.E=0;
		adj=new LinkedList[V]; //有多少頂點就建立多大的數組鄰接表
		for(int v=0;v<V;v++){ //初始化所有連結清單為空
			adj[v]=new LinkedList();
		}
	}
	/**
	 * 傳回頂點數目
	 * @return
	 */
	public int V(){
		return V;
	}
	/**
	 * 傳回邊的數目
	 * @return
	 */
	public int E(){
		return E;
	}
	
	public void addEdge(int v,int w){
		adj[v].add(w);  //将w添加到v的連結清單中
		adj[w].add(v);  //将v添加到w的連結清單中
		E++;
	}
	
	public LinkedList<Integer> adj(int v){
		return adj[v];
	}
	/**
	 * 計算v的度數（多少條邊連接配接這個頂點）
	 * @return
	 */
	public int degree(Graph G,int v){
		int deg=0;
		for (int w:adj(v)) {
			deg++;//也就是多少個頂點就多少條邊
		}
		return deg;
	}
	/**
	 * 傳回所有頂點中的最大度數
	 * @param G
	 * @return
	 */
	public int maxDegree(Graph G){
		int max=0;
		for (int v = 0; v < V(); v++) {
			if(degree(G, v)>max){
				max=degree(G, v);
			}
		}
		return max;
	}
	/**
	 * 計算所有頂點的平均度數(一條邊連接配接兩個頂點)
	 * @param G
	 * @return
	 */
	public double avgDegree(Graph G){
		return 2.0*E()/V();
	}
	/**
	 * 計算自環的個數
	 * @return
	 */
	public int numberOfSelfLoops(Graph G){
		int count=0;
		for (int v = 0; v < V(); v++) {
			for (int w : adj(v)) {  //每個頂點都和相鄰的頂點比一次，如果相等那麼就是自環
				if(v==w){
					count++;
				}
			}
		}
		return count/2;//每條邊都被記過兩次
	}
	/**
	 * 重寫toString方法
	 */
	@Override
	public String toString() {
		String s=V + " vertices, " + E + " edges\n";
		for (int v = 0; v < V; v++) {
			s+=v+": ";
			for(int w:adj(v)){
				s+=w+" ";
			}
			s+="\n";
		}
		return s;
	}
}</span>