环检测以及拓扑排序算法

Java leetcode
数据结构与算法
发布日期:   2023-02-24

1. 环检测算法

这道题可以先看到关于这道题的描述:

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

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

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

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

就是说,给出n门,问你能否存在一种方法,使得能够完整修完这n门课？

首先,存在这种前置条件的连接关系,一般就要想到利用图来做了,那么在这道题中,能否完成所有的课程,取决于是否有循环依赖,如果有循环依赖,那么就证明无法完成课程的修读,比如说我想修读课程A,那么必须修读课程B,但是我修读课程B,那么必须要修读课程A

如果完成图论问题,一般可以分成两步

  • 第一步,将题中给出的关系,转换为图的关系,比较常见的有邻接矩阵和邻接表
  • 第二步,根据图的关系,执行搜索算法

那么对于这道题而言,首先要将数组关系转换成一幅图,写出伪代码如下:

/**
 * 这里建立的是一个被依赖的关系,也就是说,通过map[i]->target
 * 它的含义是说:只有先完成i才能完成target
 * @param prerequisites:它的含义是说,你只有完成了[1],才能完成[0]
 * @return
 */
private List<Integer>[] buildMap(int[][] prerequisites){
    while(关系还没有遍历完){
        //from边
        int from = prerequisites[i][1];
        //to边
        int to = prerequisites[i][0];
        //添加一条从from指向to的有向边
        graph[from].add(to);
    }
    return graph;
}

那么在接下来拿到这个图之后,就要开始遍历了:

private void traverse(List<Integer>[] graph,int s){
    if(在本次遍历的路径上遇到过这个点){
        产生了环;
        标记并且返回;
    }
    if(已经遍历过了这个点){
        return;
    }
    标记当前节点已经被访问过;
    将当前节点加入到当前访问路径中;
    继续遍历;
}

将伪代码进行修正,得到:

public class CanFinish {
    private boolean[] visited;
    private boolean[] onPath;
    private boolean hadCycle;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        //1. 建图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        //2. 对图进行搜素,看是否有环
        for(int i = 0;i<numCourses;i++){
            traverse(graph,i);
        }
        //3. 返回结果
        return !hadCycle;
    }


    private void traverse(List<Integer>[] graph,int s){
        if(onPath[s]){
            hadCycle = true;
            return;
        }
        if(hadCycle || visited[s]){
            return;
        }
        //标记当前节点已经被访问过
        visited[s] = true;
        //将当前节点加入到当前访问路径中
        onPath[s] = true;
        //继续遍历
        for (Integer node : graph[s]) {
            traverse(graph,node);
        }
        onPath[s] = false;
    }

    /**
     * 这里建立的是一个被依赖的关系,也就是说,通过map[i]->target
     * 它的含义是说:只有先完成i才能完成target
     * @param prerequisites:它的含义是说,你只有完成了[1],才能完成[0]
     * @return
     */
    private List<Integer>[] buildGraph(int numCourses,int[][] prerequisites){
        //1. 建立图的负载
        List<Integer>[] graph = new ArrayList[numCourses];
        //2. 初始化图
        for(int i = 0;i<numCourses;i++){
            graph[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            //from边
            int from = prerequisite[1];
            //to边
            int to = prerequisite[0];
            //添加一条从from指向to的有向边
            graph[from].add(to);
        }
        return graph;
    }
}

2. 拓扑排序

这里先说一个结论:在进行遍历的时候,只需要在后序的位置将节点的值添加到数组中,然后最终将数组逆序就可以就是答案了?(在定义了被依赖的这种关系的前提下)

在进行遍历的时候,只需要在后序的位置将节点的值添加到数组中,最终就是答案了,在定义了依赖的这种关系的前提下

为什么?

首先要理解拓扑排序中,什么样的节点可以被加入队列,是那些没有入边的节点,就可以被加入到队列中来,那么什么时候这个节点没有入边呢,试想一下,我们使用后序遍历的过程中,只有当左右(或者是连通的其他节点)节点都遍历完了之后,才会访问本节点

定义依赖和被依赖有什么区别?

如果是定义依赖,那么边的指向就是它需要依赖的那些对象,只有当被依赖的那些对象全部被访问完了之后,才能访问此对象,被定义被依赖,这个就比较抽象,不好理解,但是你可以理解为,两者就是顺序不同而已。

我们只需要理解定义依赖的这种情况就好了

首先我们利用依赖的这种关系,将第一题的算法重新编写一次,验证我们的猜想是否正确

private boolean[] visited;
private boolean[] onPath;
private boolean hasCycle;

public boolean canFinish(int numCourses, int[][] prerequisites) {
    //1. 初始化常量
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    //2. 建图
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    //3. 遍历
    for(int i = 0;i<numCourses;i++){
        traverse(graph,i);
    }
    //4. 返回结果
    return !hasCycle;
}

/**
 * 定义依赖关系,也就是说:从map[i]->target
 * 其中i需要依赖于target
 * @param numCourses:有几门课
 * @param prerequisites:课的依赖关系
 * @return
 */
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
    //1. 初始化图
    List<Integer>[] graph = new LinkedList[numCourses];
    for(int i = 0;i<numCourses;i++){
        graph[i] = new LinkedList<>();
    }
    //2. 遍历关系表
    for (int[] prerequisite : prerequisites) {
        //学习[0]必须先学习[1]
        //那么也就是说[0]依赖于[1]
        int from = prerequisite[0];
        int to = prerequisite[1];
        graph[from].add(to);
    }
    return graph;
}

//遍历函数
private void traverse(List<Integer>[] graph,int s){
    if(onPath[s]){
        hasCycle = true;
    }
    if(hasCycle || visited[s]){
        return;
    }
    visited[s] = true;
    onPath[s] =true;
    for (Integer t : graph[s]) {
        traverse(graph,t);
    }
    onPath[s] = false;
}

这样的话是完全正常的,只是修改了边与边之间的关系而已,于是我们继续在这个基础上修改代码

private boolean[] visited;
private boolean[] onPath;
private boolean hasCycle;
private int[] ans;
private int idx = 0;

public int[] finOrder(int numCourses, int[][] prerequisites) {
    //1. 初始化常量
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    ans = new int[numCourses];
    //2. 建图
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    //3. 遍历
    for(int i = 0;i<numCourses;i++){
        traverse(graph,i);
    }
    //4. 返回结果
    //4.1 如果有环,就是空数组
    if(hasCycle){
        return new int[]{};
    }
    //4.2 如果无环,那么就返回一个合法的数组回来
    return ans;
}

/**
 * 定义依赖关系,也就是说:从map[i]->target
 * 其中i需要依赖于target
 * @param numCourses:有几门课
 * @param prerequisites:课的依赖关系
 * @return
 */
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
    //1. 初始化图
    List<Integer>[] graph = new LinkedList[numCourses];
    for(int i = 0;i<numCourses;i++){
        graph[i] = new LinkedList<>();
    }
    //2. 遍历关系表
    for (int[] prerequisite : prerequisites) {
        //学习[0]必须先学习[1]
        //那么也就是说[0]依赖于[1]
        int from = prerequisite[0];
        int to = prerequisite[1];
        graph[from].add(to);
    }
    return graph;
}

//遍历函数
private void traverse(List<Integer>[] graph,int s){
    if(onPath[s]){
        hasCycle = true;
    }
    if(hasCycle || visited[s]){
        return;
    }
    visited[s] = true;
    onPath[s] =true;
    for (Integer t : graph[s]) {
        traverse(graph,t);
    }
    ans[idx++] = s;
    onPath[s] = false;
}

3. 环检测算法的BFS解法

BFS的算法流程,实际上就是拓扑排序的原始算法,这里的话简单描述一下拓扑算法的算法是怎么样的

检测全图,看是否有入度为0,如果有的话,那么就将这个节点和他相连的边直接删除,如果图中的节点保持不变,此时观察节点数量是否为0,如果为0,那么就无环,同时遍历的序列就是拓扑排序的结果,否则的话就是有环,抛出异常,无法完成拓扑排序

  1. 构建临接表,建图,边的方向表示被依赖的关系

为什么是被依赖的关系,因为只有那些不需要任何依赖的课程才是拓扑排序的起点,因此在这个情况下,定义为被依赖的关系是比较好理解的

private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites){
    //1. 初始化图
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    //2. 遍历关系,建图
    for (int[] prerequisite : prerequisites) {
        //[0]依赖于[1],那么也就是说:从[1]出发到[0]
        int from = prerequisite[1];
        int to = prerequisite[0];
        graph[from].add(to);
    }
    return graph;
}
  1. 构建一个inDegree[]数组来记录第i个节点的入度,那么怎么算有入度呢?就是说当有被人指向的时候,就是有入度,在上面的建图函数中,to就代表着,有一条边指向了to,因此就是:
inDegree[to]++;
  1. 对BFS队列进行初始化,首先对于那些入度为0的节点首先加入队列
  2. 开始执行BFS循环,不断弹出队列中的节点,减少相邻节点的入度,并且将入读为0的节点加入到队列中
  3. 如果最终所有节点都被遍历过,count == 节点数,说明环是能够消除完的,反之就是说明存在环
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //1. 初始化入度数组
        int[] inDegree = new int[numCourses];
        int node = 0;
        //2. 初始化图 && 计算每个节点的入度
        List<Integer>[] graph = buildGraph(numCourses, prerequisites, inDegree);
        //3. BFS搜索
        //3.1 初始化队列
        Queue<Integer> q = new ArrayDeque<>(numCourses);
        //3.2 将入度为0的数组加入到队列中
        for (int i = 0; i < inDegree.length; i++) {
            if(inDegree[i] == 0){
                q.offer(i);
            }
        }
        //3.3 开始广搜
        while(!q.isEmpty()){
            //3.4 弹出头节点,这个头结点要从图中删除
            Integer head = q.poll();
            node++;
            //3.5 要删除头节点,那么就要将头节点的相邻边也删除
            for (Integer t : graph[head]) {
                if(--inDegree[t] == 0){
                    q.offer(t);
                }
            }
        }
        //4. 返回结果
        return node == numCourses;
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites,int[] inDegree){
        //1. 初始化图
        List<Integer>[] graph = new LinkedList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        //2. 遍历关系,建图
        for (int[] prerequisite : prerequisites) {
            //[0]依赖于[1],那么也就是说:从[1]出发到[0]
            int from = prerequisite[1];
            int to = prerequisite[0];
            graph[from].add(to);
            inDegree[to]++;
        }
        return graph;
    }
}

4. 拓扑排序BFS

其实非常简单,只需要在poll()的时候将元素加到数组来就行了

public int[] findOrder(int numCourses, int[][] prerequisites) {
    //1. 初始化入度数组
    int[] inDegree = new int[numCourses];
    int[] ans = new int[numCourses];
    int node = 0;
    //2. 初始化图 && 计算每个节点的入度
    List<Integer>[] graph = buildGraph(numCourses, prerequisites, inDegree);
    //3. BFS搜索
    //3.1 初始化队列
    Queue<Integer> q = new ArrayDeque<>(numCourses);
    //3.2 将入度为0的数组加入到队列中
    for (int i = 0; i < inDegree.length; i++) {
        if(inDegree[i] == 0){
            q.offer(i);
        }
    }
    //3.3 开始广搜
    while(!q.isEmpty()){
        //3.4 弹出头节点,这个头结点要从图中删除
        Integer head = q.poll();
        ans[node++] = head;
        //3.5 要删除头节点,那么就要将头节点的相邻边也删除
        for (Integer t : graph[head]) {
            if(--inDegree[t] == 0){
                q.offer(t);
            }
        }
    }
    //4. 返回结果
    if(node == numCourses){
        return ans;
    }else{
        return new int[]{};
    }
}
文章作者: 穿山甲
文章链接: https://lumxi.github.io/2023/02/24/algorithm/normal/top-sort/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 穿山甲 !
Java leetcode
赏
  目录