当前位置：首页 > article >正文

[Lc18_BFS拓扑排序] 邻接表 | 课程表I II

article 2025/3/28 15:52:04

0.简介

1.有向无环图(DAG图)

2.AOV网(顶点活动图)

3.拓扑排序

4.实现拓扑排序

2.课程表

题解

3.课程表 II

题解

0.简介

拓扑排序解决的就是有向无环图的排列问题。

接下来先介绍有向无环图，然后是有向无环图的一个应用 AOV网(顶点活动图)，然后根据AOV网再来说说什么是拓扑排序，以及实现拓扑排序。

1.有向无环图(DAG图)

有向无环图指的是有方向，但没有环的图。
图就是一个顶点和边连接而成的一个数据结构，有向图就是边都是有方向的。
有向无环图就是图中是没有环的。
如不能从1->2->3，3->2->4 所以这个图就是一个有向无环图。

如 4->5->6 是可以走通的，这就不是有向无环图了。

什么是入度和出度？

入度和出度都是针对一个点来说的

入度：有多少条边指向这个顶点
出度：由这个顶点出去多少条边

2.AOV网(顶点活动图)

AOV网也叫做顶点活动图，它其实是一个有向无环的一个应用。

在有向无环图中，用顶点来表示一个活动，用边来表示执行活动的先后顺序的图结构
比如我想洗菜，我得先买菜，我想腌肉需要先买菜和准备厨具。。

3.拓扑排序

通俗来讲就是，在AOV网中找到做事情的先后顺序。
可以看到在这些活动中，其中一些活动必须在某些活动执行之后才能执行，比如说炒菜，必须先切菜，腌肉。
所以在整个工程中这个炒菜绝对不可能先干。

那些活动可以先干呢？

可以看到准备厨具、买菜可以先干，原因就是并没有边执行它们俩。
可以先准备厨具，或者先买菜。

所以从这里就可以发现一点，拓扑排序的结果可能不是唯一的！

如果先买菜，买完菜之后与买菜相连的箭头就可以删掉了
因为买完菜就可以解锁洗菜的操作了。所以这个箭头就可以删去了。

接下来可以准备厨具或者洗菜，原因是它俩都没有其他条件来限制。可以任选一个。

接下来只能洗菜啦
同理重复上面操作，最后我们就可以得到这样的做事情先后的序列，这也是就是拓扑排序的序列。

找到做事情的先后顺序。

做一个事情之前，存在前置条件，要先做完...再做完...才能做这个

如何排序？

找出图中入度为 0 的点，然后输出
删除与该点相连的边
重复1、2操作，直到图中没有点或者没有入度为 0 的点为止

图中没有点理解，所有活动都找完了可以停止了此时的序列就是拓扑排序的序列。

图中没有入度为 0 的点是怎么回事？

其实就是在这个拓扑排序中可能面对的不是有向无环图，是有环形结构的。
比如下面这个图，刚开始并不知道这个有向图是不是有环的，所以我们可以先做一下拓扑排序
当把1、3、2拿出来之后，发现剩下的都拿不出来了。
原因就是4、5、6形成一个环路，是没有入度为0的边。

因此这个结束条件还需要加上直到图中没有入度为 0 的点为止原因就是可能有环！
所以说拓扑排序有一个特别重要的应用，判断有向图中是否有环。

如何判断？

直接对图来一次拓扑排序，当拓扑排序过程中发现没有入度为0的点的时候
但是图中还有剩余点的时候，此时这个图中一定会有环形结构。

4.实现拓扑排序

借助队列，来一次 BFS 即可

初始化：把所有入度为 0 的点加入到队列中
当队列不为空的时候

1. 拿出队头元素，加入到最终结果中
2. 删除与该元素相连的边
3. 判断：与删除边相连的点，是否入度变成 0 ，如果入度为 0，加入到队列中

这里还有一个问题没说，如何建图？如何表示一个点的入度呢？下面的题在说。

建完图再进行拓扑排序。

2.课程表

链接： 207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

题解

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 ，如 0 、1、2等等。
如果给的是一个一个字符串，一会建图的时候还需要先把字符串转换成一个一个数才能映射。

在选修某些课程之前需要一些先修课程。

先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。

其实这道题问题的就是有向图中是否有环。

我们可以把给的信息抽象称一张有向图，题目问能否完成所有课程学习意思就是能不能把这个课程排个序
说白了就是能否拓扑排序
能否拓扑排序也就是是否这个图是否是有向无环图 —> 有向图中是否有环？

做一次拓扑排序即可，前面已经说过如何拓扑排序，接下来重点就是如何建图？

如何建图？灵活使用语言提供的容器

可以参考图部分的博客笔记~[数据结构#2] 图(1) | 概念 | 邻接矩阵 | 邻接表 | 模拟

看稠密（看数据量）

邻接矩阵（稠密图）
邻接表（稀疏图）

这道题我们用邻接表建图

相像中的邻接表最左边代表某个节点，这个节点右边一坨代表这个点所连接的点。
看起来就像一个个链表，头表示当前所考虑的这个节点，后面相连所有的节点是与我当前点相连的节点。
我们建图的目的就是为了方便找到某个点所连接的那个点。
不然还要遍历数组去找太麻烦了，所以把这些东西先存到一个数据结构中，这个数据结构就是图。

邻接表我们脑海中想到的应该就是这样的一条一条链表的结构。

那如何实现一个邻接表呢？

我们没有必须真的搞一个链式结构出来，这里有两种方式：

vector<vector> edges
unordered_map<int,vector> edges

用vector嵌套一个vector是比较局限的，只能用于节点里面的值是数字表示的。

用unordered_map是比较万能的，可以把int —> string， vector< int > —> vector< string >，等等其他任何类型。

vector嵌套一个vector，通过下标可以找到与这个节点的值相连的其他节点。
仅需在对应下标的vector做push_back就可以把与当前节点相连的节点加入。

用unordered_map就比较万能了，完全像刚才想象出来的邻接表结构，我们这里是一个int的数后面挂了一个int数组，那不就和一个节点挂着一个节点的效果一样的吗。
用数组表示所连接的节点。

根据算法流程，灵活建图

刚才我们只是实现把所有的边存起来。我们还要根据算法流程多添加一些东西。

比如这里我们是做拓扑排序，因此我们需要知道每个顶点的入度是多少。
可以用一个vector< int > ，数组里面的值就表示这个顶点的入度是多少。
总结：建图先看数据量选择邻接矩阵还是邻接表来建图，然后根据算法流程，灵活的在建图的基础上多添加上一点东西。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        //拓扑排序 判环
        unordered_map<int,vector<int>> graph;
        vector<int> in(numCourses,0);//初始化 入度数组

        for(auto& p:prerequisites)
        {
    //!!!可以 自动创建 不存在的键
            graph[p[1]].push_back(p[0]);
            in[p[0]]++;
        }//建立 邻接表
//在建图时 判断一下入度为0

    queue<int> q;
    for(int i=0;i<numCourses;i++)
    {
        if(in[i]==0)
            q.push(i);
    }

//！！！！！！！！记录已完成的课程数
//用于判环
    int count=0;

    while(q.size())
    {
        int a=q.front();
        q.pop();
        count++;

        for(auto p:graph[a])
        {
            // for(int m:p)
            // ... ...已经 传的是vector了
                if(--in[p]==0)
                {
                    q.push(p);
                }
        }
    }  
//成环部分 是无法入队的
    return count==numCourses;
    }
};

3.课程表 II

链接： 210. 课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前必须先选修 bi 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

题解

这道题和上面是一模一样的，还是做一次拓扑排序，不同的是这次要把拓扑排序顺序返回来。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) 
    {
        //邻接表
        unordered_map<int,vector<int>> graph;
        vector<int> in(numCourses,0);

        for(auto& p:prerequisites)
        {
            graph[p[1]].push_back(p[0]);
            in[p[0]]++;
        }

        vector<int> ret={};
        queue<int> q;
        for(int i=0;i<numCourses;i++)
        {
            if(in[i]==0)
            {
                q.push(i);
                ret.push_back(i);
            }
        }

        while(q.size())
        {
            int a=q.front();
            q.pop();

            for(int m : graph[a])
            {
                if(--in[m]==0)
                {
                    q.push(m);
                    ret.push_back(m);

                }
            }
        }
        //判环
        if(ret.size() != numCourses) 
            return {};
        
        return ret;
    }
};

查看全文

http://www.kler.cn/a/599510.html