图论思维导图_编号c6283963-TreeMind树图

查看详情

图论

树图思维导图提供图论在线思维导图免费制作，点击“编辑”按钮，可对图论进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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; } /*