该类包括

  1. 基础方法
  2. 邻接矩阵
  3. 邻接表
  4. 深度优先遍历
  5. 广度优先遍历
  6. 最小生成树
  7. 最短路径
  8. 拓扑排序

    package com.naah.s4_Graph;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Stack;
    
    /**
    *
    * ClassNameCh 图
    * ClassNameEn Graph
    * Description 数据结构图
    * Company
    * @author Naah
    * @date 2017年8月13日 下午11:18:46
    * @param
    */
    public class Graph> {
    
    	// 顶点数组
    	private T[] vertexs;
    
    	// 邻接表元素数组
    	private VertexNeighborNode[] neighborArray;
    
    	// 邻接矩阵
    	private int[][] matrix;
    
    	// 度数组
    	private Edge[] edges;
    
    	// 泛型对象的类文件
    	private Class Class;
    
    	// 顶点数量
    	private int size;
    
    	// 常亮:未连接
    	public static final int NO_LINK = -1;
    
    	/**
    	 * 构造方法
    	 * @param Class 类对象
    	 * @param vertexs 顶点可选数组
    	 */
    	public Graph(Class Class, T... vertexs) {
    		super();
    		this.vertexs = vertexs;
    		this.size = vertexs.length;
    		this.Class = Class;
    
    	}
    
    	/**
    	 * 构造方法
    	 * @param vertexs 可选数组
    	 */
    	public Graph(T... vertexs) {
    		super();
    		this.vertexs = vertexs;
    		this.size = vertexs.length;
    
    	}
    
    	/**
    	 * 基础添加方法
    	 * @param vertex 顶点
    	 */
    	private void basicAdd(T vertex) {
    		// 创建新顶点数组
    		T[] newVertexs = (T[]) Array.newInstance(Class, vertexs.length + 1);
    
    		// 将原顶点数组复制到新顶点数组
    		System.arraycopy(vertexs, 0, newVertexs, 0, vertexs.length);
    
    		// 将新顶点添加到新顶点数组
    		newVertexs[newVertexs.length - 1] = vertex;
    
    		// 将新顶点数组设置为原顶点数组
    		vertexs = newVertexs;
    
    		// 长度增加
    		size++;
    
    	}
    
    	/**
    	 * 添加顶点方法(无邻接矩阵)
    	 * @param vertex 顶点
    	 * @return 顶点的下标
    	 * @throws Exception 有邻接矩阵
    	 */
    	public int add(T vertex) throws Exception {
    
    		// 判断当前对象是否含有邻接矩阵、
    		// 没有则进入
    		if (matrix == null) {
    
    			// 添加顶点
    			basicAdd(vertex);
    
    			// 返回新顶点下标
    			return vertexs.length - 1;
    		} else {
    
    			// 有邻接矩阵则抛出异常
    			throw new Exception("当前存在邻接矩阵!请使用重载方法!");
    		}
    
    	}
    
    	/**
    	 * 添加节点(有邻接矩阵)
    	 * @param vertex 顶点
    	 * @param inWeight 入度(不包含自己)
    	 * @param outWeight 出度(不包含自己)
    	 * @return 顶点下标
    	 * @throws Exception 邻接数组长度不对
    	 * @throws Exception 不存在邻接数组
    	 */
    	public int add(T vertex, int[] inWeight, int[] outWeight) throws Exception {
    
    		// 判断是否有邻接矩阵,如果没有则抛出异常
    		if (matrix == null) {
    			throw new Exception("当前不存在邻接矩阵!请使用重载方法!或建立邻接矩阵!");
    		}
    
    		// 判断邻接数组长度是否与顶点数组长度相同
    		if (inWeight.length != vertexs.length
    				|| outWeight.length != vertexs.length) {
    			throw new Exception("邻接数组长度不对");
    		}
    
    		// 添加元素
    		basicAdd(vertex);
    
    		// 创建新邻接矩阵
    		int[][] newMatrix = new int[vertexs.length][vertexs.length];
    
    		// 遍历原邻接矩阵
    		for (int i = 0; i < matrix.length; i++) {
    
    			// 将原邻接矩阵数组元素复制到新邻接矩阵数组中
    			System.arraycopy(matrix[i], 0, newMatrix[i], 0, matrix[i].length);
    
    			// 将新顶点的出度添加到邻接矩阵中
    			newMatrix[i][vertexs.length - 1] = inWeight[i];
    
    			// 将新节点的入度添加到邻接矩阵中
    			newMatrix[vertexs.length - 1][i] = outWeight[i];
    		}
    
    		// 顶点与自己的度为0
    		newMatrix[vertexs.length - 1][vertexs.length - 1] = 0;
    
    		// 将新的邻接矩阵设置为邻接矩阵
    		matrix = newMatrix;
    
    		// 返回行顶点的下标
    		return vertexs.length - 1;
    	}
    
    	/**
    	 * 得到出度数量
    	 * @param vertex 顶点
    	 * @return 出度数量
    	 * @throws Exception 未定义邻接矩阵
    	 */
    	public int getOutSize(T vertex) throws Exception {
    		// 如果邻接矩阵为空
    		if (matrix == null) {
    
    			// 抛出异常
    			throw new Exception("未找到邻接矩阵");
    		}
    
    		// 得到顶点下标
    		int position = getIndex(vertex);
    
    		// 判断是否找到
    		if (position != -1) {
    
    			// 出度数量
    			int size = 0;
    
    			// 遍历顶点的出度数组
    			for (int i = 0; i < matrix[position].length; i++) {
    
    				// 不为自己 并且 有链接
    				if (matrix[position][i] > 0 && matrix[position][i] != NO_LINK) {
    
    					// 出度数量增加
    					size++;
    				}
    			}
    
    		} else {
    
    			throw new Exception("未找到该顶点");
    		}
    
    		// 返回出度数量
    		return size;
    	}
    
    	/**
    	 * 得到入度数量
    	 * @param vertex 顶点
    	 * @return 入度数量
    	 * @throws Exception 未找到邻接矩阵
    	 */
    	public int getInSize(T vertex) throws Exception {
    
    		// 如果邻接矩阵为空
    		if (matrix == null) {
    
    			// 抛出异常
    			throw new Exception("未找到邻接矩阵");
    		}
    
    		// 得到顶点下标
    		int position = getIndex(vertex);
    
    		// 判断是否找到
    		if (position != -1) {
    
    			// 出度数量
    			int size = 0;
    
    			// 遍历入度数组
    			for (int i = 0; i < matrix.length; i++) {
    
    				// 不为自己 并且 有链接
    				if (matrix[i][position] > 0 && matrix[i][position] != NO_LINK) {
    
    					// 出度数量增加
    					size++;
    				}
    			}
    		} else {
    			throw new Exception("未找到该节点");
    		}
    		// 返回出度数量
    		return size;
    	}
    
    	/**
    	 * 得到下标位置
    	 * @param vertex 顶点
    	 * @return下标位置
    	 */
    	public int getIndex(T vertex) {
    
    		// 遍历顶点数组
    		for (int i = 0; i < vertexs.length; i++) {
    
    			// 顶点不为空 并且 相同
    			if (vertexs[i] != null && vertexs[i].equals(vertex)) {
    
    				// 找到则返回下标
    				return i;
    			}
    		}
    
    		// 找不到返回-1
    		return -1;
    	}
    
    	/**
    	 * 得到邻接矩阵
    	 * @return
    	 */
    	public int[][] getMatrix() {
    		return matrix;
    	}
    
    	/**
    	 * 设置邻接矩阵
    	 * @param matrix 邻接矩阵
    	 * @throws Exception 数组长度不对
    	 */
    	public void setMatrix(int[][] matrix) throws Exception {
    		if (matrix.length != this.vertexs.length) {
    			throw new Exception("二维数组长度不对");
    		}
    		for (int i = 0; i < matrix.length; i++) {
    			if (matrix[i].length != this.vertexs.length) {
    				throw new Exception("二维数组长度不对");
    			}
    
    		}
    		this.matrix = matrix;
    	}
    
    	/**
    	 * 得到顶点数量
    	 * @return 顶点数量
    	 */
    	public int getSize() {
    		return size;
    	}
    
    	/**
    	 * 设置顶点数组
    	 * @param vertexs 顶点数组
    	 */
    	public void setVertexs(T[] vertexs) {
    		this.vertexs = vertexs;
    		this.size = vertexs.length;
    	}
    
    	/**
    	 * 得到顶点数组
    	 * @return 顶点数组
    	 */
    	public T[] getVertexs() {
    		return vertexs;
    	}
    
    	/**
    	 * 得到度数组
    	 * @return
    	 */
    	public Edge[] getEdges() {
    		return edges;
    	}
    
    	/**
    	 * 深度优先遍历方法(递归)
    	 */
    	public void depthFirst() {
    		// 建立记录数组
    		boolean[] isVisited = new boolean[size];
    
    		// 顶点数组循环
    		for (int i = 0; i < vertexs.length; i++) {
    
    			// 全部遍历标记,为节省资源
    			boolean isAllTrue = true;
    
    			// 遍历记录数组是否已全部记录
    			for (int j = 0; j < isVisited.length; j++) {
    
    				// 如果有一个没记录
    				if (isVisited[j] == false) {
    
    					// 则将全部遍历标记设置为false
    					isAllTrue = false;
    
    					// 跳出该循环
    					break;
    				}
    			}
    
    			// 如果已全部遍历
    			if (isAllTrue) {
    
    				// 跳出循环,不再继续
    				break;
    			}
    
    			// 判断当前顶点是否已遍历,如果没有则进行遍历
    			if (!isVisited[i]) {
    
    				// 遍历该顶点
    				depthFirst(isVisited, i);
    			}
    		}
    	}
    
    	/**
    	 * 深度优先遍历实现方法(递归)
    	 * @param isVisited 遍历记录数组
    	 * @param i 遍历的起点
    	 */
    	private void depthFirst(boolean[] isVisited, int i) {
    
    		// 将当前顶点设置为已遍历
    		isVisited[i] = true;
    
    		// 找到该顶点的第一个出度顶点下标
    		int weight = getFirstNeighbor(i);
    
    		// 深度遍历出度顶点,直到没有出度顶点
    		while (weight != -1) {
    
    			// 判断出度顶点是否已遍历过,如果没遍历过则进行遍历
    			if (!isVisited[weight]) {
    
    				// 输出该出度顶点的信息
    				System.out.println("第" + weight + "个顶点被访问:" + vertexs[weight]);
    
    				// 深度遍历该出度顶点
    				depthFirst(isVisited, weight);
    			}
    
    			// 如果没有出度顶点,则查找该顶点下一个出度顶点
    			weight = getNextNeighbor(i, weight);
    		}
    	}
    
    	/**
    	 * 得到该顶点的第一个出度顶点下标
    	 * @param i 顶点数组下标
    	 * @return 第一个出度顶点下标
    	 */
    	private int getFirstNeighbor(int i) {
    
    		// 循环矩阵中顶点的出度数组
    		for (int j = 0; j < size; j++) {
    
    			// 如果该出度不为0,并且相连
    			if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
    
    				// 返回出度顶点下标
    				return j;
    			}
    		}
    
    		// 返回未连接
    		return NO_LINK;
    	}
    
    	/**
    	 * 得到该顶点从某位置后的第一个出度顶点下标
    	 * @param i 顶点数组下标
    	 * @param weight 位置
    	 * @return 出度顶点下标
    	 */
    	private int getNextNeighbor(int i, int weight) {
    
    		// 从某位置开始循环矩阵中顶点的出度数组
    		for (int j = weight + 1; j < size; j++) {
    
    			// 如果该出度不为0,并且相连
    			if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK) {
    
    				// 返回出度顶点下标
    				return j;
    			}
    		}
    
    		// 返回未连接
    		return NO_LINK;
    	}
    
    	/**
    	 * 广度优先遍历方法(递归)
    	 */
    	public void bredthFirst() {
    		// 建立记录数组
    		boolean[] isVisited = new boolean[size];
    
    		// 创建队列
    		LinkedList queue = new LinkedList();
    
    		// 广度优先遍历方法实现,从第一个开始
    		bredthFirst(isVisited, queue, 0);
    
    	}
    
    	/**
    	 * 广度优先算法遍历方法实现
    	 * @param isVisited 记录数组
    	 * @param queue 队列
    	 * @param i 开始顶点
    	 */
    	private void bredthFirst(boolean[] isVisited, LinkedList queue,
    			int i) {
    
    		// 将当前顶点设置为已遍历
    		isVisited[i] = true;
    		System.out.println("第" + i + "个顶点被访问了:" + vertexs[i]);
    
    		// 循环将该顶点的出度顶点下标添加到队列中
    		for (int j = 0; j < size; j++) {
    
    			// 出度顶点判断,不为自己 并且 相连 并且没有访问过
    			if (matrix[i][j] != 0 && matrix[i][j] != NO_LINK && !isVisited[j]) {
    
    				// 添加到队列
    				queue.offer(j);
    			}
    		}
    
    		// 如果队列不为空则循环
    		while (!queue.isEmpty()) {
    
    			// 将顶点下标从队首移出
    			int weight = queue.poll();
    
    			// 如果该顶点没访问过
    			if (!isVisited[weight]) {
    
    				// 递归广度遍历该方法
    				bredthFirst(isVisited, queue, weight);
    			}
    		}
    
    	}
    
    	/**
    	 * 最小生成树方法-普里姆算法
    	 *
    	 */
    	public void prim() {
    
    		// 创建最小权值数组
    		int[] least = new int[size];
    
    		// 上一个顶点下标数组
    		int[] lastIndex = new int[size];
    
    		// 最小权值和
    		int sum = 0;
    
    		// 初始化最小权值数组
    		for (int i = 0; i < least.length; i++) {
    			least[i] = matrix[0][i];
    		}
    
    		// 循环查找最小生成树
    		for (int i = 1; i < least.length; i++) {
    
    			// 将最小权值设置为int最大值
    			int min = Integer.MAX_VALUE;
    
    			// 将最小权值下标设置为0
    			int minIndex = 0;
    
    			// 循环查找最小权值数组中的最小值
    			for (int j = 1; j < least.length; j++) {
    
    				// 大于0的最小权值
    				if (least[j] > 0 && least[j] < min) {
    
    					// 设置为最小值
    					min = least[j];
    
    					// 将当前下标设置为最小权值下标
    					minIndex = j;
    				}
    			}
    
    			// 输出已找到的最小顶点
    			System.out.println(
    					lastIndex[minIndex] + "顶点---" + minIndex + "顶点:" + min);
    
    			// 将已找到的最小权值点设置为0,标记为已找到
    			least[minIndex] = 0;
    
    			// 将最小权值累加到最小权值和中
    			sum += min;
    
    			// 将上一个顶点的所有出度权值添加到最小权值数组中
    			for (int j = 1; j < least.length; j++) {
    
    				// 没遍历的顶点 并且 上一个顶点所到该顶点的权值 小于 最小权值数组中到该顶点的权值时 进入
    				// 最小权值数组中无法到达的顶点 并且上一个顶点能到达该顶点时 进入
    				if ((least[j] > 0 && matrix[minIndex][j] != NO_LINK
    						&& matrix[minIndex][j] < least[j])
    						|| (least[j] == NO_LINK
    								&& matrix[minIndex][j] != NO_LINK)) {
    
    					// 将上一个顶点到该顶点的出度权值添加到最小权值数组中
    					least[j] = matrix[minIndex][j];
    
    					// 将上一个顶点设置为该顶点的入度顶点
    					lastIndex[j] = minIndex;
    				}
    			}
    
    		}
    
    		// 输出最小权值和
    		System.out.println(sum);
    	}
    
    	/**
    	 * 最小生成树方法-克鲁斯卡尔算法
    	 */
    	public void kruskal() {
    
    		// 创建查找数组
    		// 该数组下标为顶点下边
    		// 该数组值为顶点出度顶点下标
    		int[] parent = new int[size];
    
    		// 最小权值和
    		int sum = 0;
    
    		// 构建度数组
    		createEdge();
    
    		// 循环出度数组
    		for (Edge edge : edges) {
    
    			// 从查找数组中寻找该出度的头所到达的顶点下标
    			int n = find(parent, edge.begin);
    
    			// 从查找数组中寻找该出度的尾所到达的顶点下标
    			int m = find(parent, edge.end);
    
    			// 如果头尾顶点下标不相等,进入
    			// 如果头尾顶点下标相对,则代表该度为多余度
    			if (n != m) {
    
    				// 输出该度信息
    				System.out.println(
    						edge.begin + "顶点---" + edge.end + "顶点:" + edge.weight);
    
    				// 将查询数组中头下标的值设置为尾下标
    				parent[n] = m;
    
    				// 累计权值
    				sum += edge.weight;
    			}
    		}
    
    		// 输出权值
    		System.out.println(sum);
    
    	}
    
    	/**
    	 * 查找数组中该顶点能到达的最后位置
    	 * @param parent 查找数组
    	 * @param i 顶点下标
    	 * @return 最后位置
    	 */
    	private int find(int[] parent, int i) {
    
    		// 如果该下标位置有出度则循环
    		while (parent[i] > 0) {
    
    			// 将出度下标设置为下一次查找的下标
    			i = parent[i];
    		}
    
    		// 返回最后位置
    		return i;
    	}
    
    	/**
    	 * 构建度数组
    	 */
    	public void createEdge() {
    
    		// 创建度的链表,不确定度的数量,所以使用链表
    		List edgeList = new LinkedList();
    
    		// 从第一个顶点开始构建度的链表
    		createEdge(edgeList, 0);
    
    		// 创建度的数组
    		this.edges = new Edge[edgeList.size()];
    
    		// 数组赋值标记
    		int i = 0;
    
    		// 遍历链表,添加到数组
    		for (Edge edge : edgeList) {
    
    			// 将链表值添加到数组
    			this.edges[i] = edge;
    
    			// 标记自增
    			i++;
    		}
    
    		// 通过Edge类实现Comparable接口进行排序
    		Arrays.sort(this.edges);
    	}
    
    	/**
    	 * 构建度数组
    	 *
    	 * 此方法思路与广度优先相同
    	 * 但是没有采用上面的递归广度优先思路
    	 * 而是使用迭代完成
    	 * @param edges 度的链表
    	 * @param i 开始节点
    	 */
    	private void createEdge(List edges, int i) {
    
    		// 创建度的队列
    		LinkedList queue = new LinkedList();
    
    		// 将顶点下标添加到队列中
    		queue.offer(i);
    
    		// 队列不为空则循环
    		while (!queue.isEmpty()) {
    
    			// 取出队首顶点下标
    			int n = queue.poll();
    
    			// 取得顶点的第一个邻接点
    			int m = getFirstNeighbor(n);
    
    			// 当邻接点连接时循环
    			while (m != NO_LINK) {
    
    				// 是否包含度标记
    				boolean isHave = false;
    
    				// 遍历度链表
    				for (Edge e : edges) {
    
    					// 如果两节点相等
    					if (e.equals(n, m, matrix[n][m])) {
    
    						// 将标记设置为真
    						isHave = true;
    						break;
    					}
    				}
    
    				// 当没有该度时
    				if (!isHave) {
    
    					// 向度链表中添加该度
    					edges.add(new Edge(n, m, matrix[n][m]));
    
    					// 将邻接点下标添加到队尾
    					queue.offer(m);
    				}
    
    				// 得到m邻接点后的一个邻接点
    				m = getNextNeighbor(n, m);
    			}
    
    		}
    
    	}
    
    	/**
    	 * 最短路径-迪杰特斯拉算法
    	 * @param v 下标
    	 * @return 最小路径数组
    	 * @throws Exception
    	 */
    	public int[] dijstra(int v) throws Exception {
    
    		// 如果链接矩阵为空,则
    		if (matrix == null) {
    
    			// 抛出异常
    			throw new Exception("未找到邻接矩阵");
    		}
    
    		// 创建最短路径数组
    		int[] least = new int[size];
    
    		// 创建记录数组
    		boolean[] getLeastWeight = new boolean[size];
    		int k = 0;
    
    		// 初始化最短路径数组
    		for (int i = 0; i < least.length; i++) {
    			least[i] = matrix[v][i];
    
    		}
    
    		// 将当前下标记录
    		getLeastWeight[v] = true;
    
    		// 循环找出最短路径
    		for (int i = 0; i < least.length; i++) {
    
    			// 将最小值赋值
    			int min = Integer.MAX_VALUE;
    
    			// 循环查找最小的权值,并暂时保存下标
    			for (int j = 0; j < least.length; j++) {
    				if (!getLeastWeight[j] && least[j] > 0 && least[j] < min) {
    					min = least[j];
    					k = j;
    				}
    			}
    
    			// 将该顶点记录
    			getLeastWeight[k] = true;
    
    			// 循环最小权值的顶点,如果有比上一个顶点到那个顶点权值更小,则将更小的权值赋值
    			for (int j = 0; j < getLeastWeight.length; j++) {
    				if (!getLeastWeight[j] && ((matrix[k][j] + min < least[j]
    						&& matrix[k][j] > 0)
    						|| (least[j] == NO_LINK && matrix[k][j] != NO_LINK))) {
    					least[j] = matrix[k][j] + min;
    				}
    			}
    		}
    
    		// 返回最小路径数组
    		return least;
    
    	}
    
    	/**
    	 * 通过顶点的入度数量来构建邻接表
    	 * @param vertexsInEdgeNum 顶点的入度数量数组
    	 * @return 邻接表
    	 * @throws Exception 未找到顶点数组
    	 */
    	public VertexNeighborNode[] getNeighborArray(int... vertexsInEdgeNum)
    			throws Exception {
    
    		// 如果未找到顶点数组,抛出异常
    		if (vertexs == null) {
    			throw new Exception("未找到顶点数组!");
    		}
    
    		// 创建邻接表
    		neighborArray = new VertexNeighborNode[size];
    
    		// 通过传入的顶点入度数量数组构建邻接表
    		for (int i = 0; i < size; i++) {
    
    			// 通过顶点入度数量创建邻接表元素
    			neighborArray[i] = new VertexNeighborNode(vertexsInEdgeNum[i]);
    		}
    		// 返回邻接表
    		return neighborArray;
    	}
    
    	/**
    	 * 设置邻接表元素的度
    	 * @param neighborIndex 邻接表数组元素下标
    	 * @param array 邻接表度元素数组
    	 * @throws Exception 未找到邻接数组
    	 */
    	public void setNeighborEdgeNode(int neighborIndex, EdgeNode... array)
    			throws Exception {
    
    		// 如果邻接数组为空,抛出异常
    		if (neighborArray == null) {
    			throw new Exception("未找到邻接数组!");
    		}
    
    		// 如果度元素数组有元素,则
    		if (array.length > 0) {
    			// 将度元素数组第一个设置为邻接表元素的第一个度
    			neighborArray[neighborIndex].setFirstEdge(array[0]);
    		}
    
    		// 如果度元素数组长度超过1,则
    		if (array.length > 1) {
    			// 通过循环,将度元素数组剩余度链接到度元素链表中
    			for (int i = 1; i < array.length; i++) {
    
    				// 获取邻接表数组中的当前元素的第一个度
    				EdgeNode en = neighborArray[neighborIndex].getFirstEdge();
    
    				// 将当前度的下一个引用为第一个度
    				array[i].setNext(en);
    
    				// 将当前元素的第一个度设置为当前度
    				neighborArray[neighborIndex].setFirstEdge(array[i]);
    			}
    		}
    
    	}
    
    	/**
    	 * 拓扑排序方法
    	 * @throws Exception
    	 */
    	public void Topologic() throws Exception {
    
    		// 创建栈,用于添加入度为0的邻接元素下标
    		Stack zero = new Stack();
    
    		// 创建拓扑排序数量
    		int count = 0;
    
    		// 循环邻接表元素数组
    		for (int i = 0; i < size; i++) {
    
    			// 如果当前元素的入度数量为0
    			if (neighborArray[i].getIn() == 0) {
    
    				// 将当前元素的下标压入栈中
    				zero.push(i);
    			}
    		}
    
    		// 如果栈不为空,遍历栈
    		while (!zero.isEmpty()) {
    
    			// 弹出栈顶的下标
    			int zeroIndex = zero.pop();
    
    			// 输出该顶点的下标和值
    			System.out.println(zeroIndex + ":" + vertexs[zeroIndex]);
    
    			// 拓扑数量自增
    			count++;
    
    			// 遍历入度为0的邻接表元素的度元素
    			for (EdgeNode e = neighborArray[zeroIndex]
    					.getFirstEdge(); e != null; e = e.getNext()) {
    
    				// 取得弧尾顶点的下标(顶点的出度顶点)
    				int nextIndex = e.getIndex();
    
    				// 通过下标取得邻接表数组元素
    				VertexNeighborNode v = neighborArray[nextIndex];
    
    				// 将该元素的入度减1,证明该元素的入度有一个已遍历过
    				v.setIn(v.getIn() - 1);
    
    				// 如果该元素的当前入度为0,则
    				if (v.getIn() == 0) {
    
    					// 将该元素的下标压入栈中
    					zero.push(nextIndex);
    				}
    			}
    		}
    
    		// 如果遍历过的顶点数量不是全部顶点数量
    		if (count != size) {
    
    			// 则代表拓扑失败,有回环
    			throw new Exception("拓扑失败!有回环");
    		}
    	}
    }
    
    /**
    *
    * ClassNameCh 度
    * ClassNameEn Edge
    * Description 度的数据结构
    * Company
    * @author Naah
    * @date 2017年8月14日 下午10:52:53
    */
    class Edge implements Comparable {
    
    	// 度的头顶点下标
    	int begin;
    
    	// 度的尾顶点下标
    	int end;
    
    	// 度的权值
    	int weight;
    
    	public Edge() {
    		super();
    	}
    
    	/**
    	 * 构造函数
    	 * @param begin 头顶点下标
    	 * @param end 尾顶点下标
    	 * @param weight 权值
    	 */
    	public Edge(int begin, int end, int weight) {
    		super();
    		this.begin = begin;
    		this.end = end;
    		this.weight = weight;
    	}
    
    	/**
    	 * 判断相等方法
    	 * @param begin
    	 * @param end
    	 * @param weight
    	 * @return true/false
    	 */
    	public boolean equals(int begin, int end, int weight) {
    
    		// 首先判断权值相等
    		if (weight == this.weight) {
    
    			// 判断下标是否相同,包括头尾互换
    			if ((begin == this.begin && end == this.end)
    					|| (end == this.begin && begin == this.end)) {
    
    				// 返回相等
    				return true;
    			}
    
    		}
    
    		// 返回不相等
    		return false;
    
    	}
    
    	@Override
    	public String toString() {
    		return "Edge [begin=" + begin + ", end=" + end + ", weight=" + weight
    				+ "]";
    	}
    
    	/**
    	 * 判断大小方法
    	 * 以权值大小判断,为度数组的从小到大排序
    	 */
    	@Override
    	public int compareTo(Edge o) {
    
    		if (this.weight > o.weight) {
    			return 1;
    		} else if (this.weight < o.weight) {
    			return -1;
    		}
    		return 0;
    	}
    
    	public int getWeight() {
    		return weight;
    	}
    
    	public void setWeight(int weight) {
    		this.weight = weight;
    	}
    
    }
    

 边节点类

package com.naah.s4_Graph;

/**
 *
 * ClassNameCh 边节点
 * ClassNameEn EdgeNode
 * Description 边节点 ,用于记录该顶点的出度顶点
 * Company
 * @author Naah
 * @date 2017年8月17日 下午9:27:19
 */
public class EdgeNode {

	// 出度顶点下标
	private int index;

	// 下一个出度顶点的引用
	private EdgeNode next;

	// 权值
	private int weight;

	public EdgeNode(int index) {
		super();
		this.index = index;
	}

	public EdgeNode(int index, int weight) {
		super();
		this.index = index;
		this.weight = weight;
	}

	public int getIndex() {
		return index;
	}

	public void setIndex(int index) {
		this.index = index;
	}

	public EdgeNode getNext() {
		return next;
	}

	public void setNext(EdgeNode next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "EdgeNode [index=" + index + ", next=" + next + ", weight="
				+ weight + "]";
	}

}

邻接表元素类

package com.naah.s4_Graph;

/**
 *
 * ClassNameCh 邻接表元素
 * ClassNameEn VertexNeighborNode
 * Description 邻接表数组的元素,包括该顶点的第一条边
 * Company
 * @author Naah
 * @date 2017年8月17日 下午9:25:59
 * @param
 */
public class VertexNeighborNode {

	// 入度数
	private int in;

	// 边节点
	private EdgeNode firstEdge;

	public VertexNeighborNode(int in) {
		super();
		this.in = in;
	}

	public int getIn() {
		return in;
	}

	public void setIn(int in) {
		this.in = in;
	}

	public EdgeNode getFirstEdge() {
		return firstEdge;
	}

	public void setFirstEdge(EdgeNode firstEdge) {
		this.firstEdge = firstEdge;
	}

	@Override
	public String toString() {
		return "[in=" + in + ", firstEdge=" + firstEdge + "]";
	}

}