`
yanfaguanli
  • 浏览: 660781 次
文章分类
社区版块
存档分类
最新评论

拓扑排序(Topologicalsort)之Java实现

 
阅读更多

目录(?)[+]

拓扑排序算法介绍

拓扑排序解决的是一系列相互依赖的事件的排序问题，比如Ant中有很多的Task，而某些Task依赖于另外的Task，编译之前需要清理空间，打包之前要先编译，但其它一些Task处理顺序可以调换(是无所谓前后，不是并行), 如何安排Task的执行顺序就可以用拓扑排序解决。熟悉Java的朋友应该都知道Spring，一个非常优秀的解决组件(Bean)依赖的框架，组件之间可能有依赖关系，也可能没有关系，如何按顺序创建组件也是相同的问题。本文使用的是图搜索算法里面的深度优先排序算法解决问题。需要特别指出的是拓扑排序算法的结果很可能有多个(不依赖的可以调换位置)，而算法也可以有多种，深度优先排序算法只是其中一种而已。拓扑排序为线性排序，效率为O(|V|+|E|)，其中|V|表示顶点数，|E|表示边的数量。

拓扑排序算法Java实现


图像(Graph)的Java抽象实现

图可以抽象为顶点和边，分为有向图和无向图，拓扑排序里面使用的事有向图(依赖)，本文中图的边用相邻链表方法表示。每一个顶点有名字(name)，颜色(color, 搜索时候用来标记处理状态)，父节点(parent，搜索结束可以得到多棵树)，开始处理时间(discover)，结束处理时间(finish)。请注意Vertex类override了equals和hash方法。具体代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. enumColor{
  2. WHITE,GRAY,BLACK
  3. }
  5. staticclassVertex{
  6. privateStringname;
  7. privateColorcolor;
  8. privateVertexparent;
  9. privateintdiscover;
  10. privateintfinish;
  12. publicVertex(Stringname){
  13. this.name=name;
  14. this.color=Color.WHITE;
  15. }
  17. publicStringgetName(){
  18. returnname;
  19. }
  21. publicvoidsetName(Stringname){
  22. this.name=name;
  23. }
  25. publicColorgetColor(){
  26. returncolor;
  27. }
  29. publicvoidsetColor(Colorcolor){
  30. this.color=color;
  31. }
  33. publicVertexgetParent(){
  34. returnparent;
  35. }
  37. publicvoidsetParent(Vertexparent){
  38. this.parent=parent;
  39. }
  41. publicintgetDiscover(){
  42. returndiscover;
  43. }
  45. publicvoidsetDiscover(intdiscover){
  46. this.discover=discover;
  47. }
  49. publicintgetFinish(){
  50. returnfinish;
  51. }
  53. publicvoidsetFinish(intfinish){
  54. this.finish=finish;
  55. }
  57. @Override
  58. publicinthashCode(){
  59. finalintprime=31;
  60. intresult=1;
  61. result=prime*result+((name==null)?0:name.hashCode());
  62. returnresult;
  63. }
  65. @Override
  66. publicbooleanequals(Objectobj){
  67. if(this==obj)
  68. returntrue;
  69. if(obj==null)
  70. returnfalse;
  71. if(getClass()!=obj.getClass())
  72. returnfalse;
  73. Vertexother=(Vertex)obj;
  74. if(name==null){
  75. if(other.name!=null)
  76. returnfalse;
  77. }elseif(!name.equals(other.name))
  78. returnfalse;
  79. returntrue;
  80. }
  81. }
  83. staticclassGraph{
  84. privateSet<Vertex>vertexSet=newHashSet<Vertex>();
  85. //相邻的节点
  86. privateMap<Vertex,Vertex[]>adjacencys=newHashMap<Vertex,Vertex[]>();
  88. publicSet<Vertex>getVertexSet(){
  89. returnvertexSet;
  90. }
  92. publicvoidsetVertexSet(Set<Vertex>vertexSet){
  93. this.vertexSet=vertexSet;
  94. }
  96. publicMap<Vertex,Vertex[]>getAdjacencys(){
  97. returnadjacencys;
  98. }
  100. publicvoidsetAdjacencys(Map<Vertex,Vertex[]>adjacencys){
  101. this.adjacencys=adjacencys;
  102. }
  103. }

深度优先算法

遍历图的顶点，如果当前顶点还没有处理过(color为white)，就处理该节点(visitVertex)，处理节点的算法(visitVertex)也不难，时间维度加1，当前节点颜色置为gray(开始处理)，然后优先处理其子节点(深度优先)，结束之后时间维度加1，当前节点颜色置为black(结束处理)。此时就可以把该节点放到目标链表里面了(最终排好序的链表)。由于Java里面Integer值不可变(Immutable)，只能选择全局变量或者自己实现时间计数器，本文选择后者(TimeRecorder)。代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. staticclassTimeRecorder{
  2. privateinttime=0;
  4. publicintgetTime(){
  5. returntime;
  6. }
  8. publicvoidsetTime(inttime){
  9. this.time=time;
  10. }
  11. }
  13. publicstaticVertex[]topologicalSort(Graphgraph){
  14. Set<Vertex>vertexSet=graph.getVertexSet();
  15. if(vertexSet.size()<2){
  16. returnvertexSet.toArray(newVertex[0]);
  17. }
  19. LinkedList<Vertex>sortedList=newLinkedList<Vertex>();
  20. TimeRecorderrecorder=newTimeRecorder();
  22. for(Vertexvertex:vertexSet){
  23. if(vertex.color==Color.WHITE){
  24. visitVertex(graph,vertex,recorder,sortedList);
  25. }
  26. }
  28. returnsortedList.toArray(newVertex[0]);
  29. }
  31. /**
  32. *深度优先搜索(DepthFirstSearch)
  33. */
  34. publicstaticvoidvisitVertex(Graphgraph,Vertexvertex,
  35. TimeRecorderrecorder,LinkedList<Vertex>sortedList){
  36. recorder.time+=1;
  37. vertex.color=Color.GRAY;
  38. vertex.discover=recorder.time;
  40. Map<Vertex,Vertex[]>edgeMap=graph.getAdjacencys();
  41. Vertex[]adjacencys=edgeMap.get(vertex);
  42. if(adjacencys!=null&&adjacencys.length>0){
  43. for(Vertexadjacency:adjacencys){
  44. if(adjacency.color==Color.WHITE){
  45. adjacency.parent=vertex;
  46. visitVertex(graph,adjacency,recorder,sortedList);
  47. }
  48. }
  49. }
  51. recorder.time+=1;
  52. vertex.color=Color.BLACK;
  53. vertex.finish=recorder.time;
  54. sortedList.addLast(vertex);
  55. }

构建图以及测试

我们的测试图例如下(箭头的方向表示的是依赖):


为了打印排好序的结果，实现了printVertex函数。测试代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. publicstaticvoidmain(String[]args){
  2. Graphgraph=newGraph();
  3. Set<Vertex>vertexSet=graph.getVertexSet();
  4. Map<Vertex,Vertex[]>edgeMap=graph.getAdjacencys();
  6. VertextwoVertex=newVertex("2");
  7. VertexthreeVertex=newVertex("3");
  8. VertexfiveVertex=newVertex("5");
  9. VertexsevenVertex=newVertex("7");
  10. VertexeightVertex=newVertex("8");
  11. VertexnineVertex=newVertex("9");
  12. VertextenVertex=newVertex("10");
  13. VertexelevenVertex=newVertex("11");
  15. vertexSet.add(twoVertex);
  16. vertexSet.add(threeVertex);
  17. vertexSet.add(fiveVertex);
  18. vertexSet.add(sevenVertex);
  19. vertexSet.add(eightVertex);
  20. vertexSet.add(nineVertex);
  21. vertexSet.add(tenVertex);
  22. vertexSet.add(elevenVertex);
  24. edgeMap.put(twoVertex,newVertex[]{elevenVertex});
  25. edgeMap.put(nineVertex,newVertex[]{elevenVertex,eightVertex});
  26. edgeMap.put(tenVertex,newVertex[]{elevenVertex,threeVertex});
  27. edgeMap.put(elevenVertex,newVertex[]{sevenVertex,fiveVertex});
  28. edgeMap.put(eightVertex,newVertex[]{sevenVertex,threeVertex});
  30. Vertex[]sortedVertexs=topologicalSort(graph);
  31. printVertex(sortedVertexs);
  32. }
  34. publicstaticvoidprintVertex(Vertex[]Vertexs){
  35. for(Vertexvertex:Vertexs){
  36. System.out.println(vertex.getName()+"discovertime:"
  37. +vertex.getDiscover()+"finishtime:"
  38. +vertex.getFinish());
  39. }
  40. }

后记

以上Java实现参考的是算法导论的深度优先排序算法。如果想对排序的精确度有更好的控制，可以在Vertex类中加一个priority属性。每一次遍历之前都针对顶点以priority即可。参考链接:维基百科

拓扑排序算法介绍

拓扑排序解决的是一系列相互依赖的事件的排序问题，比如Ant中有很多的Task，而某些Task依赖于另外的Task，编译之前需要清理空间，打包之前要先编译，但其它一些Task处理顺序可以调换(是无所谓前后，不是并行), 如何安排Task的执行顺序就可以用拓扑排序解决。熟悉Java的朋友应该都知道Spring，一个非常优秀的解决组件(Bean)依赖的框架，组件之间可能有依赖关系，也可能没有关系，如何按顺序创建组件也是相同的问题。本文使用的是图搜索算法里面的深度优先排序算法解决问题。需要特别指出的是拓扑排序算法的结果很可能有多个(不依赖的可以调换位置)，而算法也可以有多种，深度优先排序算法只是其中一种而已。拓扑排序为线性排序，效率为O(|V|+|E|)，其中|V|表示顶点数，|E|表示边的数量。

拓扑排序算法Java实现


图像(Graph)的Java抽象实现

图可以抽象为顶点和边，分为有向图和无向图，拓扑排序里面使用的事有向图(依赖)，本文中图的边用相邻链表方法表示。每一个顶点有名字(name)，颜色(color, 搜索时候用来标记处理状态)，父节点(parent，搜索结束可以得到多棵树)，开始处理时间(discover)，结束处理时间(finish)。请注意Vertex类override了equals和hash方法。具体代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. enumColor{
  2. WHITE,GRAY,BLACK
  3. }
  5. staticclassVertex{
  6. privateStringname;
  7. privateColorcolor;
  8. privateVertexparent;
  9. privateintdiscover;
  10. privateintfinish;
  12. publicVertex(Stringname){
  13. this.name=name;
  14. this.color=Color.WHITE;
  15. }
  17. publicStringgetName(){
  18. returnname;
  19. }
  21. publicvoidsetName(Stringname){
  22. this.name=name;
  23. }
  25. publicColorgetColor(){
  26. returncolor;
  27. }
  29. publicvoidsetColor(Colorcolor){
  30. this.color=color;
  31. }
  33. publicVertexgetParent(){
  34. returnparent;
  35. }
  37. publicvoidsetParent(Vertexparent){
  38. this.parent=parent;
  39. }
  41. publicintgetDiscover(){
  42. returndiscover;
  43. }
  45. publicvoidsetDiscover(intdiscover){
  46. this.discover=discover;
  47. }
  49. publicintgetFinish(){
  50. returnfinish;
  51. }
  53. publicvoidsetFinish(intfinish){
  54. this.finish=finish;
  55. }
  57. @Override
  58. publicinthashCode(){
  59. finalintprime=31;
  60. intresult=1;
  61. result=prime*result+((name==null)?0:name.hashCode());
  62. returnresult;
  63. }
  65. @Override
  66. publicbooleanequals(Objectobj){
  67. if(this==obj)
  68. returntrue;
  69. if(obj==null)
  70. returnfalse;
  71. if(getClass()!=obj.getClass())
  72. returnfalse;
  73. Vertexother=(Vertex)obj;
  74. if(name==null){
  75. if(other.name!=null)
  76. returnfalse;
  77. }elseif(!name.equals(other.name))
  78. returnfalse;
  79. returntrue;
  80. }
  81. }
  83. staticclassGraph{
  84. privateSet<Vertex>vertexSet=newHashSet<Vertex>();
  85. //相邻的节点
  86. privateMap<Vertex,Vertex[]>adjacencys=newHashMap<Vertex,Vertex[]>();
  88. publicSet<Vertex>getVertexSet(){
  89. returnvertexSet;
  90. }
  92. publicvoidsetVertexSet(Set<Vertex>vertexSet){
  93. this.vertexSet=vertexSet;
  94. }
  96. publicMap<Vertex,Vertex[]>getAdjacencys(){
  97. returnadjacencys;
  98. }
  100. publicvoidsetAdjacencys(Map<Vertex,Vertex[]>adjacencys){
  101. this.adjacencys=adjacencys;
  102. }
  103. }

深度优先算法

遍历图的顶点，如果当前顶点还没有处理过(color为white)，就处理该节点(visitVertex)，处理节点的算法(visitVertex)也不难，时间维度加1，当前节点颜色置为gray(开始处理)，然后优先处理其子节点(深度优先)，结束之后时间维度加1，当前节点颜色置为black(结束处理)。此时就可以把该节点放到目标链表里面了(最终排好序的链表)。由于Java里面Integer值不可变(Immutable)，只能选择全局变量或者自己实现时间计数器，本文选择后者(TimeRecorder)。代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. staticclassTimeRecorder{
  2. privateinttime=0;
  4. publicintgetTime(){
  5. returntime;
  6. }
  8. publicvoidsetTime(inttime){
  9. this.time=time;
  10. }
  11. }
  13. publicstaticVertex[]topologicalSort(Graphgraph){
  14. Set<Vertex>vertexSet=graph.getVertexSet();
  15. if(vertexSet.size()<2){
  16. returnvertexSet.toArray(newVertex[0]);
  17. }
  19. LinkedList<Vertex>sortedList=newLinkedList<Vertex>();
  20. TimeRecorderrecorder=newTimeRecorder();
  22. for(Vertexvertex:vertexSet){
  23. if(vertex.color==Color.WHITE){
  24. visitVertex(graph,vertex,recorder,sortedList);
  25. }
  26. }
  28. returnsortedList.toArray(newVertex[0]);
  29. }
  31. /**
  32. *深度优先搜索(DepthFirstSearch)
  33. */
  34. publicstaticvoidvisitVertex(Graphgraph,Vertexvertex,
  35. TimeRecorderrecorder,LinkedList<Vertex>sortedList){
  36. recorder.time+=1;
  37. vertex.color=Color.GRAY;
  38. vertex.discover=recorder.time;
  40. Map<Vertex,Vertex[]>edgeMap=graph.getAdjacencys();
  41. Vertex[]adjacencys=edgeMap.get(vertex);
  42. if(adjacencys!=null&&adjacencys.length>0){
  43. for(Vertexadjacency:adjacencys){
  44. if(adjacency.color==Color.WHITE){
  45. adjacency.parent=vertex;
  46. visitVertex(graph,adjacency,recorder,sortedList);
  47. }
  48. }
  49. }
  51. recorder.time+=1;
  52. vertex.color=Color.BLACK;
  53. vertex.finish=recorder.time;
  54. sortedList.addLast(vertex);
  55. }

构建图以及测试

我们的测试图例如下(箭头的方向表示的是依赖):


为了打印排好序的结果，实现了printVertex函数。测试代码如下:

[java] view plaincopy在CODE上查看代码片派生到我的代码片
  1. publicstaticvoidmain(String[]args){
  2. Graphgraph=newGraph();
  3. Set<Vertex>vertexSet=graph.getVertexSet();
  4. Map<Vertex,Vertex[]>edgeMap=graph.getAdjacencys();
  6. VertextwoVertex=newVertex("2");
  7. VertexthreeVertex=newVertex("3");
  8. VertexfiveVertex=newVertex("5");
  9. VertexsevenVertex=newVertex("7");
  10. VertexeightVertex=newVertex("8");
  11. VertexnineVertex=newVertex("9");
  12. VertextenVertex=newVertex("10");
  13. VertexelevenVertex=newVertex("11");
  15. vertexSet.add(twoVertex);
  16. vertexSet.add(threeVertex);
  17. vertexSet.add(fiveVertex);
  18. vertexSet.add(sevenVertex);
  19. vertexSet.add(eightVertex);
  20. vertexSet.add(nineVertex);
  21. vertexSet.add(tenVertex);
  22. vertexSet.add(elevenVertex);
  24. edgeMap.put(twoVertex,newVertex[]{elevenVertex});
  25. edgeMap.put(nineVertex,newVertex[]{elevenVertex,eightVertex});
  26. edgeMap.put(tenVertex,newVertex[]{elevenVertex,threeVertex});
  27. edgeMap.put(elevenVertex,newVertex[]{sevenVertex,fiveVertex});
  28. edgeMap.put(eightVertex,newVertex[]{sevenVertex,threeVertex});
  30. Vertex[]sortedVertexs=topologicalSort(graph);
  31. printVertex(sortedVertexs);
  32. }
  34. publicstaticvoidprintVertex(Vertex[]Vertexs){
  35. for(Vertexvertex:Vertexs){
  36. System.out.println(vertex.getName()+"discovertime:"
  37. +vertex.getDiscover()+"finishtime:"
  38. +vertex.getFinish());
  39. }
  40. }

后记

以上Java实现参考的是算法导论的深度优先排序算法。如果想对排序的精确度有更好的控制，可以在Vertex类中加一个priority属性。每一次遍历之前都针对顶点以priority即可。参考链接:维基百科

分享到：
| 堆排序(Heapsort)之Java实现
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    拓扑排序 Topological Sorting 两种实现

    拓扑排序的两种实现

    tuopupaixu.rar_topological sort_tuopupaixu_拓扑_拓扑 图_拓扑排序

    拓扑排序，简单地说，是由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或是一个数据...

    c++实现拓扑排序

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现...本程序自己手动输入图的节点，实现拓扑排序。

    matlab开发-Topologicalsort

    matlab开发-Topologicalsort。执行有向图的拓扑排序

    拓扑排序--课程表

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v...简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

    Java实现-Topological Graphing

    Implement the pseudocode presented in the lecture for both creating a graph and for topological sort. Put each algorithm into a separate function. Construct a data structure to store a graph, which ...

    邻接矩阵的拓扑排序

    从文本文件中读取邻接矩阵，通过减一治的方法实现拓扑排序

    ACM拓扑排序（可输出环）

    假设给我们一个任意的图，它可能是也可能不是DAG（有向无圈图），推广拓扑排序算法，以使得给定有向图G的输入，它的输出是以下两者之一： (a) 一个拓扑排序，于是确定了G为DAG； 或者 (b) G中的一个圈，于是确定了G...

    TopologicalSort:用于对一组部分排序的元素进行排序的java程序

    项目描述 Java程序，对一组部分排序的元素进行。 程序使用Kahn的算法，该算法也在Wiki页面上进行了讨论。 项目特色 通过命令行从文件读取输入。... 如果无法进行拓扑排序，则输出消息图形包含循环。

    ACM拓扑排序

    假设给我们一个任意的图，它可能是也可能不是DAG（有向无圈图），推广拓扑排序算法，以使得给定有向图G的输入，它的输出是以下两者之一： (a) 一个拓扑排序，于是确定了G为DAG； 或者 (b) G中的一个圈，于是确定了G...

    toplogical_sort.rar_topological sorting_拓扑_数据结构 图_数据结构 拓扑排序

    这是一个图的拓扑排序的程序，是数据结构的图一章中比较重要的内容，程序已经调试通过，可以供大家参考

    拓扑排序（算法与数据结构课程设计）

    在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后...拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现

    topological-sort:使用拓扑排序对依赖项进行排序

    拓扑排序 排序依赖项 import topological from '../index.js' ;let items = [{ name : 'jquery-plugin1' , src : 'jquery-plugin-1.2.1.js' , dep : [ 'jquery' ] } ,{ name : 'jquery' , src : 'jquery-1.6.2.js' ,...

    有向图邻接表的建立，深度广度搜索及拓扑排序.zip_45V_bfs_dfs_有向图

    拓扑排序 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对...简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序

    js-topological-sorting:JavaScript的拓扑排序算法

    JavaScript的拓扑排序算法。 参见 。 :warning: 该代码要求定义regeneratorRuntime ，例如，通过导入 。 // Sort anything that can be iterated over with `for (const [u, v] of ...)` import { sorted } from...

    python实现拓扑排序的基本教程

    对于这种依赖关系，很容易将其表示成一个有向无环图（Directed Acyclic Graph，DAG，无环是一个重要条件），并将寻找其中依赖顺序的过程称为拓扑排序（topological sorting）。 拓扑排序要满足如下两个条件 每个...

    拓扑排序--医院选址

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑...

    09 TopologicalSort.zip

    严蔚敏数据结构与算法▲课本算法实现

    09 TopologicalSort.rar

    严蔚敏数据结构与算法▲课本算法实现

    关键路径课程设计.zip

    主要设计CreateUDG函数创建图的邻接链表，其中通过LocateVex 可以定位到邻接表代表元素的数组下标并进行连接TopologicalSort函数调用链栈对图的所有结点进行拓扑排序的功能，并为计算最晚开始时间做准备， ...

Magicbox
Global site tag (gtag.js) - Google Analytics