首页 > 其他分享 >图论基础

图论基础

时间：2024-08-18 10:16:37浏览次数：14  
标签：图论 int texttt 基础 连通 scc 算法 low

定义与记号

涉及常见或可能用到的概念的定义。关于更多，见参考资料。

基本定义

  • 图：一张图 \(G\) 由若干个点和连接这些点的边构成。称点的集合为 点集 \(V\)，边的集合为 边集 \(E\)，记 \(G = (V, E)\)。
  • 阶：图 \(G\) 的点数 \(|V|\) 称为 阶，记作 \(|G|\)。
  • 无向图：若 \(e \in E\) 没有方向，则称 \(G\) 为 无向图。无向图的边记作 \(e = (u, v)\)，\(u, v\) 之间无序。
  • 有向图：若 \(e \in E\) 有方向，则称 \(G\) 为 有向图。有向图的边记作 \(e = u \to v\) 或 \(e = (u, v)\)，\(u, v\) 之间有序。无向边 \((u, v)\) 可以视为两条有向边 \(u \to v\) 和 \(v \to u\)。
  • 重边：端点和方向（有向图）完全相同的边称为 重边。
  • 自环：连接相同点的边称为 自环。

相邻相关

  • 相邻：在无向图中，称 \(u,v\) 相邻 当且仅当存在 \(e=(u,v)\)。
  • 邻域：在无向图中，点 \(u\) 的 邻域 为所有与之相邻的点的集合，记作 \(N(u)\)。
  • 邻边：在无向图中，与 \(u\) 相连的边 \((u, v)\) 称为 \(u\) 的 邻边。
  • 出边 / 入边：在有向图中，从 \(u\) 出发的边 \(u \to v\) 称为 \(u\) 的 出边，到达 \(u\) 的边 \(v \to u\) 称为 \(u\) 的 入边。
  • 度数：一个点的 度数 为与之关联的边的数量，记作 \(d(u)\)，\(d(u) = \sum_{e \in E} ([u = eu] + [u = ev])\)。每个点的自环对其度数产生 2 的贡献。
  • 出度 / 入度：在有向图中，从 \(u\) 出发的边的数量称为 \(u\) 的 出度，记作 \(d^+(u)\)；到达 \(u\) 的边的数量称为 \(u\) 的 入度，记作 \(d^-(u)\)。

路径相关

  • 途径：连接一串结点的序列称为 途径，用点序列 \(v_0 \cdots v_k\) 和边序列 \(e_1 \cdots e_k\) 描述，其中 \(e_i = (v_{i-1}, v_i)\)。通常写为 \(v_0 \to v_1 \to \cdots \to v_k\)。
  • 迹：不经过重复边的途径称为 迹。
  • 回路：\(v_0 = v_k\) 的迹称为 回路。
  • 路径：不经过重复点的迹称为 路径，也称 简单路径。不经过重复点比不经过重复边强，所以不经过重复点的途径也是路径。注意题目中的简单路径可能指迹。
  • 环：除 \(v_0 = v_k\) 外所有点互不相同的途径称为 环，也称 圈 或 简单环。

连通性相关

  • 连通：对于无向图的两点 \(u, v\)，若存在途径使得 \(v_0 = u\) 且 \(v_k = v\)，则称 \(u, v\) 连通。
  • 弱连通：对于有向图的两点 \(u, v\)，若将有向边改为无向边后 \(u, v\) 连通，则称 \(u, v\) 弱连通。
  • 连通图：任意两点连通的无向图称为 连通图。
  • 弱连通图：任意两点弱连通的有向图称为 弱连通图。
  • 可达：对于有向图的两点 \(u, v\)，若存在途径使得 \(v_0 = u\) 且 \(v_k = v\)，则称 \(u\) 可达 \(v\)，记作 \(u \Rightarrow v\)。
  • 关于点双连通 / 边双连通 / 强连通，见对应章节。

特殊图

  • 简单图：不含重边和自环的图称为 简单图。
  • 基图：将有向图的所有有向边替换为无向边得到的图称为该有向图的 基图。
  • 有向无环图：不含环的有向图称为 有向无环图，简称 \(\texttt{DAG}\)（\(\texttt{Directed Acyclic Graph}\)）。
  • 完全图：任意不同的两点之间恰有一条边的无向简单图称为 完全图。\(n\) 阶完全图记作 \(K_n\)。
  • 树：不含环的无向连通图称为 树。树是简单图，满足 \(|V|=|E|+1\)。若干棵（包括一棵）树组成的连通块称为 森林。相关知识点见 “树论”。
  • 稀疏图 / 稠密图： \(|E|\) 远小于 \(|V|^2\) 的图称为 稀疏图，\(|E|\) 接近 \(|V|^2\) 的图称为 稠密图。这两个概念没有严格定义，用于讨论时间复杂度为 \(O(|E|)\) 和 \(O(|V|^2)\) 的算法。

子图相关

  • 子图：满足 \(V' \subseteq V\) 且 \(E' \subseteq E\) 的图 \(G' = (V', E')\) 称为 \(G = (V, E)\) 的 子图，记作 \(G' \subseteq G\)。
  • 导出子图：选择若干个点以及两端都在该点集的所有边构成的子图称为该图的 导出子图。导出子图的形态仅由选择的点集 \(V'\) 决定，称点集为 \(V'\) 的导出子图为 \(V'\) 导出的子图，记作 \(G[V']\)。
  • 生成子图：\(|V'| = |V|\) 的子图称为 生成子图。
  • 极大子图（分量）：在子图满足某性质的前提下，称子图 \(G'\) 是 极大 的，当且仅当不存在同样满足该性质的子图 \(G''\) 且 \(G' \subset G'' \subseteq G\)。称 \(G'\) 为满足该性质的 分量，如连通分量，点双连通分量。极大子图不能再扩张。例如，极大的连通的子图称为原图的连通分量，也就是我们熟知的连通块。

约定

  • 一般记 \(n\) 表示点集大小 \(|V|\)，\(m\) 表示边集大小 \(|E|\)。

拓扑排序

计算方法

常用的拓扑排序算法包括基于深度优先搜索（\(\texttt{DFS}\)）的方法和基于入度表（\(\texttt{Kahn}\) 算法）的方法。这里，我将描述基于入度表的方法，这种方法利用队列来实现：

  1. 初始化入度表：遍历图中所有的边，统计每个顶点的入度（即指向该顶点的边的数量）。
  2. 将入度为 \(0\) 的顶点入队：所有在图中入度为 \(0\) 的顶点，都可以作为拓扑排序的起点，将它们加入到一个队列中。
  3. 循环执行以下步骤，直到队列为空：
    • 从队列中取出一个顶点 \(u\)（即当前排序的下一个顶点），并将其输出为结果序列的一部分。
    • 遍历从顶点 \(u\) 出发的所有边 \((u, v)\)，将每个相邻顶点 \(v\) 的入度减 \(1\)（表示边 $ (u, v) $ 被移除）。如果某个顶点 \(v\) 的入度降为 \(0\)，则将 \(v\) 入队。

\(\texttt{DAG}\) 的拓扑序性质很好，常用于解决建图题或图论类型的构造题，常常会将图转化为 \(\texttt{DAG}\)，进行 \(\texttt{dp / dfs}\) 求解。

例 1: B3644 【模板】拓扑排序 / 家谱树

题目描述

有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。

第 \(1\) 行一个整数 \(N\)（\(1 \le N \le 100\)），表示家族的人数。接下来 \(N\) 行，第 \(i\) 行描述第 \(i\) 个人的后代编号 \(a_{i,j}\)，表示 \(a_{i,j}\) 是 \(i\) 的后代。每行最后是 \(0\) 表示描述完毕。

输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。

代码

// B3644 【模板】拓扑排序 / 家谱树
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;                                     // 最大顶点数，根据需要修改
int n, x;                                                   // 顶点数
vector<int> Edge[MAXN];                                     // 邻接表表示图
int in_degree[MAXN];                                        // 入度数组
void toposort() {
    queue<int> Q;
    for(int i = 1; i <= n; i++) 
        for(int j : Edge[i]) in_degree[j]++;                // 初始化入度表
    for(int i = 1; i <= n; i++) 
        if(in_degree[i] == 0)  Q.push(i);                   // 将所有入度为0的顶点入队
    while(!Q.empty()) {                                     // 进行拓扑排序
        int u = Q.front(); Q.pop();
        cout << u << " ";                                   // 输出顶点
        for(int i : Edge[u]) {                              // 遍历u的所有邻接点
            in_degree[i]--;
            if(in_degree[i] == 0) 
                Q.push(i);
        }
    }
    cout << endl;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        while (cin >> x && x) 
            Edge[i].push_back(x);
    toposort();
    return 0;
}

最短路问题算法

\(\texttt{Floyd}\) 算法

基本原理

Floyd-Warshall 算法是一种计算图中所有顶点对之间最短路径的算法。

算法流程

  1. 初始化距离矩阵，对角线为0，其他为两点之间的边权重，若无直接边则为无穷大。
  2. 对每个顶点 $k $，更新所有顶点对 $ (i, j) $ 的距离：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。
  3. 重复步骤2，直到所有点都被考虑过。

适用场景

适用于计算任意两点间的最短路径，特别是点数量不是很大时效果好。

代码

void floydWarshall() {
    for (int k = 1; k <= n; k++) 
        for (int i = 1; i <=n; i++) 
            for (int j = 1; j <= n; j++) 
                if (dist[i][k] + dist[k][j] < dist[i][j]) 
                    dist[i][j] = dist[i][k] + dist[k][j];
}

\(\texttt{Dijkstra}\) 算法

基本原理

\(\texttt{Dijkstra}\) 算法用于在加权图中找到一个顶点到其他所有顶点的最短路径。

算法流程

  1. 初始化距离数组，源点距离为 \(0\)，其余为无穷大。
  2. 使用优先队列（或堆）来存储所有节点，优先级为节点的当前距离。
  3. 从队列中取出距离最小的节点，更新其相邻节点的距离。
  4. 重复步骤3，直到队列为空或找到目标节点。

适用场景

适用于无负权边的图。

\(\texttt{SPFA}\) 算法

关于 \(\texttt{SPFA}\), 他 __ 了。

基本原理：
\(\texttt{SPFA}\) 是 \(\texttt{Bellman-Ford}\) 算法的一种改进，用于求解单源最短路径问题。它通过使用队列优化了算法的效率。

算法流程：

  1. 初始化距离数组，源点距离为0，其余为无穷大。
  2. 将源点入队。
  3. 当队列非空时，取出队首元素，遍历其所有出边。
  4. 如果通过当前点可以使得到达某个点的距离更短，则更新距离并将该点入队（如果它当前不在队列中）。
  5. 重复步骤3和4，直到队列为空。

适用场景：
适用于含负权边但无负权回路的图。

\(\texttt{Tarjan}\) 算法

\(\texttt{Trajan}\) 求 \(\texttt{SCC}\)

算法描述

  • \(\texttt{Tarjan}\) 算法用于在有向图中寻找强连通分量（\(\texttt{SCC}\)）。算法通过深度优先搜索（\(\texttt{DFS}\)）遍历图，并利用栈维护访问过的顶点，从而在回溯时能够识别并构成强连通分量。

代码解释

  • s.push(x), vis[x] = 1;：当前顶点 x 入栈，并标记为已访问。
  • dfn[x] = low[x] = ++tim;：为顶点 x 分配一个访问编号和最小可回溯编号。
  • 遍历 x 的每个邻接顶点 i：
    • 如果 i 未被访问（!dfn[i]），递归调用 tarjan(i)，并更新 x 的 low 值。
    • 如果 i 已在栈中（vis[i]），则更新 x 的 low 值。
  • 如果 dfn[x] == low[x]，说明找到了一个强连通分量的根节点：
    • 通过循环将栈中的元素出栈，直到遇到 x，同时为出栈的顶点分配相同的强连通分量编号，并累加对应的值。

复杂度分析

  • 时间复杂度：\(O(V + E)\)，其中 \(V\) 是顶点数，\(E\) 是边数。
  • 空间复杂度：\(O(V)\)，主要是用于存储栈、访问标记、时间戳等信息。

通过这个函数实现，\(\texttt{Tarjan}\) 算法能有效地在有向图中识别所有的强连通分量，并能处理每个分量的累计值问题。希望这样的笔记能帮助您更好地理解和使用 \(\texttt{Tarjan}\) 算法。

代码

void tarjan(int x) {
	s.push(x), vis[x] = 1;
	dfn[x] = low[x] = ++tim;
	for (int i : Edge[x]) {
		if (!dfn[i]) {
			tarjan(i);
			low[x] = min(low[x], low[i]);
			low[x] = min(low[x], dfn[i]);
		} else if (vis[i]) {
			low[x] = min(low[x], dfn[i]);
			low[x] = min(low[x], low[i]);
		}
	}

	if (dfn[x] == low[x]) {
		++count_scc;
		while (s.top() != x) {
			color[s.top()] = count_scc;
			sum[count_scc] += val[s.top()];
			vis[s.top()] = false;
			s.pop();
		}
		color[s.top()] = count_scc;
		sum[count_scc] += val[s.top()];
		vis[s.top()] = false;
		s.pop();
	}
}

例 1: CF949C Data Center Maintenance

题意

题意 : \(n\) 个点，每个点有一个值 \(a_i\)。\(m\) 条边，每个条边链接 \(2\) 个点 \(x，y\) 使得 \(a_x \not =a_y\)。选择最少的 \(k(1 \le k \le n)\) 个点，使 \(a_i = (a_i + 1) \mod h\)，\(m\) 个条件仍成立。

题解

  1. 对于每一条边，如果 \(x_i = y_i + 1\) 则把 \(x_i\) 向 \(y_i\) 连一条边
  2. 缩点
  3. \(\texttt{DAG}\) 上跑没有出度权值最小的点。

代码

#include <bits/stdc++.h>
#define int long long
#define debug(x) cerr << #x << " " << x << '\n';
#define multi false
using namespace std;
const int N = 1e5 + 10;
int t = 1, n, m, h, x, y, tim, scc_count, ansid;
int val[N], dfn[N], low[N], vis[N], color[N], siz[N];
stack <int> s;
vector <int> Edge[N];
vector <int> scc[N];
void tarjan (int x) {
	vis[x] = 1; s.push(x);
	dfn[x] = low[x] = ++tim;
	for (int i : Edge[x]) {
		if (!dfn[i]) {
			tarjan(i);
			low[x] = min(low[x], low[i]);
			low[x] = min(low[x], dfn[i]);
		} else if (vis[i]) {
			low[x] = min(low[x], low[i]);
			low[x] = min(low[x], dfn[i]);
		}
	}
	if (low[x] == dfn[x]) {
		scc_count++;
		while (s.top() != x) {
			color[s.top()] = scc_count;
			vis[s.top()] = 0;
			siz[scc_count]++; 
			s.pop();
		}
		color[s.top()] = scc_count;
		vis[s.top()] = 0;
		siz[scc_count]++; 
		s.pop();
	}
	return;
}
void solve() {
	cin >> n >> m >> h;
	for (int i = 1; i <= n; i++) cin >> val[i];
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		if ((val[x] + 1) % h == val[y]) Edge[x].push_back(y);
		if (val[x] == (val[y] + 1) % h) Edge[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) 
		if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++)
		for (int j : Edge[i])
			if (color[i] != color[j])
				scc[color[i]].push_back(color[j]);
	for (int i = 1; i <= scc_count; i++) 
		if (scc[i].size() == 0 && (siz[i] < siz[ansid] || ansid == 0))
			ansid = i;
	cout << siz[ansid] << '\n';
	for (int i = 1; i <= n; i++)
		if (color[i] == ansid)
			cout << i << ' ';
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (multi) cin >> t;
    while (t--) solve();
	return 0;
}

\(\texttt{Trajan}\) 缩点

算法描述

  1. 求出所有的 \(\texttt{SCC}\)。
  2. 对于每个 \(\texttt{SCC}\)，把所有的点缩成一个点。并求出其权值(这个是要根据题意来的，比如例题是求 \(\texttt{SCC}\) 的权值和)。
  3. 对于原图中的每一条边，如果这条边连接的两个点不在同一个 \(\texttt{SCC}\) 中，则把这条边连到两个 \(\texttt{SCC}\) 上。
  4. 对于缩点后的图，形成了一个 \(\texttt{DAG}\)。

例1: P3387

题意

给定一个 \(n\) 个点 \(m\) 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。

允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。

题解

  1. 求出所有的 \(\texttt{SCC}\)。
  2. 对于每个 \(\texttt{SCC}\)，把所有的点缩成一个点，并求出其权值和。
  3. 对于原图中的每一条边，如果这条边连接的两个点不在同一个 \(\texttt{SCC}\) 中，则把这条边连到两个 \(\texttt{SCC}\) 上。
  4. 对于缩点后的图，形成了一个 \(\texttt{DAG}\)。
  5. 在 \(\texttt{DAG}\) 上跑 \(\texttt{DP}\)，求出路径经过的点权值之和的最大值。

代码

#include <bits/stdc++.h>
#define int long long
#define debug(x) cerr << #x << " " << x << '\n';
#define multi false
using namespace std;
const int N = 1e5 + 10;
const int M = 1e5 + 10;
int t = 1, n, m, tim, count_scc, ans;
int x[M], y[M], val[N], color[N], sum[N], f[N];
int vis[N], low[N], dfn[N];
vector <int> Edge[N];
vector <int> scc[N]; // scc edge
stack <int> s;
void tarjan(int x) {
	s.push(x), vis[x] = 1;
	dfn[x] = low[x] = ++tim;
	for (int i : Edge[x]) {
		if (!dfn[i]) {
			tarjan(i);
			low[x] = min(low[x], low[i]);
			low[x] = min(low[x], dfn[i]);
		} else if (vis[i]) {
			low[x] = min(low[x], dfn[i]);
			low[x] = min(low[x], low[i]);
		}
	}

	if (dfn[x] == low[x]) {
		++count_scc;
		while (s.top() != x) {
			color[s.top()] = count_scc;
			sum[count_scc] += val[s.top()];
			vis[s.top()] = false;
			s.pop();
		}
		color[s.top()] = count_scc;
		sum[count_scc] += val[s.top()];
		vis[s.top()] = false;
		s.pop();
	}
}
int dfs(int x) {
	if (f[x]) return f[x];
	f[x] = sum[x];
	for (int i : scc[x]) 
		f[x] = max(f[x], dfs(i) + sum[x]);
	return f[x];
}
void solve() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> val[i];
	for (int i = 1; i <= m; i++) {
		cin >> x[i] >> y[i];
		Edge[x[i]].push_back(y[i]);
	}
	for (int i = 1; i <= n; i++) 
		if (!dfn[i]) 
			tarjan(i);
	for (int i = 1; i <= m; i++) 
		if (color[x[i]] != color[y[i]])
			scc[color[x[i]]].push_back(color[y[i]]);
	for (int i = 1; i <= n; i++) 
		ans = max(ans, dfs(i));
	cout << ans << '\n';
    return;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    if (multi) cin >> t;
    while (t--) solve();
	return 0;
}

参考资料

施工进度

标签：图论,int,texttt,基础,连通,scc,算法,low
From： https://www.cnblogs.com/kimi0705/p/18364227

相关文章

  • 【时时三省】(C语言基础)调试技巧2
    山不在高，有仙则名。水不在深，有龙则灵。             ----CSDN时时三省多多动手，尝试调试，才能有进步。•一定要熟练掌握调试技巧。•初学者可能80%的时间在写代码，20%的时间在调试。但是一个程序员可能20%的时间在写程序，但是80%的时间在调试。•我......
  • 算法刷题记录 八十五【图论的广度优先搜索理论基础】
    前言图论章节第2篇。第1篇：记录八十二【图论理论基础及深度优先搜索算法】；本文：记录八十五【图论的广度优先搜索理论基础】一、广度优先搜索理论基础广度优先搜索理论基础参考链接1.1知识点框架1.2模拟广度搜索的过程在有向图中，以下图为例，如何进行广度优先搜索......
  • 013、Vue3+TypeScript基础，computed计算属性的使用，结果会被缓存
    01、App.vue代码如下：<template><divclass="app"><h2>{{title}}</h2><!--使用了ref来获取子组件的属性--><Person/></div></template><scriptlang="ts"setupname="App"......
  • [Java基础]Set
    Set集合有什么特点？如何实现key无重复的？set集合特点：Set集合中的元素是唯一的，不会出现重复的元素。set实现原理：Set集合通过内部的数据结构（如哈希表、红黑树等）来实现key的无重复。当向Set集合中插入元素时，会先根据元素的hashCode值来确定元素的存储位置，然后再通过equals方法来判断......
  • Linux基础知识学习（一）
    一.简介Linux内核最初只是由芬兰人林纳斯·托瓦兹（LinusTorvalds）在赫尔辛基大学上学时出于个人爱好而编写的。Linux是一套免费使用和自由传播的类Unix操作系统，是一个基于POSIX（可移植操作系统接口）和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。Linux能运......
  • VUE基础
    1.VUE简介它是一个构建用户界面的框架Vue是一个前端框架jsjqVue(发音为/vjuː/，类似view)是一款用于构建用户界面的JavaScript框架。它基于标准HTML、CSS和JavaScript构建，并提供了一套声明式的、组件化的编程模型，帮助你高效地开发用户界面。无论是简单还是复杂的......
  • 【面试宝典】java基础面试题总结[上]
    一、Java中有几种基本数据类型？各占多少字节？在Java中基本数据类型有8个，占用的字节分别是整型byte（1个字节）、short（2个字节）、int（4个字节）、long（8个字节）；浮点型float（4个字节）、double（8个字节）；布尔类型boolean；字符类型char(2个字节)。二、String类能被继承吗？为什么？Stri......
  • 012、Vue3+TypeScript基础，子页面使用defineExpose暴露成员来给主页面使用
    01、App.vue代码如下：<template><divclass="app"><h2>{{title}}</h2><button@click="showLog">点我数组子页面年龄</button><!--使用了ref来获取子组件的属性--><Personref="person001"/......
  • 二分查找不理解？一篇弄懂！--基础二分查找算法详细解释(带简单例题的详细解法)
    本文参考:灵茶山艾府分享丨【题单】二分算法（二分答案/最小化最大值/最大化最小值/第K小）-力扣（LeetCode）二分查找红蓝染色法_哔哩哔哩_bilibili本文主要详细讲解基础的二分算法中的查找，包括原理和模板，并用leetcode和洛谷的一些例题来进行实际题目讲解，如果觉得有帮助或者写......
  • 011、Vue3+TypeScript基础，template中ref的用法意义
    1、如果多个页面都用同一个id，那么就会报错。用ref可以指明是某个元素，规避报错情况。App.vue代码如下：<template><divclass="app"><h2ref="title2">好好学习，天天向上</h2><button@click="showLog">点我输出h2元素</button><Person/&g......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99