拓扑排序是可以用图模拟的另一种操作方式.
他可用于表示一种情况, 即某些项目或事件必须按照某种顺序排列发生.
基本思想:
步骤 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
来源: http://www.jianshu.com/p/b1d626203fe1