图论:有向图的环路检测和取环 图的相关概念 顶点 边(有向、无向) 度(入度、出度) 一个顶点如果有一条边指向它,那我们就说这个顶点的入度为1
;类似地,从顶点出发,有一条边我们就说这个顶点的出度为 1
图的表示 邻接矩阵
假设有 n
个顶点 m
条边的图,声明一个 m * n
的二维数组,G[i][j] = 1
表示 i → j
是连通的
但存在几个问题:
遍历元素时,存在的边和不存在的边都不得不检查一遍,导致遍历效率低。
不能存储重复的边。
当顶点数量多时,内存空间开销会很大。
空间利用率不高。
存储无向图时,由于此时矩阵是对称的,而对称位置上的成对元素保存的信息是重复的,导致空间利用率不高。
邻接表
用一个数组adj
存储以这个点可以到达的所有顶点,例如:adj[i] = [a, b, c, d]
,adj[i]
可以是一个链表或者数组
数表中关联字段 cellValue 的结构实际上也可以看成一种邻接表(从一个 id 出发,关联了一个 id 数组): id → reocod → linkfield → cellvalue [id1, id2, id3]
图的环检测方法 并查集 并查集详解 –图文解说,简单易懂(转)
Q & A
为什么需要路径压缩?为什么可以压缩? 最坏的情况下,查找路径可能退化成一条链,极大影响查找效率; pre
数组并不用存储真正的节点之间的关系,它的作用只有一个,判断任意 2
个节点有没有一个公共祖先; 压缩的几种方式:
按秩合并
边查找边合并
什么情况下说明有环? 将要合并的 2
个节点,它们已经拥有公共祖先的时候,说明可能存在环(注意是可能存在
)
那什么情况下有公共祖先但是也没有环呢? 有向图
的情况,要知道有向图的边是有方向的,即使 2
个节点存在公共祖先,也不一定构成环,例如:[ [1,2], [1,3], [2,3] ]
不过下面这道题涉及的只是无向图,因此不用特别处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 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<vector<int > >& 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<int > preSet; for (int i = 0 ; i < n; i++) { preSet.insert (find (i)); } return preSet.size () == 1 ; } };
拓扑排序 什么是拓扑关系?
举个例子,一门课程都有它的先修课程
用图的方式表示就是:
课程之间的相互关系就是一种拓扑关系
。
什么是拓扑序列,如何寻找拓扑序列?
我们知道了任意一门课程的先修课程,如果此时要你来给学生做一张大学四年的课程表,那么这种课程表中课程组成的序列实际上就是一个拓扑序列
具体做法:在有向图中,找出入度为 0
的顶点,将这些顶点放到队列中,依次删除这些顶点及其相关的边,重复上一步,就可以得到一个拓扑序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 const edges = [[1 ,0 ],[2 ,0 ],[3 ,1 ],[3 ,2 ]];const inDegree = [];edges.forEach(edge => { const [target, source] = edge; inDegree[target]++; } 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]--; 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 版:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 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 = [[], [], [], [], [], [], [], [], []]; 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 ) { buildCycle(target, source); } }); color[source] = 2 ; } for (let v = 1 ; v <= n; v++) { if (color[v] === 0 ) { dfs(v); } } console .log(cycles)
C++版:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 #include <iostream> #include <vector> using namespace std;const int maxN = 1e5 +10 ;vector<int> color(maxN, 0) , pre(maxN, 0), adj[maxN]; vector<vector<int > > res; void build_cycle (int start, int end) { vector<int > cycle; cycle.push_back (start); for (int cur = end; cur != start; cur = pre[cur]) { cycle.push_back (cur); } cycle.push_back (start); vector<int > 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
的祖先不存在,不构成环,所以可以结束遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 #include <iostream> #include <vector> #include <cmath> #include <set> #include <algorithm> using namespace std;const int maxN = 1e5 +10 ;int pre[maxN];int pre2[maxN];vector<vector<int > > res; void buildCycle (int start, int end) { vector<int > cycle; cycle.push_back (start); for (int cur = end; cur != start; cur = pre2[cur]) { if (cur == -1 ) { return ; } cycle.push_back (cur); } cycle.push_back (start); vector<int > reversedCycle; for (int i = cycle.size () - 1 ; i >= 0 ; i--) { reversedCycle.push_back (cycle[i]); } res.push_back (reversedCycle); } int find (int x) { return x == pre[x] ? x : pre[x] = find (pre[x]); } 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
变成二维,再遍历一个节点的所有父节点,目前看广搜深搜都可
应该使用深搜!! 还是不对,广搜其实可以