数据结构和算法17 之拓扑排序

  这一节我们学习一个新的排序算法，准确的来说，应该叫“有向图的拓扑排序”。所谓有向图，就是A->B，但是B不能到A。与无向图的区别是，它的边在邻接矩阵里只有一项（友情提示：如果对图这种数据结构部不太了解的话，可以先看一下这篇博文：数据结构和算法之 无向图。因为拓扑排序是基于图这种数据结构的）。

有向图的邻接矩阵如下表所示：


 
A
B
C

A
0
1
1

B
0
0
1

C
0
0
0

        所以针对前面讨论的无向图，邻接矩阵的上下三角是对称的，有一半信息是冗余的。而有向图的邻接矩阵中所有行列之都包含必要的信息，它的上下三角不是对称的。所以对于有向图，增加边的方法只需要一条语句：

[java] view plain copy

 

  1. //有向图中，邻接矩阵中只有一项  
  2. public void addEdge(int start, int end) {  
  3.     adjMat[start][end] = 1;  
  4. }  

        如果使用邻接表示意图，那么A->B表示A在它的链表中有B，但是B的链表中不包含A，这里就不多说了，本文主要通过邻接矩阵实现。

        因为图是有向的，假设A->B->C->D这种，那这就隐藏了一种顺序，即要想到D，必须先过C，必须先过B，必须先过A。它们无形中形成了一种顺序，这种顺序在实际中还是用的挺广泛的，比如，要做web开发，必须先学Java基础等等，这些都遵循一个顺序，所以拓扑排序的思想也是这样，利用有向图特定的顺序进行排序。但是拓扑排序的结果不是唯一的，比如A->B的同时，C->B，也就是说A和C都能到B，所以用算法生成一个拓扑排序时，使用的方法和代码的细节决定了会产生那种拓扑排序。

        拓扑排序的思想虽然不寻常，但是却很简单，有两个必要的步骤：

        1. 找到一个没有后继的顶点；

        2.从图中删除这个顶点，在列表中插入顶点的标记

        然后重复1和2，直到所有顶点都从图中删除，这时候列表显示的顶点顺序就是拓扑排序的结果了。

        但是我们需要考虑一种特殊的有向图：环。即A->B->C->D->A。这种必然会导致找不着“没有后继的节点”，这样便无法使用拓扑排序了。

        下面我们分析下拓扑排序的代码：

[java] view plain copy

 

  1. public void poto() {  
  2.     int orig_nVerts = nVerts; //记录有多少个顶点  
  3.     while(nVerts > 0) {  
  4.         //返回没有后继顶点的顶点  
  5.         int currentVertex = noSuccessors(); //如果不存在这样的顶点，返回-1  
  6.         if(currentVertex == -1) {  
  7.             System.out.println("ERROR: Graph has cycles!");  
  8.             return;  
  9.         }  
  10.           
  11.         //sortedArray中存储排过序的顶点（从尾开始存）  
  12.         sortedArray[nVerts-1] = vertexArray[currentVertex].label;  
  13.         deleteVertex(currentVertex);//删除该顶点，便于下一次循环，寻找下一个没有后继顶点的顶点  
  14.     }  
  15.     System.out.println("Topologically sorted order:");  
  16.     for(int i = 0; i < orig_nVerts; i++) {  
  17.         System.out.print(sortedArray[i]);  
  18.     }  
  19.     System.out.println("");  
  20. }  

        主要的工作在while循环中进行，这个循环直到定点数为0时才退出：
        1. 调用noSuccessors()找到任意一个没有后继的顶点；

        2. 如果找到一个这样的顶点，把顶点放到sortedArray数组中，并且从图中删除这个顶点；

        3. 如果不存在这样的顶点，则图必然存在环。

        最后sortedArray数组中存储的就是排过序的顶点了。下面我们分析下noSuccessor()方法和deleteVertes()方法：

[java] view plain copy

 

  1. //return vertex with no successors  
  2. private int noSuccessors() {  
  3.     boolean isEdge;  
  4.     for(int row = 0; row < nVerts; row++) {  
  5.         isEdge = false;  
  6.         for(int col = 0; col < nVerts; col++) {  
  7.             if(adjMat[row][col] > 0) { //只要adjMat数组中存储了1，表示row->col  
  8.                 isEdge = true;  
  9.                 break;  
  10.             }  
  11.         }  
  12.         if(!isEdge) {//只要有边，返回最后一个顶点  
  13.             return row;  
  14.         }  
  15.     }  
  16.     return -1;  
  17. }  
  18.   
  19. private void deleteVertex(int delVertex) {  
  20.     if(delVertex != nVerts -1) {  
  21.         for(int i = delVertex; i < nVerts-1; i++) { //delete from vertexArray  
  22.             vertexArray[i] = vertexArray[i+1];  
  23.         }  
  24.         //删除adjMat中相应的边  
  25.         for(int row = delVertex; row < nVerts-1; row++) {//delete row from adjMat  
  26.             moveRowUp(row, nVerts);  
  27.         }  
  28.           
  29.         for(int col = delVertex; col < nVerts-1; col++) {//delete column from adjMat  
  30.             moveColLeft(col, nVerts-1);  
  31.         }  
  32.     }  
  33.     nVerts--;  
  34. }  

        从上面代码可以看出，删除一个顶点很简单，从vertexArray中删除，后面的顶点向前移动填补空位。同样的，顶点的行列从邻接矩阵中删除，下面的行和右面的列移动来填补空位。删除adjMat数组中的边比较简单，下面看看moveRowUp和moveColLeft的方法：

[java] view plain copy

 

  1. private void moveRowUp(int row, int length) {  
  2.     for(int col = 0; col < length; col++) {  
  3.         adjMat[row][col] = adjMat[row+1][col];  
  4.     }  
  5. }  
  6.   
  7. private void moveColLeft(int col, int length) {  
  8.     for(int row = 0; row < length; row++) {  
  9.         adjMat[row][col] = adjMat[row][col+1];  
  10.     }  
  11. }  

        这样便介绍完了拓扑排序的所有过程了。下面附上完整的代码：

[java] view plain copy

 

  1. package graph;  
  2. /** 
  3.  * 有向图的拓扑排序： 
  4.  * 拓扑排序是可以用图模拟的另一种操作，它可以用于表示一种情况，即某些项目或事件必须按特定的顺序排列或发生。 
  5.  * 有向图和无向图的区别是：有向图的边在邻接矩阵中只有一项。 
  6.  * 拓扑排序算法的思想虽然不寻常但是很简单，有两个步骤是必须的： 
  7.  * 1. 找到一个没有后继的顶点 
  8.  * 2. 从图中删除这个顶点，在列表的前面插入顶点的标记 
  9.  * 重复这两个步骤，直到所有顶点都从图中删除，这时，列表显示的顶点顺序就是拓扑排序的结果。 
  10.  * 删除顶点似乎是一个极端的步骤，但是它是算法的核心，如果第一个顶点不处理，算法就不能计算出要处理的第二个顶点。 
  11.  * 如果需要，可以再其他地方存储图的数据(顶点列表或者邻接矩阵)，然后在排序完成后恢复它们。 
  12.  * @author eson_15 
  13.  * @date 2016-4-20 12:16:11 
  14.  *  
  15.  */  
  16. public class TopoSorted {  
  17.     private final int MAX_VERTS = 20;  
  18.     private Vertex vertexArray[]; //存储顶点的数组  
  19.     private int adjMat[][]; //存储是否有边界的矩阵数组, 0表示没有边界，1表示有边界  
  20.     private int nVerts; //顶点个数  
  21.     private char sortedArray[]; //存储排过序的数据的数组  
  22.       
  23.     public TopoSorted() {  
  24.         vertexArray = new Vertex[MAX_VERTS];  
  25.         adjMat = new int[MAX_VERTS][MAX_VERTS];  
  26.         nVerts = 0;  
  27.         for(int i = 0; i < MAX_VERTS; i++) {  
  28.             for(int j = 0; j < MAX_VERTS; j++) {  
  29.                 adjMat[i][j] = 0;  
  30.             }  
  31.         }  
  32.         sortedArray = new char[MAX_VERTS];  
  33.     }  
  34.       
  35.     public void addVertex(char lab) {  
  36.         vertexArray[nVerts++] = new Vertex(lab);  
  37.     }  
  38.       
  39.     //有向图中，邻接矩阵中只有一项  
  40.     public void addEdge(int start, int end) {  
  41.         adjMat[start][end] = 1;  
  42.     }  
  43.       
  44.     public void displayVertex(int v) {  
  45.         System.out.print(vertexArray[v].label);  
  46.     }  
  47.       
  48.     /* 
  49.      * 拓扑排序 
  50.      */  
  51.     public void poto() {  
  52.         int orig_nVerts = nVerts; //remember how many verts  
  53.         while(nVerts > 0) {  
  54.             //get a vertex with no successors or -1  
  55.             int currentVertex = noSuccessors();  
  56.             if(currentVertex == -1) {  
  57.                 System.out.println("ERROR: Graph has cycles!");  
  58.                 return;  
  59.             }  
  60.               
  61.             //insert vertex label in sortedArray (start at end)  
  62.             sortedArray[nVerts-1] = vertexArray[currentVertex].label;  
  63.             deleteVertex(currentVertex);  
  64.         }  
  65.         System.out.println("Topologically sorted order:");  
  66.         for(int i = 0; i < orig_nVerts; i++) {  
  67.             System.out.print(sortedArray[i]);  
  68.         }  
  69.         System.out.println("");  
  70.     }  
  71.   
  72.     //return vertex with no successors  
  73.     private int noSuccessors() {  
  74.         boolean isEdge;  
  75.         for(int row = 0; row < nVerts; row++) {  
  76.             isEdge = false;  
  77.             for(int col = 0; col < nVerts; col++) {  
  78.                 if(adjMat[row][col] > 0) {  
  79.                     isEdge = true;  
  80.                     break;  
  81.                 }  
  82.             }  
  83.             if(!isEdge) {  
  84.                 return row;  
  85.             }  
  86.         }  
  87.         return -1;  
  88.     }  
  89.   
  90.     private void deleteVertex(int delVertex) {  
  91.         if(delVertex != nVerts -1) {  
  92.             for(int i = delVertex; i < nVerts-1; i++) { //delete from vertexArray  
  93.                 vertexArray[i] = vertexArray[i+1];  
  94.             }  
  95.               
  96.             for(int row = delVertex; row < nVerts-1; row++) {//delete row from adjMat  
  97.                 moveRowUp(row, nVerts);  
  98.             }  
  99.               
  100.             for(int col = delVertex; col < nVerts-1; col++) {//delete column from adjMat  
  101.                 moveColLeft(col, nVerts-1);  
  102.             }  
  103.         }  
  104.         nVerts--;  
  105.     }  
  106.   
  107.     private void moveRowUp(int row, int length) {  
  108.         for(int col = 0; col < length; col++) {  
  109.             adjMat[row][col] = adjMat[row+1][col];  
  110.         }  
  111.     }  
  112.   
  113.     private void moveColLeft(int col, int length) {  
  114.         for(int row = 0; row < length; row++) {  
  115.             adjMat[row][col] = adjMat[row][col+1];  
  116.         }  
  117.     }  
  118. }  

        拓扑排序就介绍到这吧，如有错误之处，欢迎留言指正~

转载：http://blog.csdn.net/eson_15/article/details/51194219

时间： 2024-09-20 20:01:05

数据结构和算法17 之拓扑排序的相关文章

算法起步之拓扑排序

原文:算法起步之拓扑排序         拓扑排序是图中所有节点的一种线性次序,首先拓扑排序是对有向无环图来说的,如果不满足这个条件则无法拓扑排序,拓扑排序就是遵循一定的规则对节点的排序,规则就是假设在图中有一条边是从a节点出发指向b节点,则在拓扑排序中b节点不可能排在a的前面.其实就是一直寻找入度为0的节点.我们也可以理解成b的完成必须依赖a的完成,a没有完成则b无法进行,其实这样理解的话我们先前说的线性规划也是一种拓扑排序,像我们平时的起床过程也是一种拓扑排序.          拓扑排序的

数据结构和算法15 之二叉树排序

 顾名思义,二叉树排序就是利用二叉搜索树的特点进行排序,前面提到过二叉搜索树的特点是,左子节点比自己小,右子节点比自己大,那么二叉树排序的思想就是先将待排序序列逐个添加到二叉搜索树中去,再通过中序遍历二叉搜索树就可以将数据从小到大取出来.如果对二叉树还不太了解,请看这篇博文:数据结构和算法之二叉树 ,这里不再赘述. 下面我们来看看二叉树排序的实现: [java] view plain copy   public class Tree2Sort {       private Node root;

数据结构和算法11 之基础排序

前10节我们学习了一些经典的数据结构,从这节开始,我们将学习一些排序算法.这一节我们先学习几个基础排序算法:冒泡排序,选择排序和插入排序. 1. 冒泡排序         冒泡排序算法运行起来非常慢,但在概念上它是排序算法中最简单的,因此冒泡排序算法在刚开始研究排序技术时是一个非常好的算法.冒泡排序算法的基本流程是:每一轮从头开始两两比较,将较大的项放在较小项的右边,这样每轮下来保证该轮最大的数在最右边. 算法程序如下: [java] view plain copy   public void 

数据结构与算法C#版笔记--排序(Sort)-下

5.堆排序(HeapSort) 在接触"堆排序"前,先回顾一下数据结构C#版笔记--树与二叉树 ,其中提到了"完全二叉树"有一些重要的数学特性: 上图就是一颗完全二叉树,如果每个节点按从上到下,从左至右标上序号,则可以用数组来实现顺性存储,同时其序号: 1.如果i>1,则序号为i的父结节序号为i/2(这里/指整除) 言外之意:整个数组前一半都是父节点,后一半则是叶节点 2.如果2*i<=n(这里n为整颗树的节点总数),则序号为i的左子节点序号为2*i 3

Java数据结构及算法实例：选择排序 Selection Sort_java

/** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

数据结构和算法12 之希尔排序

 上一章我们学习了冒泡排序.选择排序和插入排序三种基础排序算法,这三种排序算法比较简单,时间复杂度均为O(N2),效率不高.这节我们讨论一个高级排序算法:希尔排序.希尔排序是基于插入排序的,插入排序有个弊端,假设一个很小的数据项在很靠近右端的位置上,那么所有的中间数据项都必须向右移动一位,这个步骤对每一个数据项都执行了将近N次的复制,这也是插入排序效率为O(N2)的原因.         希尔排序的中心思想是将数据进行分组,然后对每一组数据进行插入排序,在每一组数据都有序后,再对所有的分组利用插

数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序) 注:排序后的结果可以从小到大,或者从大到小,这只是一个相反的处理而已,为方便起见,本文中的方法都是从小到大排序 1.直接插入排序(InsertOrder) 思路:从第二个元素开始向后遍历,检查本身(后面称之为tmp)与前面相邻元素的大小,如果发现前面的元素更大,则依次从近及远(即倒序遍历)检查前面的所有元素,将比自身元素大的元素依次后移,这样最终将得到一个空位,

图的遍历、拓扑排序、最短路径算法

1.DFS(深度优先搜索) 深度优先搜索算法(Depth-First-Search),是搜索算法的一种.它沿着树的深度遍历树的节点,尽可能深的搜索树的分支.当节点v的所有边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点.这一过程一直进行到已发现从源节点可达的所有节点为止.如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止.DFS 属于盲目搜索. 深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的相应拓扑排序表,利用

数据结构例程——拓扑排序

本文是[数据结构基础系列(7):图]中第11课时[拓扑排序]的例程. (程序中graph.h是图存储结构的"算法库"中的头文件,详情请单击链接-) [代码] #include <stdio.h> #include <malloc.h> #include "graph.h" void TopSort(ALGraph *G) { int i,j; int St[MAXV],top=-1; //栈St的指针为top ArcNode *p; for