拓扑排序问题

简介: 拓扑排序问题

公众号merlinsea


  • AOV网
  • 活动在顶点上的网(Activity on Vertex Network,AOV)是一种可以反映各个工程顶点先后关系的一种有向图,通过拓扑排序,我们可以得到这些活动先后执行的一个合理顺序。

640.png


  • 拓扑排序算法
  • 从有向图中输出没有前驱的节点,即那些入度为0的节点
  • 将输出的节点在原图中删除并删除由其发出的边
  • 重复前面两个步骤,直到没有节点输出为止
  • 关于拓扑排序的思考
  • 如果一个有向图存在回路,那么拓扑排序输出的节点必然会少于节点总数。
  • 拓扑排序关注的是节点的入度
  • 拓扑排序代码实现


640.png


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上面关于课程表的问题,如果给出一个学生学习的课程之间不同的先导课程,那么请给出一个合理的课程安排顺序,要求保证每门课程学习之前都已经学习过这门课程的先导课了。
  • 针对这种输出次序有先后要求的问题,可以考虑使用拓扑排序来解决。
相关文章
|
4月前
拓扑排序
拓扑排序
21 0
|
4月前
|
NoSQL 容器 消息中间件
图、图的遍历及图的拓扑排序
图、图的遍历及图的拓扑排序
|
5月前
|
存储 人工智能 算法
【算法总结】拓扑排序
【算法总结】拓扑排序
30 0
|
8月前
我们来看看拓扑排序
我们来看看拓扑排序
|
人工智能 自然语言处理 搜索推荐
拓扑排序算法
拓扑排序算法
90 0
|
存储 算法 Java
【数据结构与算法】有向图的拓扑排序
【数据结构与算法】有向图的拓扑排序
150 1
【数据结构与算法】有向图的拓扑排序
拓扑排序(邻接表实现)
拓扑排序(邻接表实现)
140 0
拓扑排序(邻接表实现)
|
机器学习/深度学习 存储
图的遍历 无向图深搜 宽搜
图的遍历 无向图深搜 宽搜
图的遍历 无向图深搜 宽搜
|
搜索推荐 算法
|
人工智能 BI
[Nowcoder] 有向无环图 | 拓扑排序简单应用
题目描述 Bobo 有一个 n 个点,m 条边的 有向无环图 (即对于任意点 v,不存在从点 v 开始、点 v 结束的路径)。 为了方便,点用 1 , 2 , … , n编号。 设count(x,y) 表示点 x 到点 y 不同的路径数量(规定count(x,x)=0,Bobo 想知道 ∑i=1n∑j=1ncount(i,j)⋅ai⋅bj 除以( 1 0 9 + 7 ) 的余数。 其中,a i , b j 是给定的数列。
108 0