前言

关于图，我主要讲一下拓扑排序和迪加特斯拉算法

TopSort

基本算法思路就是每次寻找入度为0的点，然后将其加入到集合中，然后需要把其相邻的点的入度减1，（毕竟加入了集合，那就不需要连接在一起了，也就减少了入度了）。

代码

#include<bits/stdc++.h>using namespace std;
const int N=100010;
vector<vector<int>>edges;//邻接表存储图
int indges[N];//每个点的入度
vector<int>ans;//答案存储点的序列
int main()
{int n,m; //指点的个数和边的条数cin>>n>>m;edges.resize(n+1);int x,y;queue<int>que;for(int i=0;i<m;i++){cin>>x>>y;edges[x].push_back(y);indges[y]++;}for(int i=1;i<=n;i++){if(indges[i]==0){que.push(i);}}while(que.size()){auto u=que.front();que.pop();ans.push_back(u);indges[u]--;  //去除一个点，其入度不能为0了for(auto &v:edges[u]){indges[v]--;if(indges[v]==0){que.push(v);}}}if(ans.size()==n){for(auto &num:ans)cout<<num<<" ";}else cout<<-1<<endl;return 0;
}

迪杰特斯拉算法

对djk算法，主要是要维护一个空集合，然后选择距离源点距离最小的点，加入其中这个集合，再通过这个点来进行对其他点的距离的更新。之后再下次则需要在这个集合的补集中的点中选择距离源点最小的点，再次更新对其他点的距离，因此一共需要n次的迭代来使集合满，同时选择距离源点距离最小需要n次，所以时间复杂度为o(n2)

代码

#include<bits/stdc++.h>using namespace std;
const int N=510;
int dist[N];//各点到源点的距离
int st[N];//维护的集合
int n,m;
int g[N][N];//图
int djk()
{memset(dist,0x3f,sizeof dist);//需要先把距离初始化为无穷大dist[1]=0;//第一个节点肯定是0for(int i=0;i<n;i++)//需要迭代n次{int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t])){t=j;}}st[t]=true;//加入集合//进行更新for(int j=1;j<=n;j++){if(dist[j]>dist[t]+g[t][j]){dist[j]=dist[t]+g[t][j];}}}if(dist[n]==0x3f3f3f3f)return -1;else return dist[n];
}
int main()
{memset(g,0x3f,sizeof g);cin>>n>>m;int x,y,w;for(int i=0;i<m;i++){cin>>x>>y>>w;g[x][y]=min(g[x][y],w);//如果输入重边的话，就选择最小的}cout<<djk()<<endl;return 0;
}

基于堆优化的djk算法

如果采用堆的话，就可以把求最小距离的时间复杂度降低为nlog(n),而求最小距离是最耗时的，每求一次需要n次，一共需要n次迭代，则其时间复杂度为o(n2)

代码

//这个是基于邻接表来的。
#include<bits/stdc++.h>using namespace std;
const int N=150100;
typedef pair<int,int> PII;//存储节点之间的距离和点
vector<vector<PII>>edges;//邻接表
priority_queue<PII,vector<PII>,greater<PII>>heap;//小根堆
int dist[N];//距离源点的距离
int st[N];//集合
int n,m;
int djk()
{memset(dist,0x3f,sizeof dist);dist[1]=0;heap.push({0,1});//注意必须为距离在二元第一个元素，这样堆中才是通过距离排序while(heap.size()){auto [w,x]=heap.top();heap.pop();if(st[x])continue;st[x]=true;//已经找到了最小距离，则下一步即是更新for(auto &[y,w]:edges[x]){if(dist[x]+w<dist[y]){dist[y]=dist[x]+w;heap.push({dist[y],y});}}}if(dist[n]==0x3f3f3f3f)return -1;else return dist[n];
}
int main()
{cin>>n>>m;edges.resize(n+1);int x,y,w;for(int i=0;i<m;i++){cin>>x>>y>>w;edges[x].push_back({y,w});}cout<<djk()<<endl;return 0;
}