公众号merlinsea
- AOV网
- 活动在顶点上的网（Activity on Vertex Network，AOV）是一种可以反映各个工程顶点先后关系的一种有向图，通过拓扑排序，我们可以得到这些活动先后执行的一个合理顺序。
- 拓扑排序算法
- 从有向图中输出没有前驱的节点，即那些入度为0的节点
- 将输出的节点在原图中删除并删除由其发出的边
- 重复前面两个步骤，直到没有节点输出为止
- 关于拓扑排序的思考
- 如果一个有向图存在回路，那么拓扑排序输出的节点必然会少于节点总数。
- 拓扑排序关注的是节点的入度
- 拓扑排序代码实现
public class Main { public static void main(String[] args) { int[][] edges = new int[][]{{1,6},{1,2},{0,2},{0,3},{6,5},{2,5},{2,3},{5,4},{3,7},{4,9},{7,9},{7,8}}; LinkGraph linkGraph = new LinkGraph(10,edges); // 计算每个节点的入度 int[] inDegree = new int[10]; for(int i = 0; i<linkGraph.graph.length; i++){ EdgeNode edgeNode = linkGraph.graph[i].neighbors; while(edgeNode!=null){ //计算出每个节点的入度 inDegree[edgeNode.no]++; edgeNode = edgeNode.next; } } Queue<Integer> queue = new LinkedList<>(); // 初始化队列 for(int i=0;i<inDegree.length;i++){ if(inDegree[i]==0){ queue.offer(i); } } while(!queue.isEmpty()){ int cur = queue.poll(); // 输出一个入度为0的节点 System.out.println("节点 "+cur); // 取出cur的邻居节点 EdgeNode edgeNode = linkGraph.graph[cur].neighbors; while(edgeNode!=null){ inDegree[edgeNode.no]--; // 删除当前节点后如果存在入度为0的节点就加入队列中 if(inDegree[edgeNode.no]==0){ queue.offer(edgeNode.no); } edgeNode = edgeNode.next; } } } }
- 拓扑排序可以解决的问题
- LeetCode上面关于课程表的问题，如果给出一个学生学习的课程之间不同的先导课程，那么请给出一个合理的课程安排顺序，要求保证每门课程学习之前都已经学习过这门课程的先导课了。
- 针对这种输出次序有先后要求的问题，可以考虑使用拓扑排序来解决。
