图论学习笔记
最后一次编辑于2019年8月15日上午11点18分
最小生成树
Kruskal
\(kruskal\)，一种求最小生成树的算法，其思想与贪心有些相似，具体做法为：
将边按照边权由小到大排序，每次拿出权值最小的一条边，看它连接的两个顶点是否在同一个连通块中（可以用并查集维护），如果在的话就不使用他，否则就加入生成树，一直加入到边数为\(n - 1\)结束
如何证明？
要我说我也说不明白，还是直接上图吧
图片来自：https://blog.csdn.net/weixin_43272781/article/details/83589394
复杂度：\(O(mlogm)\)
代码实现：
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x <<3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 5011;
const int M = 200011;
struct node {
int x, y, val;
} a[M];
int n, m, k, fa[N], ans = 0;
bool cmp(node a, node b) {
return a.val < b.val;
}
inline int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= m; i++) {
a[i].x = read(), a[i].y = read(), a[i].val = read();
}
stable_sort(a + 1, a + 1 + m, cmp);
for(int i = 1; i <= m; i++) {
int dx = find(a[i].x), dy = find(a[i].y);
if(find(dx) != find(dy)) {
fa[dx] = fa[dy];
ans += a[i].val;
k++;
}
if(k == n - 1) break;
}
cout << ans << '\n';
return 0;
}Prim
同样是一种求最小生成树的算法，也用到了贪心的思想，具体做法是：
随便找一个点作为一棵树的根节点，然后找出和它相邻的边（这里邻接表存储，用一遍循环即可），使用一条边扩展这个树，要求这条边一个顶点在树中，另一 个顶点不在树中，并且这条边的权值要求最小。重复以上的步骤，同时维护一个\(dis\)数组，表示为已用点到未用点的最短距离。
证明：\(Prim\)算法之所以是正确的，主要基于一个判断：对于任意一个顶点\(v\)，连接到该顶点的所有边中的一条最短边\((v, v_j)\)必然属于最小生成树（即任意一个属于最小生成树的连通子图，从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树）
复杂度：\(O(elog_2v)\)
来自：https://www.cnblogs.com/bcoier/p/10293059.html
代码实现如下：
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int INF = 1e10 + 11;
const int N = 5011;
const int M = 200011;
struct node {
int to, next, val;
} e[M << 1];
int head[N], dis[N], cnt;
int n, m, k, now = 1, ans = 0;
bool vis[N];
inline void add(int from, int to, int val) {
e[++cnt].to = to;
e[cnt].val = val;
e[cnt].next = head[from];
head[from] = cnt;
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; i++) {
int x = read(), y = read(), w = read();
add(x, y, w), add(y, x, w);
}
for(int i = 2; i <= n; i++) dis[i] = INF;
for(int i = head[1]; i; i = e[i].next) dis[e[i].to] = min(dis[e[i].to], e[i].val);
while(++k < n) {
int minn = INF;
vis[now] = 1;
for(int i = 1; i <= n; i++) {
if(!vis[i] && minn > dis[i]) {
minn = dis[i];
now = i;
}
}
ans += minn;
for(int i = head[now]; i; i = e[i].next) {
int v = e[i].to;
if(dis[v] > e[i].val && !vis[v]) {
dis[v] = e[i].val;
}
}
}
cout << ans << '\n';
return 0;
}练习题
建立一个超级源点，将它往每个点建一条边权为\(wi\)的边，跑最小生成树即可
建一个最大生成树，然后跑树上倍增
菜死我了，还没看
最短路
Floyd
这个就不多说了吧……求多源最短路，四行代码搞定，复杂度\(O(N^3)\)
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]);另外说一下，用玄学优化是可以让\(floyd\)跑过最短路这个题的！
//早期代码没空格hhh
#include<bits/stdc++.h>
using namespace std;
long long g[1010][1010];
long long n,m,a,b,s;
int qread()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main() {
n=qread();m=qread();
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
g[i][j]=0xffffff;
}
}
for(int i=1; i<=m; ++i) {
a=qread();b=qread();s=qread();
g[a][b]=s;
}
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
if(i!=k && g[i][k]!=0xffffff) {
for(int j=1; j<=n; j++) {
if(i!=j&&j!=k&&g[i][j]>g[i][k]*g[k][j]) {
g[i][j]=g[i][k]*g[k][j];
}
}
}
printf("%lld",g[1][n]%9987);
return 0;
}Dijkstra
\(Dijkstra\)用于求单源最短路径，他是比较优秀的最短路算法，但是不能处理负边权，不做详细介绍
普通版本
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 5011;
int n, m, ans;
int dis[N], a[N][N];
bool vis[N];
int main() {
memset(a, 0x3f, sizeof(a));
n = read(), m = read();
for(int i = 1, u, v, w; i <= m; i++) {
u = read(), v = read(), w = read();
a[u][v] = a[v][u] = w;
}
for(int i = 0; i <= n; i++) dis[i] = a[1][i];
vis[1] = 1;
dis[1] = 0;
for(int i = 1; i <= n; i++) {
int k = 0;
for(int j = 1; j <= n; j++) {
if(!vis[j] && dis[j] < dis[k]) {
k = j;
}
}
vis[k] = 1;
for(int j = 1; j <= n; j++) {
if(dis[j] > dis[k] + a[k][j]) {
dis[j] = dis[k] + a[k][j];
}
}
}
cout << dis[n] << '\n';
return 0;
}堆优化
typedef pair<int,int> pairs;
priority_queue<pairs,vector<pairs>,greater<pairs> >q ;
int dis[100007],head[100007];
bool vis[100007];
inline void dijkstra(){
memset(dis,0x3f,sizeof dis);
dis[s]=0;
q.push(make_pair(dis[s],s));
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
if(dis[x]+edge[i].w<dis[to]){
dis[to]=dis[x]+edge[i].w;
q.push(make_pair(dis[to],to));
}
}
}
}SPFA
一个最可怕的最短路算法，因为它的复杂度是错的，甚至很多人都说，\(SPFA\)已经死了，实在是可怕啊
不过\(SPFA\)可以判断负环，这是好的
平常没有负边权还是不要写\(SPFA\)，好好写\(Dijkstra\)吧
SPFA判负环
queue <int> q;
bool inq[N];
int dis[N], len[N];
bool spfa() {//true表示有环
for(int i = 2; i <= n; i++) dis[i] = INF;
len[1] = 1;
q.push(1);
inq[1] = true;
while(!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
int w = W[u][i];
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
len[v] = len[u] + 1;
if(len[v] >= n) return true;
if(!inq[v]) q.push(v), inq[v] = true;
}
}
}
return false;
}练习题
\(floyd\)优化版，按时间走就行了
拓扑排序
给定一张有向图，要求输出一个满足以下条件的结点序列：
如果图中\(u\)到\(v\)有一条有向边，那么在序列中\(v\)在\(u\)的后面
如果这个序列存在，就说明图中没有环
怎么求？
声明一个结点队列\(q\)
\(①\) 将所有入度为\(0\)的结点加入\(q\)
\(②\)每次从队列中取出第一个结点\(u\)，将\(u\)从图中删除（让所有\(u\)连向的结点\(v\)入度\(--\)）。如果结点\(v\)此时入度变为\(0\)，则v入队。
重复\(②\)直到队列为空
如果所有结点都入过队，原图没有环，结点按出队的顺序排列是一个合法的拓扑序； 否则原图有环，无解。
无优化版
//topsort O(n^2)
int ind[N]/*每个点的入度*/, seq[N]/*拓扑序*/, cnt;
bool vis[N];
bool topsort() { //有环返回false
while(true) {
if(cnt == n) return true;
int k = 0;
for(int i = 1; i <= n; i++) {
if(!vis[i] && ind[i] == 0) {
k = i;
break;
}
}
if(k == 0) return false;
seq[++cnt] = k;
vis[k] = true;
for(int i = 0; i < e[k].size(); i++) {
int u = e[k][i];
--ind[u];
}
}
}队列优化
//队列优化topsort O(n + m)
queue <int> q;
int ind[N], seq[N], cnt;
bool topsort() { //有环返回false
for(int i = 1; i <= n; i++) if(!ind[i]) q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
seq[++cnt] = u;
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
--ind[v];
if(ind[v] == 0) q.push(v);
}
}
return cnt == n;
} 强连通分量
一些概念
强连通：在一个有向图\(G\)中，如果两个顶点间至少存在一条路径，称两个顶点强连通（\(strongly\ connected\)）。
强连通图：如果有向图\(G\)的每两个顶点都强连通，则称\(G\)是一个强连通图。
强连通分量（\(SCC\)）：非强连通图有向图的极大强连通子图，成为强连通分量（\(strongly\ connected\ components\)），强连通分量中，任意两个顶点之间都有相互可达的路径
Tarjan算法
如何求\(SCC\)呢？，这就需要用到一个叫做\(Tarjan\)的算法了
记录两个数组：
\(dfn[]\) (表示这个点是第几个被搜到的)
\(low[]\) (每个点及其搜索树子树中的点中能访问到的点\(dfn\)的最小值)
容易发现\(low\)相同的一批点在同一个强连通分量中
因此我们可以在每个\(dfn==low\)的结点将其强连通分量提取出来
算法实现
一些数组
\(dfn[]\) ，表示这个点是第几个被搜到的
\(low[]\) ，表示每个点及其搜索树子树中的点中能访问到的点\(dfn\)的最小值
\(stack[]\)，表示当前所有可能能构成强连通分量的点。
\(vis[]\)，表示一个点是否在\(stack[]\)数组中。
假设现在开始遍历点\(u\)：
首先初始化\(dfn[u]=low[u]=\)第几个被\(dfs\)到
将\(u\)存入\(stack[]\)中，并将\(vis[u]\)设为\(true\)
遍历\(u\)的每一个能到的点，如果这个点\(dfn[ ]\)为\(0\)，即仍未访问过，那么就对点\(v\)进行\(dfs\)，然后\(low[u]=min{low[u],low[v]}\)
假设我们已经\(dfs\)完了\(u\)的所有的子树，那么之后无论我们再怎么\(dfs\)，\(u\)点的\(low\)值已经不会再变了。
节选自洛谷日报：https://www.luogu.org/blog/styx-ferryman/chu-tan-tarjan-suan-fa-qiu-qiang-lian-tong-fen-liang-post
代码实现：
void tarjan(int u) {
dfn[u] = low[u] = ++ dfsnum;
vis[u] = 1;
stack[++top] = u;
int sz = e[u].size();
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}
else {
if(vis[v]) low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]) {
col[u] = ++sum;
vis[u] = 0;
while(stack[top] != u) {
col[stack[top]] = sum;
vis[stack[top--]] = 0;
}
top--;
}
}那么扫一遍就结束了吗，就能遍历整个图了吗？不一定。
为了防止有的点没有遍历到，我们这样写
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}这样就OK啦！
缩点
由于强连通分量中的点可以相互到达，有时将强连通分量看成一个点会比较好处理。
具体方法
用\(tarjan\)求出强连通分量，建立一个新图，新图中每个点为原图的一个强连通分量。两个点之间有边当且仅当原图中两个对应的强连通分量内的点之间有边
代码
来自调了大半天的洛谷P3387的恶臭代码（***************************）
//缩点 + DP
#include <cstdio>
#include <cstring>
#define min(a,b) (a>b?b:a)
#define max(a,b) (a<b?b:a)
const int M = 10111;
const int N = 100111;
struct node {
int to, nxt;
} e[N];
int n, m;
int cnt = 0, tot = 0, num = 0;
int dfn[M], low[M], x[N], y[N], head[M], st[M], top, vis[M], a[M];
int col[M], val[N];
inline void add(int from, int to) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void tarjan(int now) {
dfn[now] = low[now] = ++tot;
st[++top] = now;
vis[now] = 1;
for(int i = head[now]; i != -1; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) tarjan(v), low[now] = min(low[now], low[v]);
else if(vis[v]) low[now] = min(low[now], dfn[v]);
}
if(dfn[now] == low[now]) {
num++;
while(st[top + 1] != now) {
col[st[top]] = num;
vis[st[top]] = 0;
val[num] += a[st[top]];
top--;
}
}
}
int f[M];
int ans = 0;
void dp(int now) {
for(int i = head[now]; i != -1; i = e[i].nxt) {
int v = e[i].to;
if(!f[v]) dp(v);
f[now] = max(f[now], f[v]);
}
f[now] += val[now];
}
int main() {
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);//n = read(), m = read();
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);//a[i] = read();
for(int i = 1; i <= m; i++) {
scanf("%d%d", &x[i], &y[i]);//x[i] = read(), y[i] = read();
add(x[i], y[i]);
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i);
}
memset(head, -1, sizeof(head));
cnt = 0;
for(int i = 1; i <= m; i++) {//强连通分量之间连边
if(col[x[i]] != col[y[i]]) {
add(col[x[i]], col[y[i]]);
}
}
//DP过程
for(int i = 1; i <= num; i++) {
if(!f[i]) {
dp(i);
ans = max(ans, f[i]);
}
}
printf("%d", ans);
return 0;
}另外提供某亲爱的学长压行后送回的代码，不得不说好看极了
#include <cstdio>
#include <cstring>
#include <complex>
const int M = 10111;
const int N = 100111;
struct node {int to, nxt;} e[N];
int n, m, cnt, tot, num;
int dfn[M], low[M], x[N], y[N], head[M], st[M], top, vis[M], a[M];
int col[M], val[N], f[M], ans;
void add(int from, int to) {
e[++cnt].to = to;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void tarjan(int now) {
dfn[now] = low[now] = ++tot; st[++top] = now; vis[now] = 1;
for(int i = head[now]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) tarjan(v), low[now] = min(low[now], low[v]);
else if(vis[v]) low[now] = min(low[now], dfn[v]);
}
if(dfn[now] == low[now]) {
num++;
while(st[top + 1] != now) {
col[st[top]] = num;
vis[st[top]] = 0;
val[num] += a[st[top]];
top--;
}
}
}
void dp(int now) {
for(int i = head[now]; i; i = e[i].nxt) {
int v = e[i].to;
if(!f[v]) dp(v);
f[now] = max(f[now], f[v]);
}
f[now] += val[now];
ans = max(ans, f[now]);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= m; i++) scanf("%d%d", &x[i], &y[i]), add(x[i], y[i]);
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
memset(head, 0, sizeof(head)); cnt = 0;
for(int i = 1; i <= m; i++) if(col[x[i]] != col[y[i]]) add(col[x[i]], col[y[i]]);
for(int i = 1; i <= num; i++) if(!f[i]) dp(i);
printf("%d", ans); return 0;
}
练习题
tarjan缩点，看出度为0的点有几个，如果只有一个输出这个强连通分量中的点个数，否则就不行
缩点，再贿赂贿赂就行了（hhhhhhhhhh）
环套树/基环树
我们知道，树是最简单的连通无向图，并且树中任意两点之间有且只有一条路径
那么什么是环套树/基环树呢？
其实就是在树上加了一条边的图，让图上多了个环
设加的一条边为\((u,v)\)，那么由之前\(u,v\)间有一条路径，加了这条边之后这条路径和这条边构成一个环，这也是形成的唯一一个环
找到环的位置很重要
那么怎么找？
- 随意找一个点开始当成树进行\(dfs\)，并记录每个结点访问的时间戳\(dfn\)
- \(dfs\)的过程中一定会有一个点往\(dfn\)比自己小的点连了边，那么这条边可以看成加上的那条。记录下这条边\((u,v)\)
- 暴力让\(u\)和\(v\)往上爬到根，记录他们分别经过的点。
- 深度最大的他们都经过的点为他们的\(lca\)，\(u->lca\)之间的所有点+\(v->lca\)之间的所有点即构成环。
找环方法1
int fa[N]; //f[i]为i在搜索树中的父亲结点
bool in[N], vis[N]; //表示i是否在环中
int cir[N], cnt;
int x, y;
void dfs(int u, int f) { //f为u的父亲结点
fa[u] = f;
vis[u] = 1;
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
if(v == f) continue;
if(vis[v]) x = u, y = v;
else dfs(v, u);
}
}
void solve() { //x到y一定是返祖边
dfs(1, 0);
while(x != y) {
cir[++cnt] = x;
x = fa[x];
}
cir[++cnt] = y;
}找环方法2
//求基环树的环 方法2
queue <int> q;
int deg[N], n;
int cir[N], cnt;
bool in[N]; //是否在环中
void solve() {
for(int i = 1; i <= n; i++) in[i] = 1;
for(int i = 1; i <= n; i++)
if(deg[i] == 1) q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
in[u] = 0;
for(int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
deg[v]--;
if(deg[v] == 1) q.push(v);
}
}
int u; //u作为环的起始点
for(u = 1; u <= n; u++) if(in[u]) break;
int v = u, las = 0; //上一个环中的点
do {
cir[++cnt] = v;
int k;
for(int i = 0; i < e[v].size(); i++) {
k = e[v][i];
if(in[k] && k != las) break;
}
las = v;
v = k;
} while(v != u);
}欧拉图
通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。
通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉通路的图称为半欧拉图。
有向图的时候可以类似地定义。
G是欧拉图当且仅当G是连通的且没有奇度顶点。
G是半欧拉图当且仅当G中恰有两个奇度顶点。
证：
连通且没有奇度顶点=>一定存在一个环
那么我们把这个环上的边删掉，剩下的图仍满足连通且没有奇数顶点
由连通性这些环可以是有公共点的，可以拼起来
圈套圈算法
//欧拉回路 圈套圈算法
struct noe {
int v, nxt, id;
} e[N];
bool vis[M]; //编号为id的边是否被访问过
int seq[N], cnt;
int s[N], top;
void dfs(int u) {
s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
if(vis[e[i].id]) continue;
vis[e[i].id] = true;
dfs(e[i].v);
}
--top;
seq[++cnt] = u;
}
