本文共 8805 字，大约阅读时间需要 29 分钟。
这是一个图论总结。
图的概念
·图：由一些点和一些边组成的东西
·有向图：边有方向（单向连通）的图
·无向图：边无方向（双向连通）的图
·入度：有多少边连入这个点
·出度：有多少边连出这个点
·DAG：有向无环图
建图
邻接矩阵
用一个二维数组表示两个点之间有没有连边
s[x][y] = dis; //x和y之间有一条长度为dis的边
邻接表
用一个结构体记录所有的边，同时保存以这条边为起点的上一条边的编号，然后保存所有起点的最后一条边即可。
struct Edge{ int next, to, dis;}e[MAXN * MAXN];int head[MAXN], num;inline void Add(int from, int to, int dis){ e[++num].to = to; e[num].dis = dis; e[num].next = head[from]; head[from] = num;} 图的遍历
·DFS遍历
·BFS遍历
拓扑排序
·定义：拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
1、每个顶点出现且只出现一次。
2、若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
·求法：先把所有入度为\(0\)的点加入队列。当队列不为空时，取出队头并输出，删掉所有以该点为起点的边，并把所有新的入度为\(0\)的点加入队列。重复执行。
queue q;for(int i = 1; i <= n; ++i) if(!in[i]) //in记录入度 q.push(i);while(!q.empty()){ int now = q.front(); q.pop(); printf("%d ", now); for(int i=head[now];i;i=e[i].next) if(!(--in[e[i].to])) q.push(e[i].to);} 最短路
单源最短路
· Dijkstra
创建一个队列，保存“已经确定最短路”的点的集合。初始时队列里只有源点，除源点外所有点的距离赋值正无穷。
当集合不为空时，取出集合内距离最短的一个点，移除集合，枚举这个点连的所有边，如果这个点的距离加上这条边的距离比到的那个点小，那么更新这条边到的那个点的距离，并把它加入集合。重复执行。使用堆优化后时间复杂度
\(O(n\log n)\)。适用于稠密图。
//洛谷 P4779 【模板】单源最短路径（标准版）#include #include #include #include using namespace std;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();} while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar(); return s * w;}const int MAXN = 100010;const int MAXM = 200010; struct Node{ int next, to, dis;}e[MAXM];int head[MAXN], num;ll dis[MAXN];bool v[MAXN];void Add(int from, int to, int dis){ e[++num].to = to; e[num].next = head[from]; e[num].dis = dis; head[from] = num;}int n, m, s;int a, b, c;struct cmp{ bool operator () (int a, int b){ return dis[a] > dis[b]; }};priority_queue
, cmp> q;int main(){ n = read(); m = read(); s = read(); for(i = 1; i <= m; ++i) a = read(), b = read(), c = read(), Add(a, b, c); for(i = 1; i <= n; ++i) dis[i] = INF; dis[s] = 0; q.push(s); while(!q.empty()){ int now = q.top(); q.pop(); if(v[now]) continue; v[now] = true; for(int i = head[now];i;i = e[i].next){ if(!v[e[i].to] && dis[e[i].to] > dis[now] + e[i].dis) dis[e[i].to] = dis[now] + e[i].dis, q.push(e[i].to); } } for(i = 1; i <= n; ++i) printf("%lld ", dis[i]); return 0;}
· SPFA
创建一个队列，初始时队列里只有源点。当队列不为空时，取出队头，和
\(Dijkstra\)一样，枚举所有点，如果能更新距离，更新距离，如果更新的点不在队列里，则加入队列。重复执行。
时间复杂度
\(O(ne)\)，其中
\(e\)为平均每个点进队列的次数，一般图很小，适用于稀疏图，但遇到稠密图时间复杂度会退化为
\(O(nm)\)。还有就是不能跑有负环的图，因此也可以用来判断负环。
//SPFAqueue q;q.push(s); //s为源点 for(int i = 1; i <= n; ++i) dis[i] = INF;dis[s]=0;while(!q.empty()){ int now = q.front(); flag[now] = 0; q.pop(); for(int i = head[now]; i; i = e[i].next){ if(dis[e[i].to] > dis[now] + e[i].dis){ dis[e[i].to] = dis[now] + e[i].dis; if(!flag[e[i].to]) q.push(e[i].to), flag[e[i].to] = 1; } }} 多源最短路
·定义：求任意两点之间的最短路
·Floyd
初始时任意两点之间的距离为正无穷，任意点到自己的距离都为0，枚举所有“中介点”，再枚举所有点对，如果这两个点之间的距离大于起点到中介点再到终点的距离，则更新这两点之间的距离。时间复杂度
\(O(n^3)\)。此算法还可推广到求任意两点之间的连通性。
//Floyd求多源最短路memset(dis, 127, sizeof dis);for(int i = 1; i <= n; ++i) dis[i][i] = 0;for(int k = 1; k <= n; ++k) for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
Tarjan算法
割点
·定义：若将该点及其所有的边删去后，图中剩余点的连通性发生变化，则该点为割点，一张图可能存在多个割点。
·求法（Tarjan）：
定义两个数组：
\(dfn\)（时间戳），
\(low\)（追溯值）
先看一下代码：
void Tarjan(int u,int f){ //vis[x]=1表示x为割点 dfn[u]=low[u]=++id; int Max=0,son=0; for(int i=head[u];i;i=e[i].next){ if(!dfn[e[i].to]){ Tarjan(e[i].to,f); low[u]=min(low[u],low[e[i].to]); if(low[e[i].to]>=dfn[u]&&u!=f) vis[u]=1; if(u==f) ++son; } low[u]=min(low[u],dfn[e[i].to]); } if(u==f&&son>=2) vis[u]=1;} 由代码可知，没访问到一个点就给其分配一个时间戳，\(low\)可理解为“该点能回到的时间戳最小的点的时间戳”。
一个点
\(u\)是割点，当且仅当该点不是根且存在一个有连边的点
\(v\)，满足
\[dfn[u]<=low[v]\] 或者该点是根且存在两个有连边的点满足上述条件。
根据定义，
\(dfn[u]<=low[v]\)时，说明
\(v\)无法到达比
\(u\)更早访问的点，于是把
\(x\)删除后，
\(v\)和
\(u\)的父亲之间无法连通。但如果
\(x\)本来就是根，则无法影响到
\(v\)，所以需要存在两个点满足此条件。
割点（桥）
·定义：若把该边删去后，图的连通性发生变化，则该边为桥。
·求法(Tarjan)：
设一条边连接
\(u,v\)两个点，当
\(dfn[u]<low[v]\)时，该边为桥。
和割点一样，
\(dfn[u]<low[v]\)说明
\(v\)无法到达比
\(u\)或比
\(u\)更早的节点，删除该边后，
\(u\)与
\(v\)“失联”，该边为桥。
强联通分量
·定义：一个图中任意两点能互相到达的极大的子图。“极大”就是指若该子图满足条件，且不存在一个包含这个子图的图满足条件，则该子图就是”极大”。
·求法(Tarjan)：
Tarjan算法时把每个访问的点存到一个栈里，当对当前点的操作完成后判断，如果
\(dfn[u]==low[u]\)，则说明他的所有子节点无法到达比他更早的节点，那么这个点就是这个强联通分量的根，栈中所有在该点之上的点和该点共同构成一个强联通分量。
·缩点：把每个强联通分量看成一个点，重新连边即可。
void Tarjan(int u){ dfn[u] = low[u] = ++ID; s.push(u); vis[u] = 1; for(int i = head[u]; i; i = e[i].next){ if(!dfn[e[i].to]) Tarjan(e[i].to), low[u] = min(low[u], low[e[i].to]); else if(vis[e[i].to]) low[u] = min(low[u], dfn[e[i].to]); } if(dfn[u] == low[u]){ ++sum; int now; do{ now = s.top(); s.pop(); vis[now] = 0; belong[now] = sum; //属于哪个强联通分量 }while(now != u); }} ·缩点的作用：把有环图变为无环图（树）
树
·定义：无向无环图
·链：树上两点之间的唯一路径
树的直径
·定义：树上最长的链
·求法：从任意一个点
\(DFS\)，找到离这个点最远的点，再从那个最远的点
\(DFS\)，找到离那个点最远的点，这两个最远的点之间的路径就是树的直径。
树的重心
见
最小生成树
·定义：一个\(n\)个点图中选\(n-1\)条边使得这张图变成一棵树，且使这\(n-1\)条边的权值和最小。
·求法：
Kruskal
把所有边按权值升序排序，依次枚举所有边，如果这条边连接的两个点没有连通，则把这条边连上，计数器加上这条边的权值，当连了\(n-1\)条边后，算法结束。判断连通性用并茶集。算法时间复杂度\(O(n\log n)\)，其实就是排序的复杂度。
//洛谷 P3366 【模板】最小生成树#include #include using std::sort;const int MAXN = 5010;const int MAXM = 200010;int f[MAXN];int find(int x){ return f[x] == x ? x : f[x] = find(f[x]);}void merge(int x, int y){ f[find(y)] = find(x);}struct Edge{ int x, y, z; bool operator < (const Edge A) const{ return z < A.z; }}e[MAXM];int n, m, ans;int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) f[i] = i; --n; for(int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z); sort(e + 1, e + m + 1); for(int i = 1; i <= m && n; ++i) if(find(e[i].x) != find(e[i].y)) merge(e[i].x, e[i].y), --n, ans += e[i].z; printf("%d\n", ans); return 0;}
次小生成树
见
最近公共祖先（LCA）
·定义：距离树上两个节点最近的同时是两个节点的祖先的点。
·求法：
倍增
用\(f[u][i]\)表示节点\(u\)的第\(2^i\)个父亲， 用倍增转移状态。
查询
\(LCA\)的时候先跳到同一高度，然后跳到同一高度就行。
具体看代码：
int LCA(int u, int v){ if(dep[u] > dep[v]) swap(u, v); int cha = dep[v] - dep[u]; for(int i = 0; i <= LOGMAXN; ++i) if(cha & (1 << i)) v = f[v][i]; if(u == v) return u; for(int i = LOGMAXN; ~i; --i) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; return f[u][0];} 树链剖分(略)
Tarjan离线求LCA
点分治
·作用：快速枚举树上所有链
·方法：
1、找树的重心 -> 2、从重心开始
\(DFS\) -> 3、找所有经过当前点的链 -> 4、对所有子树进行1、2、3号操作，
//洛谷 P2634 聪聪可可#include #include #define re register#define il inlineusing std::max;using std::sort;inline int read(){ int s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * w;}const int MAXN = 20010;struct Edge{ int next, to, dis;}e[MAXN << 1];int head[MAXN], num, n, size[MAXN], vis[MAXN], maxson[MAXN], Max, root, ans, s[5], p[5];inline void Add(int from, int to, int dis){ e[++num].to = to; e[num].next = head[from]; e[num].dis = dis; head[from] = num;}void getRoot(int u, int fa, int tot){ maxson[u] = 0; size[u] = 1; for(re int i = head[u]; i; i = e[i].next){ if(e[i].to != fa && !vis[e[i].to]){ getRoot(e[i].to, u, tot); size[u] += size[e[i].to]; maxson[u] = max(maxson[u], size[e[i].to]); } } maxson[u] = max(maxson[u], tot - size[u]); if(maxson[u] < Max) Max = maxson[u], root = u;}void getADB(int u, int fa, int dep){ if(dep % 3) ans += s[3 - dep % 3]; else ans += s[0] + 1; ++p[dep % 3]; for(re int i = head[u]; i; i = e[i].next) if(e[i].to != fa && !vis[e[i].to]) getADB(e[i].to, u, dep + e[i].dis);}void dfs(int u, int fa){ vis[u] = 1; s[0] = s[1] = s[2] = p[0] = p[1] = p[2] = 0; for(re int i = head[u]; i; i = e[i].next){ if(e[i].to != fa && !vis[e[i].to]) getADB(e[i].to, u, e[i].dis), s[0] += p[0], s[1] += p[1], s[2] += p[2], p[0] = p[1] = p[2] = 0; } for(re int i = head[u]; i; i = e[i].next){ if(!vis[e[i].to]){ Max = n; getRoot(e[i].to, u, size[e[i].to]); dfs(root, u); } }}int A, B, C;int gcd(int a, int b){ return !b ? a : gcd(b, a%b);}int main(){ Max = n = read(); for(re int i = 1; i < n; ++i){ A = read(); B = read(); C = read(); Add(A, B, C); Add(B, A, C); } getRoot(1, 0, n); dfs(root, 0); ans = (ans << 1) + n; int b = n * n; int GCD = gcd(ans, b); ans /= GCD; b /= GCD; printf("%d/%d\n", ans, b); return 0;}
二分图
二分图的判定
·黑白染色法
二分图匹配
·匈牙利算法
网络流