图论思维导图
图论
树图思维导图提供 图论 在线思维导图免费制作，点击“编辑”按钮，可对 图论 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：461dac97be401c6a4e23d9e940f48870
思维导图大纲
图论思维导图模板大纲
定义
图论就是在一个图中对这个图处理
算法
基础算法
深度优先搜索
广度优先搜索
其他算法
多源最短路
佛罗伊德算法（Floyd）
实现问题
在一个图当中，找出从任意一点到另外一点的最小权值
实现方法
使用动态规划，暴力计算从i到j是直走快还是绕行k结点快
时间复杂度
由于该算法暴力枚举每种情况，时间复杂度较高，达到了O(n^3)
核心框架
for(int k=1;k<=n;k++){//k表示中间节点 for(int i=1;i<=n;i++){//i表示起点 for(int j=1;j<=n;j++){//j表示终点 f[i][j]=min(f[i][j],f[i][k]+f[k][j]);//判断i到j是直接走快还是走k绕行快 } } }
注意点
f数组要初始化为极大值，f[i][i]初始化为0，表示自己到自己为0
三层循环一定要先从中间节点开始，否则一条路还没刷新为最小值就参与另一条路最小值的计算
单源最短路
Dijkstra算法
适用范围
边的权值均为正数的图中求取单源最短路
算法底层逻辑
使用贪心算法的底层逻辑，从到起点最近的结点开始，刷新最短路径，再到离起点第二近的开始刷新，以此类推
朴素Dijkstra
时间复杂度
循环过程中只与点有关，时间复杂度为O(n^2)
适用范围
m数量极大的图
基础代码
for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&z); a[x][y]=z; if(x==1) dis[y]=z; } dis[1]=0; for(int i=1;i<n;i++){ int mind=INT_MAX,u; for(int j=2;j<=n;j++){ if(mind>dis[j]&&book[j]==0){ mind=dis[j]; u=j; } }book[u]=1; for(int v=2;v<=n;v++){ dis[v]=min(dis[v],dis[u]+a[u][v]); } } for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; }
邻接表优化
目的
由于输入过程中使用邻接矩阵，浪费空间及时间，因此可以改用之前学过的单链表作为邻接表使用
优化方案
for(int i=1;i<=m;i++){ scanf("%d%d%d",&u[i],&v[i],&w[i]); ne[i]=f[u[i]]; f[u[i]]=i; }
堆优化Dijkstra
时间复杂度
使用了priority_queue，时间复杂度变为O（mlog2(n)）
适用范围
m与n在一个数量级的图
实现
#include<bits/stdc++.h> using namespace std; const int N=20010,M=20010; int e[M],w[M],ne[M],h[N],idx,book[N],dis[N],n,m; void add(int a,int b,int c){ e[idx]=b; w[idx]=c; ne[idx]=h[a]; h[a]=idx; idx++; } void Dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1]=0; book[1]=0; for(int i=1;i<n;i++){ int mind=0x3f3f3f3f,s; for(int j=1;j<=n;j++){ if(mind>dis[j]&&book[j]==0){ mind=dis[j]; s=j; } } book[s]=1; for(int j=h[s];j!=-1;j=ne[j]){ dis[e[j]]=min(dis[e[j]],dis[s]+w[j]); } } } int main(){ memset(h,-1,sizeof(h)); int a,b,c,k; cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } Dijkstra(); if(dis[n]!=0x3f3f3f3f) cout<<dis[n]; else cout<<-1; return 0; } /*
沪公网安备 31011502019485号
上海工商