圖（鄰接表）

圖（鄰接表）

/**
 * 文件名：Graph.java
 * 時間：2014年11月13日下午4:51:12
 * 作者：修維康
 */
package chapter9;

import java.util.*;

/**
 * 類名：Graph 說明：
 */
class Vertex {
	public AnyType value;
	public int indegree = 0;// 頂點的入度，拓撲排序的時候用到
	public LinkedList adjacent = new LinkedList();
	public int topNum = 0;// 拓撲排序
	private int size = 0;
	private int index = 0;
	public int dist = Integer.MAX_VALUE;// 到一個頂點的距離,開始默認都不可達
	public boolean visited = false;
	public Vertex path = null;
	public Vertex(AnyType value) {
		this.value = value;
	}

	public void addAdj(Vertex v) {
		v.indegree++;
		adjacent.add(v);
		size++;
	}
	
	public Vertex next() {
		return adjacent.get(index++);
	}

	public boolean hasAdj() {
		int temp = index;//定義一個臨時的變量，使其到尾部的時候在指向0
		if(index == size)
			index = 0;
		return temp != size;
	}

}

class Graph {
	public ArrayList> vList = new ArrayList>();

	public Graph() {
		Vertex v1 = new Vertex(1);
		Vertex v2 = new Vertex(2);
		Vertex v3 = new Vertex(3);
		Vertex v4 = new Vertex(4);
		Vertex v5 = new Vertex(5);
		Vertex v6 = new Vertex(6);
		Vertex v7 = new Vertex(7);
		v1.addAdj(v2);
		v1.addAdj(v3);
		v1.addAdj(v4);
		v2.addAdj(v4);
		v2.addAdj(v5);
		v3.addAdj(v6);
		v4.addAdj(v3);
		v4.addAdj(v6);
		v4.addAdj(v7);
		v5.addAdj(v4);
		v5.addAdj(v7);
		v7.addAdj(v6);
		vList.add(v1);
		vList.add(v2);
		vList.add(v3);
		vList.add(v4);
		vList.add(v5);
		vList.add(v6);
		vList.add(v7);
	}

	public String toString() {
		StringBuffer s = new StringBuffer();
		Iterator> ite = vList.iterator();
		System.out.println("v1  v2  v3  v4  v5  v6  v7   ");
		while (ite.hasNext())
			s.append(ite.next().topNum + "   ");
		return new String(s);
	}

	public String printDist() {
		StringBuffer s = new StringBuffer();
		Iterator> ite = vList.iterator();
		System.out.println("v1  v2  v3  v4  v5  v6  v7   ");
		while (ite.hasNext())
			s.append(ite.next().dist + "   ");
		return new String(s);
	}

}

public class GraphTest {
	/**
	 * 方法名：topSort 說明：拓撲排序 是對無環圖進行的
	 */
	public static void topSort(Graph graph) {
		Queue> q = new LinkedList>();
		Vertex v = findIndegreeZero(graph);
		if (v == null) {
			System.out.println("該圖有環，無法進行拓撲排序");
			return;
		}
		q.add(v);
		int count = 0;
		while (!q.isEmpty()) {
			Vertex w = q.poll();
			w.topNum = ++count;
			while (w.hasAdj()) {
				Vertex e = w.next();
				if (--e.indegree == 0)
					q.add(e);
			}
		}
	}

	private static Vertex findIndegreeZero(Graph graph) {
		for (Vertex v : graph.vList) {
			if (v.indegree == 0)
				return v;
		}
		return null;
	}

	/**
	 * 方法名：unWeighted 說明：無權的最短路徑
	 */
	public static void unWeighted(Vertex s) {
		Queue> q = new LinkedList>();
		s.dist = 0;
		q.add(s);
		while (!q.isEmpty()) {
			Vertex v = q.poll();
			while (v.hasAdj()) {
				Vertex w = v.next();
				if (!w.visited) {
					w.dist = v.dist + 1;
					w.visited = true;
					q.add(w);
				}
			}
		}
	}
	public static void main(String[] args) {
		Graph g = new Graph();
		topSort(g);
		System.out.println(g);
		unWeighted(g.vList.get(0));// 各個頂點到0的路徑；
		System.out.println(g.printDist());
	}
}