目录

 

AOV网

拓扑排序简介

拓扑排序算法

java实现

拓扑排序

测试

---

AOV网

AOV网表示一个有向图中顶点，用弧表示顶点之间的优先关系。如下图所示，在AOV网中，若从顶点vi到顶点vj之间存在一条有向路径，则称顶点vi为顶点vj的前驱，顶点vj为顶点vi的后继。注意，AOV图不能有回路，否则会将序列陷入死循环，称为死锁。

拓扑排序简介

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

可以把一条边，当做是一种前提，比如上图，C指向E，代表C必须在E前，在拓扑排序中，前面的代表要先做的，后面的代表前面的作为才能做的

拓扑排序算法

对AOV网进行拓扑排序的基本思路：

从AOV网中选择一个入度为0的顶点输出；

然后删除此顶点，并删除以次顶点为尾的弧；

继续重复此操作.....

直到输出全部顶点或AOV网中不存在入度为0的顶点为止。

 

java实现

图的基本实现

https://blog.csdn.net/xushiyu1996818/article/details/90373591

拓扑排序

求图的拓扑序列的思路就是：先找到图中一个出度为0的顶点，访问该顶点并将之入栈。访问了该顶点之后，相当于指向该顶点的所有的边都已经被删除了。然后，继续在图中寻找下一个出度为0且未被访问的顶点，直至图中所有的顶点都已被访问。

前面的算法是找入度为0的顶点，但是这里是出度为0，原因是图的数据结构的问题，这里的图只能根据A找到A到B的边，不能根据B找到A到B的边，否则要全图遍历所有的边。

不过这里的方法是可行的，不过这里最先找到的顶点是最后一个做的顶点，最后找到的顶点是第一个要做的顶点，所以用栈来存储这些顶点

此拓扑排序算法实现的最坏情况下时间复杂度为：O(V*max(V,E))；空间复杂度为：O(V)--定义一个辅助栈来保存遍历顺序

//下面与拓扑排序相关 /** 返回一个出度为0（以该点出发的边数为0或者以该点出发的边的结束点都被访问过了），而且没有被访问过的顶点 * @return 如果没有，则返回null */ public Vertex<T> getNextTuopuVertex(){ Vertex<T> vertex; Iterator<Vertex<T>> iterator=getVertexIterator(); while(iterator.hasNext()){ vertex=iterator.next(); if((vertex.isVisited()==false)&&(vertex.getUnvisitedVertex()==null)){ //返回一个出度为0（以该点出发的边数为0或者以该点出发的边的结束点都被访问过了），而且没有被访问过的顶点 return vertex; } } //如果没有，则返回null return null; } /** 返回拓扑排序，返回的stack，第一个pop出的是第一个要做的顶点，最后一个是最后一个才能做的顶点 * @return */ public Stack<Vertex<T>> getTopuSort(){ clearVisitStatus(); Stack<Vertex<T>> stack=new Stack<>(); Vertex<T> vertex; while(true){ vertex=getNextTuopuVertex(); if(vertex==null){ //如果得不到下一个出度为0的节点，直接返回stack System.out.println("拓扑排序结束"); return stack; } //顶点入栈并被访问,遍历完成后,出栈就可以获得图的一个拓扑序列 stack.push(vertex); vertex.visit(); System.out.println("拓扑排序：入栈节点："+vertex.getLabel()); } }

测试

package datastructure.graph.adjacencymatrixgraph; public class Main { public static void main(String[] args) { Graph<String> graph=new Graph<>(true); graph.addVertex("first", 0); graph.addVertex("second", 0); graph.addVertex("third", 0); graph.addVertex("fourth", 0); graph.addEdge("first", "second", 1); graph.addEdge("first", "third", 2); graph.addEdge("third", "fourth", 2); graph.printGraph(); //graph.breathFirstTraversal("first"); //graph.depthFirstTraversal("first"); graph.getTopuSort(); } } 图是否为有向图：true，图的顶点个数：4，图的总边个数：3 顶点：first，以这个顶点为出发点的边的个数：2，该顶点的权值为：0.0 边：从 first 到 second ，权值：1.0 边：从 first 到 third ，权值：2.0 顶点：second，以这个顶点为出发点的边的个数：0，该顶点的权值为：0.0 顶点：third，以这个顶点为出发点的边的个数：1，该顶点的权值为：0.0 边：从 third 到 fourth ，权值：2.0 顶点：fourth，以这个顶点为出发点的边的个数：0，该顶点的权值为：0.0 拓扑排序：入栈节点：second 拓扑排序：入栈节点：fourth 拓扑排序：入栈节点：third 拓扑排序：入栈节点：first 拓扑排序结束

可以看到最后入栈的是第一个要做的，first是一切的起源