知识点整理——最小环

前言

近日刷图论题遇到了多道求解最小环的例题，由于方法众多，用法不尽相同，数次被此所困扰。在互联网上寻找良久，却没能发现什么系统性的整理，所以便有了此文。

求解此类问题：

给出一张图，输出图中最小环的大小。定义最小环为：由 \(k(k \ge 3)\) 个点构成的最小的简单环。

标准写法1：\(\tt flody\)

应用极为广泛的做法，本质是求出最短路后暴力枚举。泛用性高、代码短，唯一的缺点是时间复杂度较高，为 \(\mathcal O(N^3)\) 。

模板：

int flody(int n) {
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			val[i][j] = dis[i][j]; // 记录最初的边权值
		}
	}
	int ans = 0x3f3f3f3f;
	for (int k = 1; k <= n; ++ k) {
		for (int i = 1; i < k; ++ i) { // 注意这里是没有等于号的
			for (int j = 1; j < i; ++ j) {
				ans = min(ans, dis[i][j] + val[i][k] + val[k][j]);
			}
		}
	for (int i = 1; i <= n; ++ i) { // 往下是标准的flody
		for (int j = 1; j <= n; ++ j) {
			dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	return ans;
}

有限制的写法：\(\tt bfs\)

本质也是求解最短路，只适用于无边权图。复杂度 \(\mathcal O(N^2)\) 。

int solve(int n) {
	auto bfs = [&] (int s) {
		queue<int> q; q.push(s);
		dis[s] = 0;
		fa[s] = -1;
		while (q.size()) {
			auto x = q.front(); q.pop();
			for (auto y : ver[x]) {
				if (y == fa[x]) continue;
				if (dis[y] == -1) {
					dis[y] = dis[x] + 1;
					fa[y] = x;
					q.push(y);
				}
				else ans = min(ans, dis[x] + dis[y] + 1);
			}
		}
	};
	for (int i = 1; i <= n; ++ i) {
		fill(dis + 1, dis + 1 + n, -1);
		bfs(i);
	}
	return cout << ans;
}

对比算法：\(\tt dfs\)

一句话概括该种写法：能够输出图中其中一个简单环的大小，而不是最小环。本方法在本质上是使用了 \(\tt dfs\) 序加以处理，与 \(\tt tarjan\) 相仿。

时间仓促，直接引用做题时的截图为例，在下图中，最小环为 \(2-6-5-2\) ，而使用 \(\tt dfs\) 会输出 \(2-3-4-5-6-2\) 这个简单环。

虽然这个做法不能找到最小环，但是由于其优秀的复杂度，在某些题目的解题过程中是必不可少的。

function<void(int, int)> dfs = [&] (int x, int f) {
	for (auto y : ver[x]) {
		if (y == f) continue;
		if (dis[y] == -1) {
			dis[y] = dis[x] + 1;
			fa[y] = x;
			dfs(y, x);
		}
		else if (dis[y] < dis[x] && dis[x] - dis[y] <= k - 1) { // 遇到了更小的时间戳
			cout << dis[x] - dis[y] + 1 << endl; // 输出简单环的大小
			int pre = x;
			cout << pre << " "; // 输出环上元素
			while (pre != y) {
				pre = fa[pre];
				cout << pre << " ";
			}
			exit(0);
		}
	}
};
dis[1] = 0;
dfs(1, -1);