一起学习交流~

图-02-拓扑排序

算法 laomuji 7个月前 (03-01) 326次浏览 已收录 0个评论

拓扑排序

一般用于解决先做什么,后做什么的问题,比如B依赖于A,那么必须先完成A才能完成B
拓扑排序需要用到inDegree(入度)的概念

如图所示:

拓扑排序的结果不一定是唯一的,只要符合条件就行

例题

比如力扣207题和210题的课程表
https://leetcode-cn.com/problems/course-schedule-ii/

测试数据:
输入:numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出:[0,2,1,3]

拓朴排序题解

有4门课,编号为0,1,2,3
课程1依赖于课程0
课程2依赖于课程0
课程3依赖于课程1
课程3依赖于课程2

那么可以建立以下邻接矩阵
课程0:0 1 1 0
课程1:0 0 0 1
课程2:0 0 0 1
课程3:0 0 0 0
由于该题是有向图,使用邻接矩阵浪费比较大,所以使用邻接表来存放边
那么就可以建立以下邻接表,节约内存
课程0:1 2
课程1:3
课程2:3
课程3:

那么此时,课程入度和出度为:
课程0: 0,2
课程1: 1,1
课程2: 1,1
课程3: 2,0
但拓扑排序不需要考虑出度,只需要考虑入度
也就是说
课程0 依赖于0个其它课程
课程1 依赖于1个其它课程
课程2 依赖于1个其它课程
课程3 依赖于2个其它课程
拓扑排序步骤如下
先把入度为0的课程加入队列
出队,把依赖于该课程的课程入度-1,然后判断是否为0,若为0则入队

对应上面的数据就是
队列:0
出队:0
课程1入度-1,入度为0,加入队列
课程2入度-1,入度为0,加入队列
队列:1 2
出队:1
课程3入度-1,入度为1
出队:2
课程3入度-1,入度为0,加入队列
队列:3
出队:3

可以根据出队的数量来判断是否可以学完所有课程

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>>edges(numCourses,vector<int>());//邻接表
        vector<int>inDegrees(numCourses,0);//记录各个节点的入度
        queue<int>que;//队列
        vector<int>result;//存放返回的结果
        for(const auto&prerequisite : prerequisites){
            edges[prerequisite[1]].push_back(prerequisite[0]);
            inDegrees[prerequisite[0]]++;
        }
        //先把入度为0的数据加入队列
        for(int i =0;i<inDegrees.size();i++){
            if(inDegrees[i]==0)que.push(i);
        }
        while(que.size()){//若队列中存在数据
            int u = que.front();que.pop();//出队
            result.push_back(u);//加入结果
            //将由当前节点作为u的边的v的点的入度-1
            for(int v =0;v<edges[u].size();v++){
                inDegrees[edges[u][v]]--;//入度-1
                if(inDegrees[edges[u][v]]==0)que.push(edges[u][v]);//若为0则加入队列
            }

        }
        if(result.size()<numCourses)return {};//若个数不正确则返回空数组
        return result;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论