java 图的拓扑排序（利用Vector存储）

Stack类：

package com.javaeye.rsrt;

/**
 * 栈，遵循先进后出的原则，用来保存元素
 * 
 * @author nishiting
 * 
 */
public class Stack {

	private int[] st;
	private int top;
	private int count;

	/**
	 * 构造一个栈
	 * 
	 * @param size
	 *            栈的大小
	 */
	public Stack(int size) {
		st = new int[size];
		top = -1;
		count = 0;
	}

	/**
	 * 元素进栈
	 * 
	 * @param j
	 *            要进栈的元素
	 */

	public void push(int j) {
		count++;
		st[++top] = j;
	}

	/**
	 * 元素出栈
	 * 
	 * @return 出栈的元素
	 */

	public int pop() {

		return st[top--];
	}

	/**
	 * 查询栈顶元素
	 * 
	 * @return 栈顶元素
	 */

	public int peek() {
		return st[top];
	}

	/**
	 * 查询栈是否为空
	 * 
	 * @return 栈是否为空
	 */

	public boolean isEmpty() {
		count--;
		return (top == -1);
	}

	/**
	 * 查看栈里的所有元素
	 */

	public void list() {

		for (int i = 0; i < count; i++) {

			System.out.print(st[i] + "   ");

		}
		System.out.println();
	}

	/**
	 * 得到栈里一共有多少元素
	 * 
	 * @return 栈里的元素个数
	 */
	public int getCount() {
		return count;
	}

	/**
	 * 查看栈里是否包含某个元素
	 * 
	 * @param i
	 *            要查询的元素
	 * @return 是否包含了要查询的元素
	 */

	public boolean isContains(int i) {
		for (int k = 0; k < st.length; k++) {

			System.out.print("开始比较" + i + "此时的result:");
			list();
			System.out.println();
			if (st[k] == i) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * 得到栈里的元素集
	 * @return 栈里的元素集合
	 */
	public int[] getSt(){
		return st;
	}

}

 Graph类：

package com.javaeye.rsrt;

import java.util.Arrays;
import java.util.List;
import java.util.Vector;

/**
 * 
 * @author nishiting
 * 
 */

public class Graph {

	int vertexNum;
	Vector[] vector;
	Stack stack;
	int[] result;
	int[] in;// 入度

	/**
	 * 
	 * 构造一个图
	 * 
	 * @param num
	 *            图的顶点数
	 * 
	 */
	public Graph(int num) {

		vertexNum = num;
		vector = new Vector[vertexNum];
		stack = new Stack(num);
		result = new int[vertexNum];
		in = new int[vertexNum];

	}

	/**
	 * 向图中添加无向边
	 * 
	 * @param I
	 *            边的一个顶点
	 * @param J
	 *            边的另一个顶点
	 * @return 是否添加成功
	 */
	public boolean addEdge(int I, int J) {

		/**
		 * 判断用户输入的是否是一个顶点，如果是，则返回flase,添加不成功
		 */
		if (J == I) {
			return false;
		}

		/**
		 * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在
		 * 
		 */
		if (I < vertexNum && J < vertexNum && I >= 0 && J >= 0) {

			/**
			 * 
			 * 判断边是否存在
			 */

			if (isEdgeExists(I, J)) {

				return false;
			}

			/**
			 * 添加边，将孤头的入度加1
			 */

			vector[I].add(J);
			in[J]++;
			return true;
		}
		return false;
	}

	/**
	 * 判断有向边是否存在
	 * 
	 * @param i
	 *            要查询的有向边的一个孤尾
	 * @param j
	 *            要查询的有向边的另一个孤头
	 * @return 边是否存在，false:不存在，true:存在
	 */

	public boolean isEdgeExists(int i, int j) {

		/**
		 * 判断所输入的顶点值是否在图所顶点范围值内，如果不在，则提示顶点不存在
		 * 
		 */
		if (i < vertexNum && j < vertexNum && i >= 0 && j >= 0) {

			if (i == j) {
				return false;
			}

			/**
			 * 判断i的邻接结点集是否为空
			 */

			if (vector[i] == null) {
				vector[i] = new Vector(8);
			}

			/**
			 * 判断这条边是否存在，如果存在，则提示边已经存在
			 */
			for (int q = 0; q < vector[i].size(); q++) {

				if (((Integer) vector[i].get(q)).intValue() == j) {
					System.out.println("顶点" + i + "和" + "顶点" + j + "这两点之间存在边");
					return true;

				}
			}
		}
		return false;
	}

	public void TopSort() {

		for (int i = 0; i < vertexNum; i++)
			if (in[i] == 0)
				stack.push(i);
		int k = 0;
		while (!stack.isEmpty()) {

			result[k] = (Integer) stack.pop();

			if (vector[result[k]] != null) {
				for (int j = 0; j < vector[result[k]].size(); j++) {

					int temp = (Integer) vector[result[k]].get(j);
					if (--in[temp] == 0) {
						stack.push(temp);
					}

				}

			}
			k++;

		}

		if (k < vertexNum) {
			System.out.println("有回路");
			System.exit(0);

		}

	}

	public int[] getResult() {
		return result;

	}

}

 测试类：

package com.javaeye.rsrt;

import java.util.List;

import junit.framework.TestCase;

public class GraphTest extends TestCase {

	public void testGraph(){
		Graph graph = new Graph(6);
		graph.addEdge(1, 0);
		graph.addEdge(2, 0);
		graph.addEdge(3, 0);
		graph.addEdge(1, 3);
		graph.addEdge(2, 3);
		graph.addEdge(3, 5);
		graph.addEdge(4, 2);
		graph.addEdge(4, 3);
		graph.addEdge(4, 5);
		
		graph.TopSort();
		int[] list = graph.getResult();
		System.out.println("拓扑排序的结果为：");
		for(int i : list){
			
			System.out.print(i+"        ");
		}
	}
	
}