拓扑排序的实现（Java）

拼搏现实的明天。 2024-04-18 23:58 33阅读 0赞

拓扑排序是图数据结构的一种操作，他可以表示一些事情可以按照一定的先后顺序执行的算法。在这种图中，需要边是有方向的，就是它构成的图就是有向图，在有向图中，顶点只能沿着指定的方向移动，如下图所示，就是一个简单的有向图。

![20190914182840883.png][]

另外在使用邻接矩阵表示时，与无向图的表示也是有区别的，因为它的边是单向的，所以一条边在邻接矩阵中的表示只有一项。

![20190914183549609.png][]

有向图的拓扑排序可以用在如下的场合，在数据结构与算法中文（Java）一书中，提到大学生选课的问题，大学生不能随心所欲的选择课程，因为有一些课程有先修课程，就是说这些课程必须先学习，修够了必要的课程也是取得相关专业学位的“先决条件”，为了得到学位，必须完成高级研讨会课程和比较文学课程，但是如果不选择高等代数与解析几何，就不能修高级研讨会，同样的，不修英文写作，也不能选择比较文学课程，同时要修几何，以便学习解析几何，以及修代数，以便学习高等数学和解析几何。下图表示了这样的关系。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70][]

按照课程与学位先后顺序，可以得到这样的一个排序：

BAEDGCFH，

实际上，我们可以先修英文写作（C）和比较文学（F），再修几何（B）与代数（A）那么可以得到这样的一个顺序：

CFBAEDGH

拓扑排序的思想很简单，有两个步骤是必须的：

1、找到一个没有后继的顶点。

2、从图中删除这个顶点，在列表的前面插入顶点的标记。

重复上述1和2两个步骤，直到所有的顶点都从图中删除，这时候，列表显示的顶点顺序就是拓扑排序的结果。这里的后继也是一些顶点，它与当前节点是通过一条边相连，而且边的方向是指向后继顶点的，在图中，有一条边是从A指向D，我们说D是A的后继。后继可以有多个，也可以没有，在上边的图中，只有H顶点是没有后继的。

拓扑排序能够处理的图，要求是没有环的，所谓的环就是路径的起点和终点都是同一个顶点，这样就形成了一个环。不包含环的图又叫树，这是一种特殊意义的树，有向无环这样的图，又叫有向无环图directed acyclic graph，缩写为DAG。

拓扑排序中最重要的就是删除无后继的顶点，最先删除的节点，存放在排序数组的最后面。然后依次存放图中没有后继的顶点，直到图中没有顶点。

下面给出拓扑排序的代码：

Vertex.java

package com.xxx.algorithm.wh.topgraph;
    public class Vertex {
    	public char label;
    	public Vertex(char label){
    		this.label = label;
    	}
    }

Graph.java

package com.xxx.algorithm.wh.topgraph;
    
    public class Graph {
    
    	private final int MAX_VERTS=20;
    	private Vertex vertList[];
    	private int adjMat[][];
    	private int nVerts;
    	private char sortedArray[];
    	
    	public Graph(){
    		vertList= new Vertex[MAX_VERTS];
    		adjMat = new int[MAX_VERTS][MAX_VERTS];
    		nVerts = 0;
    		for(int i=0;i<MAX_VERTS;i++){
    			for(int j=0;j<MAX_VERTS;j++){
    				adjMat[i][j] = 0;
    			}
    		}
    		sortedArray = new char[MAX_VERTS];
    	}
    
    	public void addVertex(char label){
    		vertList[nVerts++] = new Vertex(label);
    	}
    	
    	public void addEdge(int start,int end){
    		adjMat[start][end] = 1;
    	}
    	
    	public void displayVertex(int v){
    		System.out.print(vertList[v].label+" ");
    	}
    	
    	public void topo(){
    		int orig_nVerts = nVerts;
    		while(nVerts>0){
    			int currentVertex = noSuccessors();
    			if(currentVertex==-1){
    				System.out.println("error:graph has cycles");
    				return;
    			}
    			sortedArray[nVerts-1] = vertList[currentVertex].label;
    			deleteVertex(currentVertex);
    		}
    		
    		System.out.print("topologically sorted order : ");
    		for(int i=0;i<orig_nVerts;i++){
    			System.out.print(sortedArray[i]);
    		}
    		System.out.println();
    	}
    	
    	private void moveRowUp(int row,int length){
    		for(int col=0;col<length;col++){
    			adjMat[row][col] = adjMat[row+1][col];
    		}
    	}
    	
    	private void moveColLeft(int col,int length){
    		for(int row=0;row<length;row++){
    			adjMat[row][col] = adjMat[row][col+1];
    		}
    	}
    	
    	public void deleteVertex(int delVert){
    		if(delVert != (nVerts-1)){
    			for(int i=delVert;i<nVerts-1;i++){
    				vertList[i] = vertList[i+1];
    			}
    			
    			for(int row=delVert;row<nVerts-1;row++){
    				moveRowUp(row, nVerts);
    			}
    			
    			for(int col=delVert;col<nVerts-1;col++){
    				moveColLeft(col, nVerts-1);
    			}
    		}
    		nVerts--;
    	}
    	
    	public int noSuccessors(){
    		boolean isEdge;
    		for(int row=0;row<nVerts;row++){
    			isEdge = false;
    			for(int col=0;col<nVerts;col++){
    				if(adjMat[row][col]>0){
    					isEdge = true;
    					break;
    				}
    			}
    			if(!isEdge)
    				return row;
    		}
    		return -1;
    	}
    	
    	public static void main(String[] args) {
    		Graph graph = new Graph();
    		graph.addVertex('A');
    		graph.addVertex('B');
    		graph.addVertex('C');
    		graph.addVertex('D');
    		graph.addVertex('E');
    		graph.addVertex('F');
    		graph.addVertex('G');
    		graph.addVertex('H');
    		
    		graph.addEdge(0, 3);
    		graph.addEdge(0, 4);
    		graph.addEdge(1, 4);
    		graph.addEdge(2, 5);
    		graph.addEdge(3, 6);
    		graph.addEdge(4, 6);
    		graph.addEdge(5, 7);
    		graph.addEdge(6, 7);
    		
    		graph.topo();
    				
    	}
    
    }

运行程序，打印信息如下：

topologically sorted order : BAEDGCFH

这个排序顺序也是我们前面提到的一种顺序。就是先修几何，然后修英文写作，最后获得学位，满足条件。

[20190914182840883.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/51ddf812bc104a18bf9ceb11e1be814b.png
[20190914183549609.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/be7463b705f641458376f4ed6d2ccf0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlaW5pZmk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d7b51afe5a644a59bb80fb3c09db5351.png