图论模板详解

目录

Floyd算法

例题：蓝桥公园

Dijkstra算法

例题：蓝桥王国 

SPFA算法

例题：随机数据下的最短路问题

总结

最小生成树MST

Prim算法

Kruskal算法

例题：聪明的猴子

Floyd算法

最简单的最短路径算法，使用邻接矩阵存图，因为Floyd算法计算的结果是所有点对之间的最短路，本身就要的空间，用矩阵存储最合适。效率不高，计算复杂度为,只能用于n<300的小规模的图，不能用于大图，在某些场景下有自己的优势，难以替代，能做传递闭包问题。

for(int k=1;k<=n;k++){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=min(dp[i][j],d[i][k]+dp[k][j]);
		}
	}
} 

Floyd算法是多源最短路算法，以此计算能得到图中每一对结点之间（多对多）的最短路径。

Floyd算法能判断负圈，若图中有权值为负的边，某个经过这个负边的环路，所有边长相加的总长度也是负数，这就是负圈。在这个负圈上每绕一圈，总长度就更小，从而陷入在兜圈子的死循环。Floyd算法很容易判断负圈，只要在算法运行过程中出现任意一个dp[i][j]<0就说明有负圈，因为dp[i][j]是从i出发，经过其它中转点绕一圈回到自己的最短路径，如果等于0，就存在负圈。

例题：蓝桥公园

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=405;
long long dp[N][N];
int n,m,q;
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
}
int main(){
	cin>>n>>m>>q;
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=m;i++){
		int u,v;
		long long w;
		cin>>u>>v>>w;
		dp[u][v]=dp[v][u]=min(dp[u][v],w);
	}
	floyd();
	while(q--){
		int s,t;
		cin>>s>>t;
		if(dp[s][t]==INF){
			cout<<"-1"<<endl;
		}
		else if(s==t){
			cout<<"0"<<endl;
		}
		else{
			cout<<dp[s][t]<<endl;
		}
	}
	return 0;
}

Dijkstra算法

Dijkstra算法用于求解单源最短路径问题，非常高效而且稳定，但是只能处理不含负权边的图。

Dijkstra算法是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其它所有点的最短距离。

采用优先队列实现，每次往队列中放数据时，按从小到大的顺序放，采用小顶堆的方式，复杂度是，保证最小的数总在最前面。找最小值，直接取第一个数，复杂度是。

例题：蓝桥王国 

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int N=3e5+2;
struct edge{
	int from,to;
	long long w;
	edge(int a,int b,long long c){
		from=a;
		to=b;
		w=c;
	}
};
vector<edge>e[N];
struct s_node{
	int id;
	long long n_dis;
	s_node(int b,long long c){
		id=b;
		n_dis=c;
	}
	bool operator < (const s_node &a) const{ 
		return n_dis>a.n_dis;
	}
};
int n,m;
long long dis[N];
void dijkstra(){
	int s=1;
	bool done[N];
	for(int i=1;i<=n;i++){
		dis[i]=INF;
		done[i]=false;
	}
	dis[s]=0;
	priority_queue<s_node>Q;
	Q.push(s_node(s,dis[s]));
	while(!Q.empty()){
		s_node u=Q.top();
		Q.pop();
		if(done[u.id]){
			continue;
		}
		done[u.id]=true;
		for(int i=0;i<e[u.id].size();i++){
			edge y=e[u.id][i];
			if(done[y.to]){
				continue;
			}
			if(dis[y.to]>y.w+u.n_dis){
				dis[y.to]=y.w+u.n_dis;
				Q.push(s_node(y.to,dis[y.to]));
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		e[i].clear();
	}
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back(edge(u,v,w));
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		if(dis[i]>=INF){
			cout<<"-1";
		}
		else{
			cout<<dis[i];
		}
	}
	return 0;
}

SPFA算法

SPFA算法=队列处理+Bellman-Ford

Bellman-Ford算法有很多低效或无效的操作，其核心内容，是在每一轮操作中，更新所有节点到起点s的最短距离。

计算和调整一个节点u到s的最短距离后，如果紧接着调整u的邻居节点，这些邻居肯定有新的计算结果，而如果漫无目的的计算不与u相邻的节点，这可能毫无变化，所以这些操作是低效的。

改进：计算结点u之后，下一步只计算和调整它的邻居，能加速收敛的过程。这些步骤用队列操作

例题：随机数据下的最短路问题

 

#include<bits/stdc++.h>
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3f;
const int N=5e3+10;
struct edge{
	int to;
	long long w;
	edge(int tt,long long ww){
		to=tt;
		w=ww;
	}
};
long long dist[N];
int inq[N];
vector<edge>e[N];
void spfa(int s){
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int>q;
	q.push(s);
	inq[s]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		if(dist[u]==INF){
			continue;
		}
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].to;
			long long w=e[u][i].w;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				if(!inq[v]){
					q.push(v);
					inq[v]=1;
				}
			}
		}
	}
}
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v;
		long long w;
		cin>>u>>v>>w;
		e[u].push_back(edge(v,w));
	}
	spfa(s);
	for(int i=1;i<=n;i++){
		if(dist[i]==INF){
			cout<<-1;
		}
		else{
			cout<<dist[i];
		}
		if(i!=n){
			cout<<" ";
		}
		else{
			cout<<endl;
		}
	}
	return 0;
}

总结

单源最短路

（1）当权值非负时，用Dijkstra算法。

（2）当权值有负值，且没有负圈，则用SPFA。SPFA能检测负圈，但是不能输出负圈。

（3）当权值有负值而且有负圈需要输出，则用Bellman-Ford，能够检测并输出负圈。

多源最短路

使用Floyd算法。

最小生成树MST

一个含有n个结点的连通图的生成树是原图的极小连通子图，包含原图中的所有n个结点，并且边的权值之和最小。

Prim算法

对点进行贪心操作，从任意一个点u开始，把距离它最近的点加入到MST中，下一步，把距离{u,v}最近的点w加入到MST中；继续这个过程，直到所有的点都在MST中。适用于稠密图。

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=1005;
vector<int>demo;
int closest[MAXN],lowcost[MAXN],n,m;//m为节点的个数，n为边的数量
int G[MAXN][MAXN];//邻接矩阵
int prim(){
	for(int i=0;i<n;i++){
		lowcost[i]=INF;
	}
	for(int i=0;i<m;i++){
		closest[i]=0;
	}
	closest[0]=-1;//加入第一个点，-1表示该点在集合U中，否则在集合V中
	int num=0,ans=0,e=0;
	while(num<m-1){//当点还没有全部放进去 
		int micost=INF;
		for(int i=0;i<m;i++){
			if(closest[i]!=-1){
				int temp=G[e][i];
				if(temp<lowcost[i]){
					lowcost[i]=temp;
					closest[i]=e;
				}
				if(lowcost[i]<micost){
					micost=lowcost[i];
				}
			}
			ans+=micost;
			demo.push_back(micost);
			closest[e]=-1;
			num++;
		}
	} 
	return ans;
} 
int main(){
	cin>>m>>n;
	memset(G,INF,sizeof(G));
	for(int i=0;i<n;i++){
		int a,b,c;
		cin>>a>>b>>c;
		G[b][a]=G[a][b]=c;
	}
	cout<<prim()<<endl;
	for(int i=0;i<m-1;i++){
		cout<<demo[i]<<" ";
	}
	return 0;
}

Kruskal算法

对边进行贪心操作。从最短的边开始，把它加入到MST中，在剩下的边中找最短的边，加入到        MST中，继续这个过程，直到所有的点都在MST中。适用于稀疏图。

kruskal算法的两个关键技术：

（1）对边进行排序

（2）判断圈，即处理连通性问题。这个问题用并查集简单而高效，并查集是krustral算法的绝配。

例题：聪明的猴子

#include<bits/stdc++.h>
using namespace std;
int a[5005],x[5005],y[5005],f[5005];
struct Edge{
	int x,y;
	double w;
}edge[1000005];
int find(int x){
	if(x==f[x]){
		return x;
	}
	f[x]=find(f[x]);
	return f[x];
}
bool cmp(Edge a,Edge b){
	return a.w<b.w;
}
void merge(int x,int y){
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy){
		f[yy]=xx;
	}
}
int main(){
	int n,m,cnt=0;
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&a[i]);
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x[i],&y[i]);
	}
	for(int i=1;i<=n;i++){
		f[i]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]*y[j]));
			edge[++cnt]={i,j,w};
		}
	}
	sort(edge+1,edge+cnt+1,cmp);
	int num=0;
	double maxn=0.0;
	for(int i=1;i<=cnt;i++){
		if(find(edge[i].x)!=find(edge[i].y)){
			merge(edge[i].x,edge[i].y);
			num++;
			maxn=maxn>=edge[i].w?maxn:edge[i].w;
		}
		if(num==n-1){
			break;
		}
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		if(a[i]>=maxn){
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}