图论常见算法总结——prim,kruskal,dijkstra,floyed,bellman-ford,spfa

一、求最小生成树

题目链接：https://www.luogu.com.cn/problem/P3366

1.prim算法

任意选取一个起点u，设已加入树的结点为V，总结点为T，则每次搜索连接V与T-V的最短边，并使之加入V（即从T-V向V中加入一个新的节点），当T中所有节点访问完成，即为最小生成树。

优先级队列版实现代码：

#include <iostream>
#include <queue>
using namespace std;
#define MK make_pair
const int N = 5003, M = 400050,INF=(1<<30);
int to[M], w[M], nxt[M], tot;//链式前向星
int h[N], dis[N];
bool visit[N];
int n, m;
priority_queue<pair<int, int>> q;
void add(int a, int b, int c) {to[++tot] = b;        //链式前向星加边w[tot] = c;nxt[tot] = h[a];h[a] = tot;
}
void prim() {cin >> n >> m;for (int i = 1; i <= n; i++) {dis[i] = INF;}for (int i = 1, a, b, c; i <= m; i++) {cin >> a >> b >> c;add(a, b, c); add(b, a, c);//无向图加双边}q.push(MK(0, 1));dis[1] = 0;pair<int, int> now;int d, u;while (!q.empty()) {now = q.top(); q.pop();d = -now.first; u = now.second;   //默认最大堆，所以插入负权值,确保堆顶为最小权值if (dis[u]<d) continue;//已更新过最小权值，舍弃visit[u] = true;for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (dis[v] > w[i] && !visit[v]) {dis[v] = w[i];            //若枚举的边可使T-V到V的路径变短，更新q.push(MK(-dis[v], v));    }}}int ans = 0;for (int i = 1; i <= n; i++) {if (dis[i] == INF) {cout << "orz"; return;}ans += dis[i];}cout << ans;
}
int main() {prim();return 0;
}

2.kruskal算法

连接n个结点需要n-1条边，因此我们只需枚举n-1条能使n个结点连通的最短边即可。

我们首先对边按权值由小到大排序，设枚举的边为w,连接的两个点u、v，u和v分别属于a,b两个集合。若a,b,两个集合不连通，则该边合法，若a,b两个集合连通，则该边不合法，舍弃。要实现该判断，只需使用并查集。

实现代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5003, M = 200020;//这里一条边只记录一次，因此无需翻倍范围
int n, m;
int p[N];//并查集记录祖先
class Edge {
public:int u, v, w;
}; Edge e[M];
bool compar(Edge a, Edge b) {//return a.w < b.w;
}
int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);//p[x]==x即找到祖先，否则找p[x]的祖先
}
void unite(int x, int y) {p[find(x)] = find(y);//使x的祖先加入到y的祖先
}
void kruskal() {cin >> n >> m;for (int i = 1,a,b,c; i <= m; i++) {cin >> e[i].u >> e[i].v >> e[i].w;//读边}for (int i = 1; i <= n; i++) p[i] = i;//每个人的祖先初始化为自己sort(e + 1, e + m + 1, compar);//排序int ans = 0, cnt = 0;for (int i = 1,u,v; i <= m&&cnt<n-1; i++) {u = e[i].u; v = e[i].v;if (find(u) != find(v)) {ans += e[i].w;unite(u, v);cnt++;}}if (cnt != n - 1) {cout << "orz"; return;}cout << ans;
}
int main() {kruskal();
}

二、求最短路

正权图

题目链接：https://www.luogu.com.cn/problem/P4779

1.floyed算法

通过枚举n个中转点，更新每两个点之间的最短路，从而记录任意两个点的最短路。

时间复杂度为 $o(V^3)$

时间复杂度太高，代码略

2.dijkstra算法

类似于prim算法，枚举T-V与V之间的最短路径，不过这里dis[u]的意义变为了结点u与起点s之间的距离

优先级队列实现代码：

#include <iostream>
#include <queue>
using namespace std;
#define MK make_pair
const int N = 100005, M = 200050,INF=(1<<30);
int to[M], w[M], nxt[M], tot;//链式前向星
int h[N], dis[N];
int n, m, s;
priority_queue<pair<int, int>> q;
void add(int a, int b, int c) {to[++tot] = b;        //链式前向星加边w[tot] = c;nxt[tot] = h[a];h[a] = tot;
}
void dijkstra() {cin >> n >> m>>s;for (int i = 1; i <= n; i++) {dis[i] = INF;}for (int i = 1, a, b, c; i <= m; i++) {cin >> a >> b >> c;add(a, b, c);}q.push(MK(0, s));dis[s] = 0;pair<int, int> now;int d, u;while (!q.empty()) {now = q.top(); q.pop();d = -now.first; u = now.second;if (dis[u]<d) continue;//最短路径已更新for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (dis[v] > dis[u]+w[i]) { dis[v] = dis[u]+w[i];      //更新最短路径q.push(MK(-dis[v], v));}}}for (int i = 1; i <= n; i++) cout << dis[i] << ' ';
}
int main() {dijkstra();return 0;
}

三、判负环

题目链接：https://www.luogu.com.cn/problem/P3385

负环，即图中存在权值和为负数的回路（环），在这种情况下，由于可以绕负环无数圈将路径无限减小，因此不存在最短路，那么上面介绍的计算最短路的算法自然也就失效了，下面为判断图中是否存在负环的算法：

1.Bellman-Ford算法

我们先建立一层外层循环，在每一次循环中，都枚举图中的m条边，并对起点到每一个结点的最短路径进行松弛更新，可以保证，每次最少更新一条边，那么在至多n-1次循环后，在循环中将不会再有边更新。若有，则证明图中存在负环

代码如下：

#include <iostream>
using namespace std;
const int N = 2005, M = 6005,INF=(1<<30);
int h[N], dis[N];
int T, n, m, cnt;
class Edge {
public:int u, v, w;
}; Edge e[M]; int tot;
void add(int a, int b, int c) {e[++tot].u = a;e[tot].v = b;e[tot].w = c;
}
void initial() {for (int i = 1; i <= n; i++) dis[i] = INF;for (int i = 1; i <= tot; i++) e[i].u = e[i].v = e[i].w = 0;tot = 0;
}
void BellmanFord() {cin >> n >> m;initial();for (int i = 1, a, b, c; i <= m; i++) {cin >> a >> b >> c;add(a, b, c);if (c >= 0) add(b, a, c);}dis[1] = 0;for (int i = 1; i <= n - 1; i++) {for (int i = 1,u,v,w; i <= tot; i++) {u = e[i].u; v = e[i].v; w = e[i].w;if (dis[u]!=INF&&dis[v] > dis[u] + w) {dis[v] = dis[u] + w;}}}for (int i = 1,u,v,w; i <= tot; i++) {u = e[i].u; v = e[i].v; w = e[i].w;if (dis[u] == INF || dis[v] == INF) continue;if (dis[v] > dis[u] + w) {cout << "YES" << endl;return;}}cout << "NO" << endl;return;
}
int main() {cin >> T;while (T--) {BellmanFord();}return 0;
}

2.SPFA算法

SPFA算法是BellmanFord算法的队列优化，这里用到一个事实，即只有在上一轮循环中进行过松弛更新的结点能进行下一轮松弛更新，因此，我们可以用队列来记录上一轮循环中松弛过的结点来进行下一轮松弛，来提高效率。但这个时候我们就无法统计外层循环轮数了。不过，我们可以知道，当图中存在负权回路时，一个结点会反复地进入队列进行松弛。我们对到达结点u的最短路径所经历过的结点数cnt进行统计，显然cnt[u]不会超过n，若超过了n，说明已形成环路，且一定是负环。

队列实现代码如下：

#include <iostream>
#include <queue>
using namespace std;
const int N = 2005, M = 6005, INF = (1 << 30);
int to[M], w[M], nxt[M], tot;
int h[N], dis[N],cnt[N];
bool vis[N];
int T,n,m;
queue<int> q;
void initial() {//多组数据输入的题目，初始化很重要while(!q.empty()) q.pop();for (int i = 1; i <= n; i++) { dis[i] = INF; vis[i] =h[i]=cnt[i] = 0; }for (int i = 1; i <= tot; i++) { to[i] = w[i] = nxt[i] = 0; }tot = 0;
}
void add(int a, int b, int c) {to[++tot] = b;w[tot] = c;nxt[tot] = h[a];h[a] = tot;
}
void SPFA() {cin >> n >> m;initial();for (int i = 1,a,b,c; i <= m; i++) {cin >> a >> b >> c;add(a, b, c);if (c >= 0) add(b, a, c);}q.push(1);dis[1] = 0; cnt[1] = 1;int u;while (!q.empty()) {u = q.front(); q.pop();vis[u] = false;//记录u是否在队列中for (int i = h[u], v; v = to[i]; i = nxt[i]) {if (dis[v] > dis[u] + w[i]) {dis[v] = dis[u] + w[i];cnt[v] = cnt[u] + 1;//记录路径结点数if (cnt[v] > n) {cout << "YES" << endl;return;}if (!vis[v]) {q.push(v);vis[v] = true;}}}}cout << "NO" << endl;
}
int main() {cin >> T;while (T--) {SPFA();}return 0;
}