玩转图论:轻松检测和提取图中的环路
图论:有向图的环路检测和取环
图的相关概念
顶点
边(有向、无向)
度(入度、出度)
一个顶点如果有一条边指向它,那我们就说这个顶点的入度为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<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
的顶点,将这些顶点放到队列中,依次删除这些顶点及其相关的边,重复上一步,就可以得到一个拓扑序列
// 拓扑排序
// 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<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
的祖先不存在,不构成环,所以可以结束遍历
#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;
// TODO: pre2 这个一维数组并不能处理存在入度大于 1 的顶点的情况,可以改成二维,~~广搜跑一遍~~,不对应该深度优先
void buildCycle(int start, int end) {
vector<int> 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<int> 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
变成二维,再遍历一个节点的所有父节点,目前看广搜深搜都可
应该使用深搜!! 还是不对,广搜其实可以
上一篇: 使用UML建模:如何绘制实用的用例图?
推荐阅读
-
R-FCN 论文理解 - I. R-FCN 入门 1.R-FCN 的贡献 提出位置敏感得分图,解决目标检测的位置敏感问题; 基于区域的全卷积网络框架,用于两阶段目标检测; 比 Faster-RCNN 快 2.5-20 倍(在 K40GPU 上使用 ResNet-101 网络,0.17 秒/图像);。 2.R-FCN 与传统两阶段网络的异同点 图 11 R-FCN 与传统两级网络的异同点 相同点:首先是两个两级检测框架(全卷积子网络+RoI-wise 子网络);其次是最终输出都是相应的类别和相应的 BB;不同点:如上图所示,R-FCN 与 Faster R-CNN 相比,R-FCN 有更深的共享卷积:如上图所示,与 Faster R-CNN 相比,R-FCN 有更深的共享卷积网络层,因此可以获得更多抽象特征;从图中表格可以看出,Faster R-CNN 的共享卷积子网络为 91 层,RoI-wise 子网络为 91 层。RoI-wise子网络为 10 层,而 R-FCN只有深度为 101 层的共享卷积子网络。与 R-CNN 相比,最大的区别在于直接获取整幅图像的特征图,然后提取相应的 ROI,而不是直接在不同的 ROI 上获取相应的特征图。
-
玩转图论:轻松检测和提取图中的环路