图论：图的环路检测和取环

图论：有向图的环路检测和取环

图的相关概念

顶点

边（有向、无向）

度（入度、出度）

一个顶点如果有一条边指向它，那我们就说这个顶点的入度为1 ；类似地，从顶点出发，有一条边我们就说这个顶点的出度为 1

图的表示

邻接矩阵

假设有 n 个顶点 m 条边的图，声明一个 m * n 的二维数组，G[i][j] = 1 表示 i → j 是连通的

但存在几个问题：

遍历元素时，存在的边和不存在的边都不得不检查一遍，导致遍历效率低。不能存储重复的边。当顶点数量多时，内存空间开销会很大。空间利用率不高。存储无向图时，由于此时矩阵是对称的，而对称位置上的成对元素保存的信息是重复的，导致空间利用率不高。

邻接表

用一个数组adj存储以这个点可以到达的所有顶点，例如：adj[i] = [a, b, c, d] ，adj[i] 可以是一个链表或者数组

图的环路检测方法

并查集

并查集详解 --图文解说,简单易懂(转)

Q & A

为什么需要路径压缩？为什么可以压缩？

最坏的情况下，查找路径可能退化成一条链，极大影响查找效率；

pre 数组并不用存储真正的节点之间的关系，它的作用只有一个，判断任意 2 个节点有没有一个公共祖先；

压缩的几种方式：

按秩合并边查找边合并 什么情况下说明有环？

将要合并的 2 个节点，它们已经拥有公共祖先的时候，说明可能存在环（注意是可能存在 ）

那什么情况下有公共祖先但是也没有环呢？

有向图的情况，要知道有向图的边是有方向的，即使 2 个节点存在公共祖先，也不一定构成环，例如：[ [1,2], [1,3], [2,3] ]

不过下面这道题涉及的只是无向图，因此不用特别处理。

// [https://leetcode-cn.com/problems/graph-valid-tree/](https://leetcode-cn.com/problems/graph-valid-tree/)

// Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]

// Output: true

// Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]

// Output: false

const int maxN = 2010;

int pre[maxN];

int find(int x) {

return x == pre[x] ? x : pre[x] = find(pre[x]); // 路径压缩，边查找边压缩

}

void _union(int x, int y) {

int fx = find(x), fy = find(y);

if (fx != fy) {

pre[fx] = fy;

}

}

class Solution {

public:

bool validTree(int n, vector >& edges) {

for (int i = 0; i < n; i++) {

pre[i] = i;

}

for (int i = 0; i < edges.size(); i++) {

int a = edges[i][0], b = edges[i][1];

if (find(a) == find(b)) {

return false;

}

_union(a, b);

}

// 多个分离的树也不是一棵合法的树

set preSet;

for (int i = 0; i < n; i++) {

preSet.insert(find(i));

}

return preSet.size() == 1;

}

};

拓扑排序

什么是拓扑关系？

举个例子，一门课程都有它的先修课程

用图的方式表示就是:

课程之间的相互关系就是一种拓扑关系。

什么是拓扑序列，如何寻找拓扑序列？

我们知道了任意一门课程的先修课程，如果此时要你来给学生做一张大学四年的课程表，那么这种课程表中课程组成的序列实际上就是一个拓扑序列

具体做法：在有向图中，找出入度为 0 的顶点，将这些顶点放到队列中，依次删除这些顶点及其相关的边，重复上一步，就可以得到一个拓扑序列

// 拓扑排序

// input: [[1,0],[2,0],[3,1],[3,2]]

// output: [0, 1, 2, 3] or [0, 2, 1, 3]

const edges = [[1,0],[2,0],[3,1],[3,2]];

const inDegree = [];

// 求顶点的入度

edges.forEach(edge => {

const [target, source] = edge;

inDegree[target]++;

}

// 找出入度为 0 的顶点

let queue = [];

inDegree.forEach((val, index) => {

if (val === 0) {

queue.push(index)

};

});

const res = [];

while (queue.length) {

const cur = queue.shift();

res.push(cur);

edges.forEach(edge => {

const [target, source] = edge;

if (source === cur) {

inDegree[target]--;

// 新的入度为 0 的顶点，一定在这里产生

if (inDegree[target] == 0) {

queue.push(target);

}

}

})

}

console.log(res)

如果找不到一个入度为 0 的顶点，是否就说明一定存在环？

直觉上是，不过还没找到证明方法。

如何在检测环的同时取出环？

要想取出环，意味着我们需要将整个图至少遍历一遍，比较直接的做法是深度优先遍历

算法讲解：https://www.youtube.com/watch?v=rKQaZuoUR4M

Q & A

为什么要使用 3 种颜色标记节点？

其实相当于剪枝；color 为 2 的节点再也不必访问了

pre 数组是干什么用的？

记录节点的父节点，找到环时，从 dfs 最后一个探访的一个节点出发，依次寻找其父节点，直到形成一个环或者在中途路径断开（也就是说这个节点没有父节点了），到此为止，这个过程就在构造环

复杂度是多少？

假设顶点数量为 V， 边的数量为 E ， 每条边都要走一遍，那么时间复杂度为 O(V+E) ，空间复杂度为 O(V) (实际上我们需要额外的空间保存环结构，所以最坏情况下占用空间应该是 cv1+cv2+…+cvv＝2^v）

存在什么隐患？

图的层级太深会爆栈

JavaScript 版：

// [https://cses.fi/problemset/task/1678](https://cses.fi/problemset/task/1678)

// const n = 4, m = 5;

// const edges = [[1,3], [2,1], [2,4], [3,2], [3,4]];

//const n = 10, m = 20;

//const edges = [[9,8], [2,9],[7,5], [4,5],[1,5],[3,8],[4,2],[5,4],[6,5],[3,6],[8,10],[10,9],[10,7],[9,3],[7,6],[8,7],[7,3],[8,9],[7,10],[2,1]]

const n = 6, m = 7;

const edges = [[1, 2], [2, 3], [3, 1], [1, 4], [4, 6], [6, 5], [5, 4]];

const pre = Array(n + 1).fill(-1);

const color = Array(n + 1).fill(0);

// 建立邻接表

const adj = [[], [], [], [], [], [], [], [], []]; // 不知道为什么，初始化用 Array(n + 1).fill([]) 会报错

edges.forEach(edge => {

const [source, target] = edge;

adj[source].push(target);

});

const cycles = [];

const buildCycle = (start, end) => {

const cycle = [start];

for (let cur = end; cur !== start; cur = pre[cur]) {

cycle.push(cur);

}

cycle.push(start);

cycles.push(cycle.reverse());

}

const dfs = source => {

color[source] = 1;

adj[source].forEach(target => {

if (color[target] === 0) {

pre[target] = source;

dfs(target);

} else if (color[target] === 1) {

// console.log(target, source)

buildCycle(target, source);

}

});

color[source] = 2;

}

for (let v = 1; v <= n; v++) {

if (color[v] === 0) {

dfs(v);

}

}

console.log(cycles)

C++版：

#include

#include

using namespace std;

const int maxN = 1e5+10;

vector color(maxN, 0) , pre(maxN, 0), adj[maxN];

vector > res;

void build_cycle(int start, int end) {

vector cycle;

cycle.push_back(start);

for (int cur = end; cur != start; cur = pre[cur]) {

cycle.push_back(cur);

}

cycle.push_back(start);

vector reversedCycle;

for (int i = cycle.size() - 1; i >= 0; i--) {

reversedCycle.push_back(cycle[i]);

}

res.push_back(reversedCycle);

}

void dfs(int source) {

color[source] = 1;

for (int &target: adj[source]) {

if (color[target] == 0) {

pre[target] = source;

dfs(target);

} else if (color[target] == 1) {

build_cycle(target, source);

}

}

color[source] = 2;

}

int main() {

int n, m;

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

adj[a].push_back(b);

}

for (int i = 1; i <= n; i++) {

if (color[i] == 0) {

dfs(i);

}

}

if (res.size() != 0) {

for (int i = 0; i < res.size(); i++) {

cout << res[i].size() << endl;

for (int j = 0; j < res[i].size(); j++) {

cout << res[i][j] << " ";

}

cout << endl;

}

} else {

cout << "IMPOSSIBLE" << endl;

}

return 0;

}

并查集也可以部分实现，前面提到，对有向图，我们可以特殊处理一下，依然拿这个例子：[ [1,2], [1,3], [2,3] ], 我们首先合并[1,2], [2,3]，此时 [1,2,3]已经在一个集合中，再合并[2,3], 进入构建环的逻辑: 3 入队，再找到 2 的祖先是 1， 将 1 入队，1 的祖先不存在，不构成环，所以可以结束遍历

#include

#include

#include

#include

#include

using namespace std;

const int maxN = 1e5+10;

int pre[maxN];

int pre2[maxN];

vector > res;

// TODO: pre2 这个一维数组并不能处理存在入度大于 1 的顶点的情况，可以改成二维，~~广搜跑一遍~~，不对应该深度优先

void buildCycle(int start, int end) {

vector cycle;

cycle.push_back(start);

for (int cur = end; cur != start; cur = pre2[cur]) {

// 对于入度大于 1 的顶点，也会走到这里，所以需要判断一下查找过程中是不是到尽头了，到了就直接 return

if (cur == -1) {

return;

}

cycle.push_back(cur);

}

cycle.push_back(start);

vector reversedCycle;

for (int i = cycle.size() - 1; i >= 0; i--) {

reversedCycle.push_back(cycle[i]);

}

res.push_back(reversedCycle);

}

int find(int x) {

// cout << "find" << x << endl;

return x == pre[x] ? x : pre[x] = find(pre[x]); // 路径压缩，边查找边压缩

}

// 5 7

// 1 5

// 1 2

// 1 3

// 3 4

// 4 2

// 2 5

// 4 1

void _union(int x, int y) {

if (pre2[y] == -1) pre2[y] = x;

int fx = find(x), fy = find(y);

if (fx != fy) {

pre[fx] = fy;

}

}

int main() {

int n, m;

cin >> n >> m;

for (int i = 0; i <= n; i++) {

pre[i] = i;

pre2[i] = -1;

}

while (m--) {

int a, b;

cin >> a >> b;

if (find(a) == find(b) ) {

buildCycle(b, a);

continue;

}

_union(a, b);

}

if (res.size() != 0) {

for (int i = 0; i < res.size(); i++) {

cout << res[i].size() << endl;

for (int j = 0; j < res[i].size(); j++) {

cout << res[i][j] << " ";

}

cout << endl;

}

} else {

cout << "IMPOSSIBLE" << endl;

}

return 0;

}

这里有一组数据超时主要是因为，题目其实只要找一个环，我的解法为了满足业务上可能的需要，扩充了一下，找所有环，理论上改成只找到一个环就结束，应该是可以 AC 的

TODO：尚不能完美处理存在入度大于 1 的顶点的情况，需要将 pre2 变成二维，再遍历一个节点的所有父节点，目前看广搜深搜都可

应该使用深搜!! 还是不对，广搜其实可以