拓扑排序例子,拓扑排序应用实例

　　00-1010铺设介绍工作流程数据结构拓扑排序测试样本1测试样本2总结

目录

有向图：这一节我们要讲的算法涉及到有向图，所以我先讲一些有向图的概念，文章后面就不解释了。首先，有向图的节点由带箭头的线连接。节点有度外和度内的概念。指向连接线尾部的节点的出度增加1，指向连接线头部的节点的入度增加1。看下面这个例子：A的入度为0，出度为2，B的入度为1，C的入度为1，出度为1，D的入度为2，出度为0。

　　邻接表：邻接表是存储图结构的有效方法。如下图所示，左边的节点数组存储图中的所有节点，右边的邻接表存储节点的邻居节点。

　　00-1010在本文中，我们要讲的是拓扑排序，这是一种针对有向无环图的算法，主要解决的是前趋-后继关系，也就是完成当前项需要先完成的内容。事实上，这在我们的过程控制中用得很多。看下图。我们需要先完成A项，然后才能完成B项和C项，B项和C项不分先后，但D项需要在B项和C项完成后完成。而拓扑排序可以帮助我们找到这个完成项的合理顺序。同时，我们来看看上面的例子。A项完成后，B项和C项没有顺序，B项和C项都先满足条件，所以拓扑排序的顺序并不完全确定。

　　00-1010首先，拓扑排序对应的是有向无环图。非循环图，必须至少有一个节点的度为0。在目前的情况下，我们需要找到进入度为0的节点进行操作。如果进入度为0，说明当前节点没有前任节点，或者前任节点已经处理过，可以直接操作。操作完成后，当前节点的所有后继节点的渗透度都减1，重新搜索渗透度为0的节点进行操作。之后是一个递归过程，不断处理当前情况下渗透度为0的节点，直到处理完所有节点。

　　00-1010有向图的结构如下，其中node存储当前图包含的所有节点，adj存储对应下标节点的邻点。在初始化图的时候，我们需要初始化图中的节点数，存储节点的数组以及对应的相邻节点的数组。同时提供了一个addEdge方法，用来直接给两个节点添加边。事实上，后继节点被放入前趋节点的邻居列表中。

　　PublicstaticclassGraph{ /** * *节点数*/privateIntegernodeSize；/* * * node */private char[]node；/* * *邻接表*/privateLinkedList[]adj；public graph(char[]node){ this . nodesize=node . length；this.node=nodethis . adj=newLinkedList[nodeSize]；for(inti=0；iadj.lengthI){ adj[I]=newLinkedList()；}}/* * *在节点之间添加一条边，前置节点指向后续节点* @param front前置节点下标* @param end后续节点下标*/publicadddedge(int front，intent) {adj [front]。添加(结束)；} }

　　00-1010拓扑排序首先初始化两个临时数组，一个queue和一个inDegree数组来存储对应下标节点的度，因为每次访问一个节点都需要完成前一个节点，即条目的度为0，所以我们可以用这个数组快速找到这些节点；另一个是已访问数组，标记当前节点是否被访问过，防止多次访问；节点队列保存当前情况下度数为0的所有节点。(注意，为了访问方便，我们都用存储的节点下标step1:初始化了inDegree数组和visited数组；步骤2:遍历度数数组，将度数为0的所有节点放入节点队列；步骤3:依次使节点出列；根据访问过的节点判断当前节点是否被访问过；如果是，返回步骤3；如果否，进行下一步；将当前节点的邻节点度设置为-1，判断邻节点度是否为0，如果为0，则直接放入节点队列，否则返回步骤3；

　　>/**    * @param graph 有向无环图    * @return 拓扑排序结果    */   public List<Character> toPoLogicalSort(Graph graph) {       //用一个数组标志所有节点入度       int[] inDegree = new int[graph.nodeSize];       for (LinkedList list : graph.adj) {           for (Object index : list) {               ++ inDegree[(int)index];          }      }       //用一个数组标志所有节点是否已经被访问       boolean[] visited = new boolean[graph.nodeSize];       //开始进行遍历       Deque<Integer> nodes = new LinkedList<>();       //将入度为0节点入队       for (int i = 0 ; i < graph.nodeSize; i++) {           if (inDegree[i] == 0) {               nodes.offer(i);          }      }       List<Character> result = new ArrayList<>();       //将入度为0节点一次出队处理       while (!nodes.isEmpty()) {           int node = nodes.poll();           if (visited[node]) {               continue;          }           visited[node] = true;           result.add(graph.node[node]);           //将当前node的邻接节点入度-1；           for (Object list : graph.adj[node]) {               -- inDegree[(int)list];               if (inDegree[(int)list] == 0) {                   //前驱节点全部访问完毕，入度为0                   nodes.offer((int) list);              }          }      }       return result;  }

测试样例1

public static void main(String[] args) {       ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();       //初始化一个图       Graph graph = new Graph(new char[]{A, B, C, D});       graph.addEdge(0, 1);       graph.addEdge(0,2);       graph.addEdge(1,3);       graph.addEdge(2,3);       List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);  }

执行结果

测试样例2

public static void main(String[] args) {       ToPoLogicalSort toPoLogicalSort = new ToPoLogicalSort();       //初始化一个图       Graph graph = new Graph(new char[]{A, B, C, D,E,F,G,H});       graph.addEdge(0, 1);       graph.addEdge(0,2);       graph.addEdge(0,3);       graph.addEdge(1,4);       graph.addEdge(2,4);       graph.addEdge(3,4);       graph.addEdge(4,7);       graph.addEdge(4,6);       graph.addEdge(7,5);       graph.addEdge(6,7);       List<Character> result = toPoLogicalSort.toPoLogicalSort(graph);  }

执行结果

总结

我在上面有说到，拓扑排序可以用来判断图是否存在环，其实判断方式很简单，实现步骤与上面一致，只是我们最后判断一下出队的元素个数是否等于图的节点个数，如果等于，证明图无环，如果不等于则证明存在环。

　　到此这篇关于Java实现拓扑排序的示例代码的文章就介绍到这了,更多相关Java拓扑排序内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。