有向图的拓扑排序.md

拓扑排序是可以用图模拟的另一种操作方式。他可用于表示一种情况，即某些项目或事件必须按照某种顺序排列发生。

基本思想：

• 步骤1、找到一个没有后继的顶点
• 步骤2、从图中删除这个顶点，在列表的前面插入顶点标记 以下为java源码：

/**
 * @author hasee
 * @TIME 2017年5月4日
 * 有向图的拓补排序
 * 步骤1、找到一个没有后继的顶点
 * 步骤2、从图中删除这个顶点，在列表的前面插入顶点标记
 */
public class TopoApp {
	//测试
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Graph02 theGraph = new Graph02();
		theGraph.addVertex('A');
		theGraph.addVertex('B');
		theGraph.addVertex('C');
		theGraph.addVertex('D');
		theGraph.addVertex('E');
		theGraph.addVertex('F');
		theGraph.addVertex('G');
		theGraph.addVertex('H');
		theGraph.addEdge(0, 3);//AD
		theGraph.addEdge(0, 4);//AE
		theGraph.addEdge(1, 4);//BE
		theGraph.addEdge(2, 5);//CF
		theGraph.addEdge(3, 6);//DG
		theGraph.addEdge(4, 6);//EG
		theGraph.addEdge(5, 7);//FH
		theGraph.addEdge(6, 7);//GH
		theGraph.topo();
		}
}
/**
 * 有一种拓扑图是拓扑排序是做不到的，那就是有环的情况，所以需要判断是否为环
 */
/**
 * @author hasee
 * @TIME 2017年5月4日
 * 保存顶点信息的类
 */
class Vertex{
	public char label;
	public Vertex(char lab){
		this.label = lab;
	}
}
class Graph02{
	private final int MAX_VRERTS = 20;
	private Vertx vertxList[];//包含所有的节点信息
	private int adjMat[][];//邻接矩阵
	private int nVert;//当前vertxList的指向下标
	private char sortedArray[];//存储
	//初始化
	public Graph02(){
		vertxList = new Vertx[MAX_VRERTS];
		adjMat = new int[MAX_VRERTS][MAX_VRERTS];
		nVert = 0;
		for(int j=0;j<MAX_VRERTS;j++)
			for(int k = 0;k<MAX_VRERTS;k++)
				adjMat[j][k] = 0;
		sortedArray = new char[MAX_VRERTS];
	}
/**
 * @param lab
 */
public void addVertex(char lab){
	vertxList[nVert++] = new Vertx(lab);
}
/**
 * @param start
 * @param end
 * 邻接矩阵，和之前的无向图区分，单向
 */
public void addEdge(int start,int end){
	adjMat[start][end] = 1;
}
/**
 * @param v
 * 展示节点数值
 */
public void display(int v){
	System.out.println(vertxList[v].lable);
}
/**
 * 主要工作是在whil循环中完成的
 * 1、调用noSuccessor找到任意一个没有后继的顶点
 * 2、如果找到这样一个顶点把它放到数组sortedArray中，并且从图中删除
 * 3、如果没有这样的顶点则，则此图必然存在环
 * */
public void topo(){
	int orig_nVerts=nVert;//记住有多多少中下标
	while(nVert>0){
		int currentVerts = noSuccessor();//找到一个后继顶点下标
		if(currentVerts  == -1){
			System.out.println("图中存在环！！");
			return;
		}
		//从后往前保存要删除的顶点
		sortedArray[nVert-1] = vertxList[currentVerts].lable;
		
		deleteVertx(currentVerts);//在图中删除这个顶点
	}
	//如果没有环就输出所有的有向图顶点
	for(int i=0;i<orig_nVerts;i++)
		System.out.print(sortedArray[i]+" ");
}
/**
 * @return
 * noSuccessor方法使用邻接矩阵找到没有后继的的顶点，在外层循环中，沿着每一行考察每个顶点
 * 在每一行中，用内层循环扫描值为1的列，如果找一个就说明顶点后面有后继，然后跳出内层循环考察下一个顶点
 * 只有一整行都没有找到，则说明这个顶点没有后继，并返回它的行号。如果没有这样的顶点就返回-1说明这是个环
 */
public int noSuccessor(){
	boolean isEdge;
	for(int row = 0;row<nVert;row++){
		isEdge =false;
		for(int col =0;col<nVert;col++){
			if(adjMat[row][col]>0){
				isEdge = true;
				break;
			}
			if(!isEdge)
				return row;
		}
	}
	return -1;
}
/**
 * @param delVert
 * 删除一个顶点很简单，顶点从vertxList数组中删除，后面的顶点向前移动填补空位。同样的，顶点的行列从邻接矩阵中删除
 * 下面的行和右面的列移动来填补空位。这些操作有deleteVertx 、moveRow、moveColLeft来完成
 */
public void deleteVertx(int delVert){
		if(delVert != nVert -1){//如果不是最后的顶点
			//从数组中删除,后面的顶点向前移
			for(int j=delVert;j<nVert-1;j++)
				vertxList[j] = vertxList[j+1];
			for(int row =delVert; row<nVert-1;row++)
				moveRowUp(row,nVert);
			for(int col=delVert;col<nVert-1;col++)
				 moveColLeft(col,nVert-1);
				
		}
		nVert--;//数组下标减一
}
/**
 * @param row
 * @param length
 * 将后面的行向上移一位
 */
private void moveRowUp(int row,int length){
	for(int col=0;col<length;col++)
		adjMat[row][col] = adjMat[row+1][col];
}
/**
 * @param col
 * @param length
 * 将后面的列向左移一位
 */
private void moveColLeft(int col,int length){
	for(int row = 0;row<length;row++)
		adjMat[row][col] = adjMat[row][col+1];
}
}

测试结果： H G F E D C B A