图论板子总结 / 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<int,int>

 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<PII, vector<PII>, greater<PII>> 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 }

巴特西

图论板子总结 / Graph Summary

最新文章

热门文章