环检测算法

• 给定一个图，判断图中是否存在环，可以使用dfs求解，根据图的类型可以分为两种类型：

  • （1）无向图判断是否有环；

  • （2）有向图判断是否有环。

1. 无向图环检测算法

分析

• 使用st数组记录在深度遍历的过程中是否存在点之前已经被遍历过，如果存在，说明存在环。

• 注意为了消除无向边的影响，递归的过程中需要传入每个点的父节点fa。

代码

• C++

/* 测试用例
3 3
1 2
2 3
3 1
*/
#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 有环的返回true
bool dfs(int u, int fa) {
    
    st[u] = true;
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        
        if (st[j] || dfs(j, u)) return true;
    }
    return false;
}

int main() {
    
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (!st[i] && dfs(i, -1)) {
            flag = true;
            break;
        }
    
    if (flag) puts("YES");
    else puts("NO");
    
    return 0;
}

2. 有向图环检测算法

方法一

分析

• 有向图不同于无向图，不能使用无向图的方式判断是否有环，因为即使遍历到了之前遍历过的点，也不能确定有环，如下图：

• 从上图可以看出，两次递归路径会遍历到同一个点，即编号为6的点，但是因为是有向图，因此没有环。

• 使用st数组记录每个点是否在之前遍历过，同时使用path数组记录当前在递归路径上的点，如果遍历到path上的点，说明存在环；否则如果当前遍历的点不再path上且st为true的话，则之后的递归路径上不会存在环，返回false即可；否则继续递归遍历。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
bool st[N], path[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 有环的返回true
bool dfs(int u) {
    
    st[u] = true;
    path[u] = true;
    
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        
        if (path[j]) return true;
        if (st[j]) return false;
        
        if (dfs(j)) return true;
    }
    
    path[u] = false;
    
    return false;
}

int main() {
    
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }
    
    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (!st[i] && dfs(i)) {
            flag = true;
            break;
        }
    
    if (flag) puts("YES");
    else puts("NO");
    
    return 0;
}

方法二

分析

• 可以使用拓扑排序判断有向图中是否存在环，只需要判断是否所有点都入队即可。

• 如果所有点都入过队，则说明存在拓扑序，因此不存在环；否则存在环。

代码

• C++

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010, M = N * 2;

int n, m;
int h[N], e[M], ne[M], idx;
int d[N], q[N];

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {
    
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (d[i] == 0)
            q[++tt] = i;
    
    while (hh <= tt) {
        int t = q[hh++];
        
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q[++tt] = j;
        }
    }
    
    return tt != n - 1;  // 不是所有点如果队，则存在环
}

int main() {
    
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        cin >> a >> b;
        d[b]++;
        add(a, b);
    }
    
    if (topsort()) puts("YES");
    else puts("NO");
    
    return 0;
}

一、今日刷题

1.题目

207. 课程表

跳转LeetCode

你这个学期必须选修 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 。这是不可能的。

2.分析

参考文章

一上来读题都有点没读懂，看过分析后才理解，题目中给的 numCourses 并不是限制条件，反而在做题中会作为声明的数组长度的数值，为我们提供帮助。真正起限制作用的是二维数组 prerequisites，该数组中存储着每门课程的前置课程，当我们所选的课程与某门课程形成互为前置课程的关系时，会导致无法完成所有课程的学习。

我们采用图结构来解决此问题，因此，题目转化为：判断以所有课程为节点生成的图中是否存在环。

在编码层面，问题则转化为：由所给数组构建图 → 图的遍历 → 判断图中是否存在环

①构建图：
以邻接表形式存储图，

List<Integer>[] graph = new LinkedList[numCourses];

邻接表本质上是由List集合元素组成的数组，为每个图节点创建一个集合，所以数组的长度为 numCourses。
将课程填入其前置课程的邻接表中（其实不太符合正规逻辑，我们通常想的是，学习某课之前需要学习其前置课程，所以将前置课程加入该课程的邻接表中），这样就形成了由前置课程指向课程的有向边。将 numCourses 个集合组织起来，就形成了图。

graph[preCourse].add(course);

②图的遍历 + 判断图中是否存在环：
我们将这两个步骤一起处理。和找图中的所有路径一样，维护两个数组，

boolean[] onPath;
boolean[] visited;

visited 中被标记为 true 的节点用灰色表示，在 onPath 中被标记为 true 的节点用绿色表示

类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景

3.代码

答案代码：

package Graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: LYZ
 * @date: 2022/3/23 19:28
 * @description: 207. 课程表
 */
public class CanFinish {
    public static void main(String[] args) {
        int numCourses = 2;
        int[][] prerequisites = {{0, 1}};
        CanFinish canFinish = new CanFinish();
        boolean ans = canFinish.canFinish(numCourses, prerequisites);
        System.out.println(ans);
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);

        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];

        for (int i = 0; i < numCourses; i++) {
            traverse(graph, i);
        }
        return hasCycle == true ? false : true;
    }

    List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        //创建邻接表存储图
        List<Integer>[] graph = new LinkedList[numCourses];
        //对数组（graph）进行初始化
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }

        for (int[] edge : prerequisites) {
            //提取课程及其先修课程
            int course = edge[0];
            int preCourse = edge[1];
            //为课程以及先修课程创建联系，即创建由先修课程指向课程的有向边
            graph[preCourse].add(course);
        }
        return graph;
    }

    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle = false;
    void traverse(List<Integer>[] graph, int s) {
        if (onPath[s]) {
            hasCycle = true;
        }
        if (visited[s] || hasCycle) {
            return;
        }

        visited[s] = true;
        onPath[s] = true;
        for (int n : graph[s]) {
            traverse(graph, n);
        }
        onPath[s] = false;
    }
}

1、构建邻接表，和之前一样，边的方向表示「被依赖」关系。

2、构建一个 indegree 数组记录每个节点的入度，即 indegree[i] 记录节点 i 的入度。

3、对 BFS 队列进行初始化，将入度为 0 的节点首先装入队列。

4、开始执行 BFS 循环，不断弹出队列中的节点，减少相邻节点的入度，并将入度变为 0 的节点加入队列。

5、如果最终所有节点都被遍历过（count 等于节点数），则说明不存在环，反之则说明存在环。

// 主函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 建图，有向边代表「被依赖」关系
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 构建入度数组
    int[] indgree = new int[numCourses];
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 节点 to 的入度加一
        indgree[to]++;
    }

    // 根据入度初始化队列中的节点
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indgree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.poll();
        count++;
        for (int next : graph[cur]) {
            indgree[next]--;
            if (indgree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

    // 如果所有节点都被遍历过，说明不成环
    return count == numCourses;
}


// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
    // 见前文
}

1. 负环的定义
   负环是指权值和为负数的环。负环会使图的最短路径计算陷入死循环，因此，存在负环的图不存在最短路。

2. 负环的计算方法：
   负环有两种计算方法，都是基于Bellman-Ford算法或者SPFA算法。
   第一种算法是：统计每个点的入队次数，如果某个点入队大于等于n次，则说明有负环
   第二种算法是：统计到某个点的最短路所经过点的个数，如果经过n个点，则说明存在负环。
   (一般情况下，我们使用第二种算法)
   由于当负环存在时，SPFA会陷入死循环，且n是非死循环的最坏情况。所以以上两种算法是正确的。

3. 求负环算法的编程实现
   首先将所有点的距离都赋值为0
   然后将所有的点入队。
   下面说明这两步的正确性：
   
   算法的复杂度分析：
   SPFA算法的理论复杂度为O(m)，但是在实际求负环中算法的复杂度接近O(mn)。这种算法复杂度是比较高的。但是，经验来看，当SPFA的复杂度比较高时，图中大概率存在负环。
   当所有点的入队次数和超过2n时，就认为图中大概率存在负环。