当前位置:   article > 正文

(Java)数据结构——图(第九节)AOV网以及拓扑排序

(Java)数据结构——图(第九节)AOV网以及拓扑排序

前言

本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。

AOV网

先前我们了解了有向无环图DAG的概念。

所有的工程或者某种流程可以分为若干个小的工程或者阶段,这些小的工程或者阶段就称为活动。若以图中的顶点来表示活动,有向边表示活动之间的优先关系,则这样活动在顶点上的有向图,就称为AOV图(Activity On Vertex Network)。

与AOE网的区别就是:AOE的边是活动(Activity On Edge Network),要不是今天看了下书,我就记混了。

AOV网主要是看工程是否能够顺利进行(拓扑排序判断DAG图,或者其他也行,比如DFS再次碰见isVisited[N] = true等等),AOE则是主要看工程完成所必须的最短时间(关键路径)。

拓扑排序代码实现

原理:找入度为0的,加入栈,然后出栈,遍历它的“链表”,链表里有的结点入度-1,归0后加入栈,依次往复。直到栈里空了,判断一下是不是都遍历了,或者计数也行。都遍历了就是DAG,没遍历完就不是。

517e6de033cd4ab5ad362d8753852312.jpeg

可以看我的另一篇博客,或者直接看实现。

LeetCode 207.课程表——拓扑排序&真真切切建图实现-CSDN博客

应该是没问题的实现(如果出问题,就是搬自己LeetCode时候有的变量名没改)。

  1. package GraphTest.Demo;
  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.LinkedList;
  5. import java.util.Scanner;
  6. class Test {
  7. public boolean canFinish(int numCourses, int[][] prerequisites) {
  8. Graph graph = new Graph(numCourses);
  9. for(int i = 0;i<prerequisites.length;i++){
  10. //插入结点
  11. graph.insertEdge(prerequisites[i][0],prerequisites[i][1],1);
  12. }
  13. return graph.tuopu();
  14. }
  15. public static void main(String[] args) {
  16. //主要是接收数据麻烦点,其他没啥
  17. Scanner in = new Scanner(System.in);
  18. int numCourses = Integer.parseInt(in.nextLine());
  19. String[] str = in.nextLine().replaceAll("\\[","").replaceAll("]","").split(",");
  20. int n = str.length / 2;
  21. int[][] prerequisites = new int[n][2];
  22. for(int i = 0;i<n;i++){
  23. prerequisites[i][0] = Integer.parseInt(str[2*i]);
  24. prerequisites[i][1] = Integer.parseInt(str[2*i+1]);
  25. System.out.println(prerequisites[i][0]+" "+prerequisites[i][1]);
  26. }
  27. System.out.println(canFinish(numCourses,prerequisites));
  28. }
  29. }
  30. class InData{
  31. int in;
  32. int vertex;
  33. ArrayList<Integer> next = new ArrayList<>();
  34. InData(int vertex){
  35. this.in = 0;
  36. this.vertex = vertex;
  37. }
  38. }
  39. class Graph{
  40. int[][] edges; //边集合
  41. //ArrayList<Integer> vertexList = new ArrayList<>();
  42. //点集合,在这因为没有名称,都是下标,所以不用这个变量
  43. int numOfEdges;
  44. InData[] inData;
  45. boolean[] isVisited;
  46. Graph(int N){
  47. this.edges = new int[N][N];
  48. /*for(int i =0;i<N;i++){
  49. Arrays.fill(edges[i],Integer.MAX_VALUE);
  50. }
  51. 然后我之前一弄是54ms,发现是写了好多个打印,一删掉就掉到了13ms
  52. 然后我又发现把这个注释了就从13ms掉到了7ms
  53. */
  54. this.numOfEdges = 0;
  55. this.inData = new InData[N];
  56. for(int i = 0;i<N;i++){
  57. inData[i] = new InData(i);
  58. }
  59. /*for(int i = 0;i<N;i++){
  60. vertexList.add(i);
  61. }*/
  62. this.isVisited = new boolean[N];
  63. }
  64. public void insertEdge(int v1,int v2,int weight){
  65. this.edges[v1][v2] = weight;
  66. this.inData[v1].next.add(v2);
  67. this.inData[v2].in++;
  68. }
  69. public boolean tuopu(){//拓扑排序——判断是否能生成一个时间有序的序列
  70. //一开始我们已经在图中初始化顶点个数个InData类型组成数组,现在我们把他们拷贝过来
  71. LinkedList<InData> stack = new LinkedList<>();
  72. InData[] list = new InData[isVisited.length];
  73. for(int i = 0;i<list.length;i++){
  74. list[i] = inData[i];
  75. if(list[i].in == 0){//如果发现入度为0就加入栈中
  76. stack.addFirst(list[i]);
  77. this.isVisited[i] = true; //进入栈中的置为已经遍历过
  78. }
  79. }
  80. while(!stack.isEmpty()){
  81. //得到“邻接表”
  82. ArrayList<Integer> temp = stack.removeFirst().next;
  83. for(int i:temp){
  84. //list对应位置的入度-1
  85. list[i].in--;
  86. if(list[i].in == 0){
  87. //如果对应位置的入度在此刻变成0的话,加入栈中
  88. stack.addFirst(list[i]);
  89. this.isVisited[i] = true;
  90. }
  91. }
  92. }
  93. //之后进行判断,如果存在没有遍历过的,直接返回false不能生成
  94. for(int i = 0;i<isVisited.length;i++){
  95. if(!isVisited[i]){
  96. return false;
  97. }
  98. }
  99. return true;
  100. }
  101. }

 

 

声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号