图论板子总结 / Graph Summary

Template List：

  最短路问题：Dijkstra（朴素版、堆优化版），Bellman-Ford，SPFA，Floyd

  最小生成树：Prim、Kruskal

  二分图问题：染色法、匈牙利算法

朴素Dijkstra：

  适用：单源汇、无负边、稠密图 の 最短路问题

  时间复杂度：o(n²)

  Code：

 1 #define int longlong
 2 const int INF = 0x3f3f3f3f3f3f3f3f;
 3 
 4 int n, m, g[N][N], dist[N]; // 稠密图用邻接矩阵存图
 5 bool st[N];
 6 
 7 int dijkstra()
 8 {
 9     // 起点初始化为0, 其他点初始化为无穷大(INF)
10     memset(dist, 0x3f, sizeof dist);
11     dist[1] = 0;
12 
13     for(int i = 1; i <= n; i++)
14     {
15         // 找到当前未确定最短路的点中 距离最短的点
16         int t = -1;
17         for(int j = 1; j <= n; j++)
18             if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
19         // 用t更新其他点
20         for(int j = 1; j <= n; j++)
21             dist[j] = min(dist[j], dist[t]+g[t][j]);
22         // t已确定最短路 
23         st[t] = true;
24     }
25     // 若为INF说明无路可通
26     return dist[n] != INF ? dist[n] : -1;
27 }

堆优化Dijkstra：

  适用：单源汇、无负边、稀疏图 の 最短路问题

  时间复杂度：o(mlogn)

  Code：

 1 #define int long long
 2 #define PII pair
 3 const int INF = 0x3f3f3f3f3f3f3f3f;
 4 
 5 int n, m, dist[N];
 6 int h[N], e[N], w[N], ne[N], idx; // 邻接表存稀疏图
 7 bool st[N];
 8 
 9 int dijkstra()
10 {
11     memset(dist, 0x3f, sizeof dist);
12     dist[1] = 0;
13     // PII：first存dist，second存点的编号
14     // 小根堆维护当前未入st的dist最小值
15     priority_queue, greater> heap;
16     heap.push({0,1});
17 
18     while(heap.size())
19     {
20         auto t = heap.top();
21         heap.pop();
22 
23         int ver = t.second, d = t.first;
24         if(st[ver]) continue;
25         st[ver] = true;
26 
27         for(int i = h[ver]; i != -1; i = ne[i])
28         {
29             int j = e[i];
30             if(dist[j] > dist[ver] + w[i])
31             {
32                 dist[j] = dist[ver] + w[i];
33                 heap.push({dist[j], j});
34             }
35         }
36     }
37 
38     return dist[n] == INF ? -1 : dist[n];
39 }

Bellman-Ford：

  适用：单源汇、有负边（可限制最多经过的边数） の 最短路问题，判是否存在负环

  时间复杂度：o(nm)

  Code：

 1 int n, m, k, dist[N], last[N];
 2 
 3 struct Edge {
 4     int x, y, w;
 5 } edge[M]; // 存边
 6 
 7 void bellman_ford()
 8 {
 9     // dist数组初始化
10     memset(dist, 0x3f, sizeof dist);
11     dist[1] = 0;
12     // 最多经过不超过i条边时的最短路
13     for(int i = 1; i <= k; i++)
14     {
15         // 复制原来的dist数组, 避免串联更新dist
16         memcpy(last, dist, sizeof dist); 
17         for(int j = 1; j <= m; j++)
18         {
19             auto e = edge[j];
20             dist[e.y] = min(dist[e.y], last[e.x] + e.w);
21         }
22     }
23 
24     if(dist[n] > INF / 2) puts("impossible"); // 大于一个较大的值就说明不存在通路
25     else printf("%lld\n", dist[n]);
26 }

SPFA：

  适用：单源汇、有负边 の 最短路问题，判是否存在负环

  时间复杂度：一般o(n)，最差o(nm)

  Code：

    最短路问题：

 1 int n, m, dist[N];
 2 int h[N], e[N], w[N], ne[N], idx; // 邻接表存图
 3 bool st[N]; // 判断点是否在队列中
 4 
 5 void spfa()
 6 {
 7     // 初始化dist, 将起点入队
 8     memset(dist, 0x3f, sizeof dist);
 9     dist[1] = 0;
10     queue<int> q;
11     q.push(1), st[1] = true;
12 
13     while(q.size())
14     {
15         int t = q.front();
16         q.pop(), st[t] = false;
17         for(int i = h[t]; i != -1; i = ne[i])
18         {
19             int j = e[i];
20             if(dist[j] > dist[t] + w[i]) // dist[j]可更新变小 --> 用j更新其他点
21             {
22                 dist[j] = dist[t] + w[i];
23                 if(!st[j]) q.push(j), st[j] = true; // j不在队列中就入队
24             }
25         }
26     }
27 
28     if(dist[n] == INF) puts("impossible"); // 无通路
29     else printf("%lld\n", dist[n]);
30 }

    判有无负环：

 1 int n, m;
 2 int h[N], e[M], w[M], ne[M], idx; // 邻接表存图
 3 int dist[N], cnt[N]; // cnt数组记录到点i的最短路经过多少条边
 4 bool st[N];
 5 
 6 bool spfa()
 7 {
 8     queue<int> q;
 9     for(int i = 1; i <= n; i++) q.push(i), st[i] = true;
10     while(q.size())
11     {
12         int t = q.front();
13         q.pop(), st[t] = false;
14         for(int i = h[t]; i != -1; i = ne[i])
15         {
16             int j = e[i];
17             if(dist[j] > dist[t] + w[i])
18             {
19                 dist[j] = dist[t] + w[i];
20                 cnt[j] = cnt[t] + 1;
21                 if(cnt[j] >= n) return true; // 总共n个点, 经过>=n条边则必有负环
22                 if(!st[j]) q.push(j), st[j] = true;
23             }
24         }
25     }
26     return false;
27 }

Floyd：

  适用：多源汇 の 最短路问题

  时间复杂度：o(n³)

  Code：

 1 int n, m, k;
 2 int d[N][N]; // 邻接矩阵存图, 跑完floyd后d[i][j]表示i到j的最短距离
 3 
 4 void floyd()
 5 {
 6     for(int k = 1; k <= n; k++)
 7         for(int i = 1; i <= n; i++)
 8             for(int j = 1; j <= n; j++)
 9                 d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
10 }

朴素Prim：

  适用：稠密图求最小生成树

  时间复杂度：o(n²)

  Code：

 1 int n, m, g[N][N], dist[N]; // 邻接矩阵存稠密图, dist数组表示点到集合中点的最短距离
 2 bool st[N]; // 已入集合的点
 3 
 4 int prim()
 5 {
 6     int res = 0;
 7     memset(dist, 0x3f, sizeof dist);
 8     for(int i = 0; i < n; i++)
 9     {
10         int t = 0;
11         for(int j = 1; j <= n; j++)
12             if(!st[j] && (!t || dist[t] > dist[j])) t = j; // t是集合外中dist最小的点
13         if(i && dist[t] == INF) return INF; // 除第一个点外, 若dist为INF说明无最小生成树
14         if(i) res += dist[t]; // 除入集合的第一个点外, 累加边权
15         st[t] = true; // 将点入集合
16         for(int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]); // 用t更新未进入集合的点的dist
17     }
18     return res; // 返回累加的边权和
19 }

Kruskal：

  适用：稀疏图求最小生成树

  时间复杂度：o(mlogm)

  Code：

 1 int n, m, fa[N]; // fa数组：并查集, 维护点集
 2 
 3 struct Edge {
 4     int a, b, w;
 5     bool operator < (const Edge & W) const {
 6         return w < W.w;
 7     }
 8 } e[M]; // 结构体数组存边
 9 
10 // 并查集中查找根节点的函数
11 int find(int x)
12 {
13     return fa[x] == x ? x : fa[x] = find(fa[x]);
14 }
15 
16 int kruskal()
17 {
18     int res = 0, cnt = 0; // res：边权和, cnt：已连上的边数
19     sort(e+1, e+1+m); // 将边按边权从小到大排序
20     for(int i = 1; i <= n; i++) fa[i] = i; // 并查集初始化
21     for(int i = 1; i <= m; i++)
22     {
23         int a = find(e[i].a), b = find(e[i].b);
24         if(a != b) // a、b未连上
25         {
26             fa[a] = b; // 将点a、b连上
27             res += e[i].w, cnt ++; 
28         }
29         if(cnt == n-1) return res; // 最小生成树已求出
30     }
31     return INF; // 最小生成树不存在
32 }

染色法：

  适用：判断二分图

  时间复杂度：o(n+m)

  Code：

 1 int n, m;
 2 int h[N], e[M], ne[M], idx; // 邻接表存图
 3 int color[N]; // 0表示未染色, 1、2为染的不同颜色
 4 
 5 bool dfs(int u, int c)
 6 {
 7     color[u] = c; // c表示染的颜色
 8     for(int i = h[u]; i != -1; i = ne[i])
 9     {
10         int j = e[i];
11         if(!color[j] && !dfs(j, 3-c)) return false; // 若未染色, 对j及j可达的点进行染色, 3-c：染不同颜色
12         else if(color[j] == c) return false; // 若j已染色, 但与u同色, 说明染色失败
13     }
14     return true; // 本次染色成功
15 }
16 
17 bool stain()
18 {
19     for(int i = 1; i <= n; i++)
20         if(!color[i] && !dfs(i, 1)) return false; // 染色失败则不是二分图
21     return true; // 所有点染色成功则为二分图
22 }

匈牙利算法：

  适用：二分图求最大匹配数

  时间复杂度：理论：o(nm)，实际：一般比 o(nm) 快

  Code：

 1 int n1, n2, m; // n1为左点集, n2为右点集
 2 int h[N], e[M], ne[M], idx; // 邻接表存图
 3 int match[N]; // 与右点集的点匹配的左点集的点
 4 bool st[N]; // 右点集的点是否已经考虑
 5 
 6 bool find(int x) // 为左点集的点寻找匹配
 7 {
 8     for(int i = h[x]; i != -1; i = ne[i])
 9     {
10         int j = e[i];
11         if(!st[j]) // 若j还未考虑过(避免重复考虑同一个点)
12         {
13             st[j] = true;
14             if(!match[j] || find(match[j])) // 若该点未匹配 或 该点匹配的点可找到下家
15             {
16                 match[j] = x; // x与j匹配上
17                 return true;
18             }
19         }
20     }
21     return false; // 未能为x找到匹配的点
22 }
23 
24 int hungary() // 匈牙利算法
25 {
26     int cnt = 0; // 最大匹配数
27     for(int i = 1; i <= n1; i++) // 枚举左点集的点
28     {
29         memset(st, 0, sizeof st);
30         if(find(i)) cnt ++; // 匹配成功则cnt+=1
31     }
32     return cnt;
33 }