图论在算法中具有举足轻重的地位，只有学好图才能游刃有余。本文章将介绍图论中一些基础算法，可以说总结的十分全面，文章结尾也会分析各算法的差异,清晰易懂。并附上代码模板.
图论（最短路、生成树）
- 一、拓扑排序
- 二、Djikstra算法
- 1. 朴素算法
- 2. 优先队列优化
- 三、Bellan-ford算法
- 四、Floyd算法
- 五、Spfa算法
- 1.求最短路
- 2.判断负环
- 六、Prim算法求最小生成树
- 七、Kruskal算法求最小生成树
- 八、一点问题：
- 1、prim 和 dijkstra 的区别与联系：
- 2、spfa 和 dijkstra 的区别与联系：
- 3、求负环的常用方法：
- 总结:
一、拓扑排序
什么是拓扑序？
若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
算法思想：放在前面的点的入度一定更小（起点为入度为0），每次将入度为0的点放入队列中去更新其相连的点，使其相连的点入度-1。
条件：有向无环图. 注：不能存在自环
bool st[N];
int top[N];
int d[N];
bool topsort(){
queue<int> q;
for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
int k = 0;
while(!q.empty()){
int t = q.front();
q.pop();
st[t] = 1;
top[k++] = t;
for(int i=h[t];i!=-1;i=ne[i]){
int j = e[i];
if(!st[j]){
d[j]--;
if(!d[j]) q.push(j);
}
}
}
return k==n;
}
二、Djikstra算法
算法思想：Dijkastra,每次找出不再集合中的距离源点距离最小的点去更新其他点. dist数组保存到源点的距离。
适用于有向图 可存在重边和自环 但不能存在负权
1. 朴素算法
// 朴素
int Dijkastra1(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i=0;i<n;i++){
int t = -1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dist[t]>dist[j])){
t = j;
}
}
st[t] = 1;
for(int j=h[t];j!=-1;j=ne[j]){
int k = e[j];
dist[k] = min(dist[k],dist[t]+w[j]);
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
2. 优先队列优化
typedef pair<int,int> PII;
int Dijkastra2(){
memset(dist,0x3f,sizeof dist);
priority_queue<PII,vector<PII>,greater<PII> > p;
dist[1] = 0;
p.push({0,1});
while(!p.empty()){
PII t = p.top();
p.pop();
if(st[t.second]) continue;
st[t.second] = 1;
for(int i=h[t.second];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j]>dist[t.second]+w[i]){
dist[j] = dist[t.second]+w[i];
p.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
三、Bellan-ford算法
Bellan-ford有边数限制：虽算法效率不高，却有一定的实际意义。
想象这样一个背景：你在一号城市，想去n号城市去旅游。但是飞机没有1号城市从直达n号城市的（只能换乘飞机到达）。你想要花费最少到达目的地；但是吧，每换乘一次，你的心情就会变差一回，也就是说最多换乘k次。问最优解是什么？ （来自yxc大佬）
Bellman-ford算法： 可以用于判断是否存在负权回路 步骤： for k次循环(最多经过k条边) for 所有边a,b,w(权重) 更新：dist[b] = min(dist[b],dist[a]+w) 负权环，指的是一个图中存在一个环，里面包含的边的边权总和<0
int Bellman_ford(){
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
for(int i=0;i<k;i++){
memcpy(backup,dist,sizeof dist);
for(int i=0;i<m;i++){
int a = edges[i].a,b = edges[i].b,c = edges[i].w;
dist[b] = min(dist[b],backup[a]+c);
}
}
if(dist[n] > 0x3f3f3f3f/2) return -1;
else return dist[n];
}
注：图中可能存在重边和自环， 边权可能为负数
四、Floyd算法
有向图，图中可能存在重边和自环，边权可能为负数
Floyd算法用于求解两点之间的最短路问题.
int d[N][N];
void floyd(){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int q=1;q<=n;q++){
d[j][q] = min(d[j][q],d[j][i]+d[i][q]);
}
}
}
}
五、Spfa算法
spfa算法：可以理解为一圈一圈计算
1.求最短路
int dist[N];
bool st[N];
int spfa(){
queue<pii> q;
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
q.push({0,1});
st[1] = 1;
while(!q.empty()){
pii t = q.front();
q.pop();
st[t.second] = 0;
for(int i=h[t.second];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j]>dist[t.second]+w[i]){ // 此处与迪杰斯特拉算法不同. 由于dist[] 总是储存的是当前最小值
dist[j] = dist[t.second] + w[i];
if(!st[j]){
st[j] = 1;
q.push({dist[j],j});
}
}
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
2.判断负环
bool spfa() {
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i++) {
q.push(i);
st[i] = true;
}
st[1] = true;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
st[j] = true;
q.push(j);
}
}
}
}
return false;
}
六、Prim算法求最小生成树
无向图；图中可能存在重边和自环；边权可能为负数。
算法思想：更新到集合的最短距离dist
int state[N],pre[N],st[N],dist[N];
int res;
void prim(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
for(int i=1;i<=n;i++){
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1||dist[t]>dist[j])){
t = j;
}
}
st[t] = 1;
res += dist[t];
for(int j=1;j<=n;j++){
if(!st[j] && dist[j]>g[j][t]){
dist[j] = g[j][t];
}
}
}
}
七、Kruskal算法求最小生成树
算法思想：借助并查集优化算法
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
const int M = 2*N; // 边的数量
struct edge{
int a;
int b;
int w;
bool operator <(const edge &x) const
{
return w<x.w;
}
}egs[M];
int n,m;
int pre[N];
int find(int x){
if(pre[x]==x) return x;
else return pre[x] = find(pre[x]);
}
int kreskal(){
int res = 0,cnt = 0;
for(int i=0;i<m;i++){
int a = egs[i].a, b = egs[i].b, w = egs[i].w;
if(find(a)!=find(b)){
pre[find(a)] = pre[find(b)];
cnt ++;
res += w;
}
}
if(cnt==n-1) return res;
else return 0x3f3f3f3f;
}
int main()
{
scanf("%d%d",&n,&m);
int a,b,c;
for(int i=1;i<=n;i++) pre[i] = i;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
egs[i] = {a,b,c};
}
sort(egs,egs+m);
int t = kreskal();
if(t==0x3f3f3f3f) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
八、一点问题：
1、prim 和 dijkstra 的区别与联系：
- prim 为更新到集合的最短距离dist; 而dijkastra 为更新到源点的最短距离dist。即更新方式不同
- .两者均可以使用优先队列优化.不过在优化时，prim最好采用kruskal优化.
2、spfa 和 dijkstra 的区别与联系：
- st数组的作用不同，可以将一个点反复设为0和1
- SPFA算法中使用的是队列，目的只是记录一下当前发生过更新的点；而dijkstra算法使用的是优先队列，目的是取出不在集合中的距离源点最近的点
3、求负环的常用方法：
求负环的常用方法，基于SPFA，一般都用方法 2：
方法 1：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，则也说明存在负环
总结:
学会不是目的，重要的是能够熟悉算法思想，理解到代码中的细节，这样才能在做题过程中游刃有余。