[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)

[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)

207. 课程表(有向图判断是否有环)

题目链接:https://leetcode-cn.com/problems/course-schedule/

关键点/分类

  • 图(有向图:边缘列表转邻接表);
  • 有向图的遍历(DFS(递归 + 记录节点访问状态)、BFS(队列));
  • 判断有向图是否有环:DFS(判断同一趟DFS是否访问一个节点两次), BFS(即拓扑排序,引入入度数组)

《[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)》

题目分析:把问题转化为拓扑排序问题

本题是一道经典的「拓扑排序」问题。

题目给定一个匹配关系[0,1]表示先学习课程0,需要先完成课程1,如果把课程看做图的节点,这一匹配关系相当于:1 -> 0。

那么什么情况下会导致无法完成所有课程的学习?

例如:输入[[1,0],[0,1]],表示学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是矛盾的。相当于 1 -> 0和0 -> 1不能同时存在。

这一要求和拓扑排序的定义是一样的:给定一个包含 n 个节点的有向图 G,我们给出它的节点编号的一种排列,如果满足:

对于图 G 中的任意一条有向边 (u,v),u 在排列中都出现在 v 的前面。

那么称该排列是图 G 的「拓扑排序」。

而拓扑排序有一个结论:

一个有向图如果存在拓扑排序,则图中不会有环;如果图中有环则不可能存在拓扑排序。

因此题目可以转化为一个拓扑排序问题:所有课程构成一张有向图,判断该有向图是否存在拓扑排序,即判定图中是否存在回路。

题目难点在于
1、如何处理用边缘列表表示的图?
题目给定的是边缘列表:
– 优点:可以在O(1)时间下知道当前节点和哪个节点相连;
– 缺点:如果要随机访问某个节点,需要O(N)的时间来寻找。

这样在访问每个指定节点时,都需要遍历整个边缘列表才能找到目标节点,效率低。

所以将边缘列表转换成邻接表,邻接表的类型是List<List<Integer>>,存放的是以每个节点为起点所能直接到达的所有邻接节点。后续两个思路都是基于邻接表。

2、如何判断图中是否有回路?

前置问题:如何对图做DFS和BFS。(见各思路的算法设计)

那么,如何判断图中是否存在回路的问题:

  • 思路1:使用DFS判断图中是否有回路,使用一个变量来标记节点是被当前这一趟DFS访问过还是被之前其他趟DFS访问过,如果遇到的是同一趟DFS访问过的节点,则说明出现环;(DFS判断是否有环其实没有用到拓扑排序,所以不适用于210题
  • 思路2:使用BFS(入度表)判断图中是否有回路,(BFS判断是否有环使用到了拓扑排序的思想)

所以,下文介绍了:边缘列表转邻接表、对有向图的邻接表进行常规DFS,BFS、如何改造DFS,BFS以判断有向图是否有环。

思路1:DFS + 标记数组 判断是否存在回路(并未用到拓扑排序思想)

算法设计

1、先将边缘列表转化为邻接表

邻接表使用双重列表:

List<List<Integer>> adjacency = new ArrayList<>();

使用之前先根据节点数numCourses在adjacency中初始化同样个数的列表元素,以便存放每个节点和与其通过有向边连接的所有相邻节点;

因为课程编号都是从0开始的,所以adjacency[i]就表示存放的是第i个课程的邻接节点。

2、如何对有向图进行DFS遍历?(对图做DFS的框架,不涉及DFS内部实现)

首先,理解什么是一趟DFS:

一趟DFS是以图中某个节点为起点,遍历节点的邻接表,每次选择一个邻接点,然后以邻接点为起点继续遍历它的所有邻接点,以此类推,直到以这个节点为起点所能到达的所有节点都被访问过。

接着,有向图可以看做是几棵树交织在一起,对其中一棵树做DFS,能够把这棵树的所有节点都遍历到,但却可能无法从这棵树到达其他树,

例如:
《[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)》
图中的第一棵树0 -> 1 -> 2,以0为起点进行一趟DFS,但到达2后,无论如何也无法再到达其他节点,所以这一趟DFS到此为止。

但图中还有剩余的节点没有被访问到,所以要再进行一趟DFS,选择另一个节点3作为起点开始新一趟DFS,以此类推。

只有当图中没有还未访问的节点,才说明对整个图的遍历完成。

因此DFS遍历图时,需要设置一个状态数组存放每个节点的访问状态,执行一次DFS,就选择一个从未被访问过的节点为起点,进行一趟DFS。这一趟DFS完成后,再从图中选择一个还未被访问过的节点作为新的起点,进行下一趟DFS,直到所有节点都被访问过。

代码框架

  //枚举邻接表的每个节点作为起点执行DFS
  for(int i = 0; i < numCourses; i++){ 
      //如果节点在之前的DFS被访问过,则直接跳过
      if(status[i] == -1) continue;
      
      //执行一趟DFS
      dfs();//内部实现见下文
  }
  • 按起点不同可以分为多趟DFS,每个起点对应一趟DFS。
  • 被访问过的节点不会再成为一趟DFS的起点。
3、如何实现一趟深度优先遍历DFS + 有环判断?

以邻接表中的第i个节点为起点,进行一趟深度优先遍历DFS:

每个节点在整个DFS过程中存在三种状态:

  • 未被访问过;
  • 被之前其他趟DFS访问过;
  • 被当前这一趟DFS访问过;

为什么要划分这三种状态?

因为只有一个节点在同一趟DFS中被访问2次才说明出现环路,如果一个节点在之前其他趟DFS被访问过,并不能说明存在回路,反而说明该节点在之前的DFS筛选下可以认为是安全的,不会出现环路的节点,可以在遇到这样的节点时直接跳过,避免重复工作。

这里要明确:有向图的环和无向图的环是不一样的。

例如:

如下图,如果在无向图中,0,1,2,3就构成了一个环;但在有向图中,0,1,2,3并不构成环。
其中,
节点3在一趟DFS:[0->3->4->5]中被访问过,所以status[2] = -1;
之后节点3又在另一趟DFS:[0->1->2->3]中被访问,遍历到节点3时,会发现此时的status[3] == -1,但并不会构成环路。

因为并不是同一趟DFS访问两次节点3。

《[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)》

记录每个节点的访问状态,可以提供判断是否出现环路的依据,可以减少重复工作,可以用于选择一趟DFS的起点,所以DFS遍历图的关键就在于 节点访问状态的记录

如何在DFS中使用节点的状态?

我们设置一个数组status来存放所有节点的状态,下标 i 对应第 i 个节点,数组的元素有三个取值,分别表示节点的三种状态,设置0表示未被访问过,-1表示被其他趟DFS访问过,1表示被当前趟DFS访问过。

在DFS遍历过程中:

  • 如果节点未被访问过,则在DFS过程中遇到该节点时直接访问即可;

  • 如果节点被之前其他趟DFS访问过,则说明在之前几趟DFS中并没有发现该节点存在环路,安全地进行到了当前这一趟DFS,所以该节点是安全的,可以直接跳过,避免做重复工作;

  • 如果节点被当前这一趟DFS访问过,则说明图中出现环路,直接返回false。

一趟带环路判断的DFS流程要如何进行?

乔杉说:常规的DFS都做的有点倦怠了,这个带环路判断的DFS,我不得其解。那么下面我们就来看看该怎么实现。

选择一个节点作为起点,遍历邻接表中该节点对应的邻接点,每枚举一个节点 i,就先判断它在status[i]中对应的状态:

  • 如果status[i] == 0,表示还未访问过,置status[i]=1,表示在这一趟DFS得到访问,继续后续的工作;
  • 如果status[i] == -1,表示在之前的DFS被访问过,可以直接跳过,返回true;
  • 如果status[i] == 1,则说明出现环路,返回false。(和常规DFS相比只增加了这个分支)

如果status[i] == 0,就置status[i]=1,然后继续遍历该节点在邻接表中的所有邻接点,依次选择其中一个邻接点,进入下一层DFS。

直到某个节点的邻接表为空,或所有邻接点都被访问过,则退出这一趟DFS,返回本趟遍历的结果,在开始下一趟DFS之前,要把本趟所访问到的节点的status[i]置为 -1,为下一轮DFS做准备。

实现代码

class Solution { 
    public boolean canFinish(int numCourses, int[][] prerequisites) { 
        //创建邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        //初始化每个节点对应的邻接表,则adjacency.get(i)表示课程i的邻接表
        for(int i = 0; i < numCourses; i++){ 
            adjacency.add(new ArrayList<Integer>());
        }
        //将边缘列表转换为邻接表:边缘列表[i,j]对应j->i
        for(int i = 0; i < prerequisites.length; i++){ 
            adjacency.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        //节点状态数组
        int[] status = new int[numCourses];
        //枚举邻接表的每个节点作为起点执行DFS
        for(int i = 0; i < numCourses; i++){ 
            //如果节点在之前的DFS被访问过,则直接跳过
            if(status[i] == -1) continue;
            //以节点i为起点调用dfs,如果dfs返回false,则直接退出循环返回false;如果dfs返回true,则继续枚举其他节点
            if(!dfs(i, status, adjacency)) return false;
        }
        //所有节点都遍历完也没有遇到环路,则返回true
        return true;
    }
    //DFS递归实现
    public boolean dfs(int node, int[] status, List<List<Integer>> adjacency){ 
        //如果当前节点在之前的DFS被访问过,直接返回true
        if(status[node] == -1) return true;
        //如果当前节点在当前的DFS被访问过,直接返回false
        if(status[node] == 1) return false;
        //如果当前节点还未被访问过,
        else{ 
            status[node] = 1;//表示在当前DFS被访问了
            //从邻接表中依次获取它的邻接节点作为下一层DFS的起点
            for(int i = 0; i < adjacency.get(node).size(); i++){ //邻接点数量=邻接表长度
                boolean res = dfs(adjacency.get(node).get(i), status, adjacency);
                if(!res) return false;
            }
            //把刚刚置1的节点状态置为-1,为下一趟dfs做准备
            status[node] = -1;//实质就是恢复现场
            //运行到这里说明以node为起点的dfs没有遇到环路,返回true
            return true;
        }
    }
}

思路2:BFS + 入度数组(拓扑排序思想)

广度优先遍历判断是否有环使用到了拓扑排序的思想。

拓扑排序的工作流程就是:不断将当前有向图中的一个入度=0的节点删除,直到无法再删除为止,判断此时图中是否还有剩余的节点,如果还有剩余节点,说明图中存在环路;如果没有剩余,说明有向图不含环路。

  • 可以发现BFS要判断是否有环,就需要知道每个节点的入度,因此引入一个入度数组存放每个节点的入度,在BFS过程中入度数组会实时更新。

算法设计

1、边缘列表转换为邻接表(同思路1)
2、对有向图的常规BFS要如何实现?

和树的BFS(即层次遍历)一样,使用一个队列保存当前节点的所有邻接节点,每次从队列中弹出队首,访问队首节点,然后把队首节点的所有邻接节点入队。

接着,继续弹出队首,以此类推,直到队列为空,说明BFS结束。

  • 注意:对于图而言,BFS结束并不代表图中所有节点都被遍历到。
3、如何用BFS判断有向图是否存在环路?(引入入度数组)

BFS判断是否存在环路,就需要用到拓扑排序的思想,常规的BFS入队的是当前节点的所有邻接节点,这里的BFS入队的是当前图中入度为0的节点。

所以需要设置一个入度数组indegrees存放每个节点的入度。

由此带来一个问题:入度数组的初始值如何设置?

入度数组的初始化时,边缘列表就可以利用起来了,例如:[0,1]表示1->0,这样就能得到0的入度+1。

BFS开始时,先将所有入度为0的节点都入队。

然后,弹出队首,按照拓扑排序的思想,将该节点从图中删除,但并不需要真的从图上删除,只需要将它的所有邻接点的入度-1,之后将入度为0的邻接点入队。

以此类推。

直到队列为空,说明遍历结束:

  • 如果此时删除的节点数 == numCourses,说明图被完全删除干净,图不包含环路,返回true。
  • 如果删除的节点数 < numCourses,说明图中还有未被删除的节点,即图中包含环路,返回false。

实现代码

class Solution { 
    public boolean canFinish(int numCourses, int[][] prerequisites) { 
        //创建邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        //初始化每个节点对应的邻接表,后面adjacency.get(i)表示课程i的邻接表
        for(int i = 0; i < numCourses; i++){ 
            adjacency.add(new ArrayList<Integer>());
        }
        //入度数组
        int[] indegrees = new int[numCourses];
        //将边缘列表转换为邻接表:边缘列表[v,u]对应u->v;入度数组初始化
        for(int i = 0; i < prerequisites.length; i++){ 
            //对于每个边缘列表元素[v,u]中将v的入度+1
            indegrees[prerequisites[i][0]]++;
            adjacency.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }

        Queue<Integer> queue = new LinkedList<>();//BFS专用的队列
        //初始时将当前所有入度为0的节点入队
        for(int i = 0; i < numCourses; i++){ 
            if(indegrees[i] == 0) queue.offer(i);
        }
        int count = 0;//记录删除节点的次数
        //开始执行BFS
        while(!queue.isEmpty()){ 
            int n = queue.size();
            for(int i = 0; i < n; i++){ 
                int top = queue.poll();//队首节点
                count++;//每删除一个队首节点,计数器+1
                //将队首节点删除,则它的所有邻接点的入度-1
                for(int j = 0; j < adjacency.get(top).size(); j++){ 
                    int next = adjacency.get(top).get(j);//队首节点的邻接点
                    indegrees[next]--;//邻接点入度-1
                    //如果邻接点入度=0,将其加入队列中
                    if(indegrees[next] == 0) queue.offer(next);
                }
            }
        }
        //队列为空时,说明对有向图的BFS结束,但不一定遍历了图中所有节点,需要进一步判断
        return count == numCourses;//如果删除的节点数==图中节点数,说明图中不含环路
    }
}

210. 课程表 II(有向图寻找拓扑排序)

题目链接:https://leetcode-cn.com/problems/course-schedule-ii/

关键点/分类

  • 图(有向图:边缘列表转邻接表);
  • 有向图的遍历(BFS(队列));
  • 寻找有向图中的拓扑序列: BFS + 入度表

《[图 拓扑排序 DFS BFS] 207. 课程表(有向图判断是否有环:DFS、BFS)210. 课程表 II (有向图找拓扑排序:BFS)》

题目分析

这题和207.课程表类似,不同点在于207题只需要判断能否完成所有课程;本题需要给出一个正确的学习顺序,即给出一个拓扑排序。

但具体做法都是一样的,问题都可以转化为拓扑排序问题,解法包括:DFS、BFS,DFS的实现有更多细节问题,所以这里只介绍BFS。

BFS的实现和207基本相同,增加一个存放拓扑序列的一维数组res而已。

前置工作:

1、边缘列表转邻接表:
邻接表用List<List> adjacency 表示;
边缘列表的一个元素为[1,0]表示的匹配关系是0->1,所以1是0的一个邻接点,要加入0的邻接表。

2、对图做BFS的常规实现

更具体的分析见207的解析,下面直接介绍解题思路。

思路1:BFS + 入度表 (拓扑排序思想)

1、使用一个队列实现BFS,设置一个一维数组res存放正确的课程学习顺序

2、创建一个数组indegrees存放每个节点的入度数,数组的初始化要依赖边缘列表。

3、在BFS之前,先将所有入度为0的节点加入队列。
进入BFS:

弹出队首,相当于从图上删除该节点,就将它加入到res中,然后将它所有邻接点的入度都-1,如果邻接点的入度 == 0就将该邻接点也入队。后面的流程以此类推。

直到队列为空,判断加入res的元素个数是否 == numCourses,如果等于,说明得到一个正确的顺序,如果不等于,则返回res。

  • BFS拓扑排序可以解决用例:2,[],的情况,[]表示没有给出课程匹配关系,即课程之间没有先后顺序,先读谁都行。

知识点:如何返回空数组

返回空的一维数组:

return new int[0];

因为一旦开辟的数组大小>0,元素就会默认填充0,而不是空,所以大小要填0才能得到空数组。

实现代码

class Solution { 
    
    public int[] findOrder(int numCourses, int[][] prerequisites) { 
        int[] res = new int[numCourses];//存放一个正确学习顺序的数组
        int num = 0;//记录加入res的课程数
        //邻接表 + 初始化
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i = 0; i < numCourses; i++){ 
            adjacency.add(new ArrayList<Integer>());
        }
        //边缘列表转邻接表
        for(int i = 0; i < prerequisites.length; i++){ 
            adjacency.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        //入度表:[0,1]表示1->0,0入度+1
        int[] indegrees = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++){ 
            indegrees[prerequisites[i][0]]++;
        }

        //BFS需要的队列,将所有入度为0的点入队
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++){ 
            if(indegrees[i] == 0) queue.offer(i);
        }
        while(!queue.isEmpty()){ 
            int n = queue.size();
            for(int i = 0; i < n; i++){ 
                int top = queue.poll();
                res[num++] = top;
                //将所有邻接点的入度-1
                for(int j = 0; j < adjacency.get(top).size(); j++){ 
                    int next = adjacency.get(top).get(j);
                    indegrees[next]--;
                    if(indegrees[next] == 0) queue.offer(next);
                 }
            }
        }

        return num == numCourses ? res : new int[0];
    }

}
    原文作者:m0_38142029
    原文地址: https://blog.csdn.net/m0_38142029/article/details/108718502
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞