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

查看详情

图论

树图思维导图提供图论在线思维导图免费制作，点击“编辑”按钮，可对图论进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7c70ca7c0fbf1f9ef2f3d7d8a71c21e2

图论算法

举报/反馈

思维导图大纲

图论思维导图模板大纲

定义

图论就是在一个图中对这个图处理

算法

基础算法

深度优先搜索

广度优先搜索

其他算法

多源最短路

佛罗伊德算法（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; } /*

堆优化（vector）

使用一个vector数组来进行存储，替换静态数组

#include<bits/stdc++.h> using namespace std; const int N=2010,M=20010; int book[N],dis[N],n,m; typedef pair<int,int> PII; priority_queue<PII,vwctor<PII>,greater<PII>> heap; vector<PII> G[N]; void Dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[1]=0; heap.push({0,1}); while(!heap.empty()){ auto t=heap.top; heap.pop(); int u=t.second; if(book[u]) continue; book[u]=1; for(auto edge:G[u]){ int v=edge.first; int w=edge.second; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; heap.push({dis[v],v}); } } } } int main(){ //freopen("candy.in","r",stdin); //freopen("candy.out","w",stdout); int a,b,c; cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a>>b>>c; G[a].push_back({b,c}); G[b].push_back({a,c}); } Dijkstra(); if(dis[n]!=0x3f3f3f3f) cout<<dis[n]; else cout<<-1; return 0; }

贝尔曼-福特（bellman-ford）

适用于单源最短路中边权值可能为负的情形

时间复杂度

O(NM)

思路

保存每一条路径的权值，随后n-1次循环，每次循环m条边，刷新dis数组，在经过n-1次后，必然能刷新出dis的最小值

实现

int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u[i],&v[i],&w[i]); } memset(dis,0x3f,sizeof(dis); dis[1]=0; for(int k=1;k<n;k++){ for(int i=1;i<=m;i++){ if(dis[v[i]]>dis[u[i]]+w[i]){ dis[v[i]]=dis[u[i]]+w[i]; } } } for(int i=2;i<=n;i++) cout<<dis[i]<<" ";

负权回路

当在图中，有一个点到他本身的一个回路权值之和为负的时候，就是一个负权回路

检测思路

进行完n-1次循环后，在进行一轮，如果dis数组还有变化，就一定有负权回路

实现

SPFA

int check=0; for(int i=1;i<=m;i++) if(dis[v[i]]>dis[u[i]]+w[i]) flag=1; if(flag==1) cout<<"有负权回路";

相比于贝尔曼-福特，它看起来更像是bfs明知不过一个点可以重复进，但bfs不行

时间复杂度

最高退化至O(NM)

typedef pair<int,int> PII; vector<PII> G[10010]; int n,m,dis[10010]; int spfa(){ queue<int> q; memset(dis,0x3f,sizeof(dis)); dis[1]=0; q.push(1); while(!q.empty()){ int u=q.front; q.pop(); for(auto edge:G[u]){ int v=edge.first; int w=edge.second; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; q.push(v); } } } if(dis[n]==0x3f3f3f3f) return -1; return dis[n]; } int main(){ scanf("%d%d",&n,&m); int a,b,c; for(int i=1;i<=m;i++){ cin>>a>>b>>c; G[a].push_back({b,c}); G[b].push_back({a,c}); } printf("%d",spfa()); return 0; }

并查集

适用条件

需要求大量点的父亲节点

思路

通过一个f数组，存储第i个节点的父亲节点，每次输入一条路径后，如果路径的起点终点父亲节点不相同，则合并这两棵树，形成一棵新的树，以此类推

要点

初始化时，要把初始节点的父亲节点设为自己

当所有路径输入完毕后，还要再找一次父亲节点，因为受到路径输入顺序的影响，有些点的父亲节点没刷新完毕

实现

子主题 1

最小生成树

定义

对于一个连通图，最少使用几条边可以生成一棵树

常用算法

1、kruskal（稀疏图）

思路

思路继承自并查集，先将路径按照长度升序排列，随后用并查集判断使用这条路线的两个节点是否联通，如果没有，那么使用这条路径

实现

#include<bits/stdc++.h> using namespace std; const int N=10010,M=10010; int f[N]; struct stu{ int x,y,dis; }a[M]; bool cmp(stu x,stu y){ if(x.dis!=y.dis) return x.dis<y.dis; return 0; } int father(int x){ if(f[x]!=x) return f[x]=father(f[x]); return x; } void unionn(int x,int y){ int r1=father(x); int r2=father(y); if(r1!=r2) f[r1]=r2; return; } int main(){ int n,m,ans=0,tot=0; cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%d",a[i].x,a[i].y,a[i].dis); } for(int i=1;i<=n;i++) f[i]=i; sort(a+1,a+1+m,cmp); for(int i=1;i<=m;i++){ if(father(a[i].x)!=father(a[i].y)){ unionn(a[i].x,a[i].y); ans+=a[i].dis; tot++; if(tot==n-1) break; } } cout<<ans; return 0; }

时间

O(mlog(m))

2、prime（稠密图）

思路

思路继承自Dijkstra，通过邻接矩阵输入，使用dis数组判断1号节点到其他节点的距离，使用朴素Dijkstra的框架判断寻找最短路径，加上这条路径的长度，随后使用这个路径刷新到其他节点的值

实现

#include<bits/stdc++.h> using namespace std; const int inf=1e9+10; int n,s,dis[110],book[110],a[110][110]; int main(){ cin>>n; memset(a,0x3f,sizeof(a)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++) dis[i]=a[1][i]; book[1]=1; for(int i=1;i<n;i++){ int u,mini=INT_MAX; for(int j=1;j<=n;j++){ if(book[j]==0&&dis[j]<mini){ mini=dis[j]; u=j; } } book[u]=1; s+=mini; for(int v=1;v<=n;v++){ if(book[v]==0&&a[u][v]<=dis[v]){ dis[v]=a[u][v]; } } } if(check()) cout<<s; else cout<<-1; return 0; }

时间复杂度

O(N^2)

二分图

定义

对于一张图，如果能将其分为两部分，这两部分当中的节点不互相连通，则称这个图为二分图

判断

思路

通过染色法，每个节点遍历一次，相邻两个节点图上不同的颜色，如果颜色出现冲突，则不是二分图，如果能顺利染完，则为二分图

子主题 1

使用算法

dfs/bfs

实现

#include<bits/stdc++.h> using namespace std; const int N=100010; vector<int> G[N]; int color[N],u,n,m; bool dfs(int x){ for(auto edge:G[x]){ if(color[edge]&&color[edge]==color[x]) return false; if(color[edge]==0){ color[edge]=3-color[x]; if(!dfs(edge)) return false; } } return true; } bool bfs(int x){ queue<int> q; q.push(x); while(!q.empty()){ u=q.front(); q.pop(); for(auto edge:G[u]){ if(color[edge]&&color[edge]==color[u]) return 0; if(color[edge]==0){ color[edge]=3-color[x]; q.push(edge); } } } return 1; } int main(){ int a,b; while(cin>>n){ if(n==0) return 0; cin>>m; for(int i=1;i<=n;i++){ G[i].clear(); color[i]=0; } for(int i=1;i<=m;i++){ scanf("%d%d",&a,&b); G[a].push_back(b); G[b].push_back(a); } int flag=0; for(int i=1;i<=n;i++){ if(color[i]==0){ color[i]=1; if(!bfs(i)){ flag=1; break; } } } if(flag==0) cout<<"BICOLORABLE.\n"; else cout<<"NOT BICOLORABLE.\n"; } return 0; }

匹配

定义

对于一张图，如果一个图每个点都能对应一个节点且于其他节点不连通

但因为这种情况很难实现，因此一般讨论最大匹配，即这张图最多支持几组匹配关系

寻找最大匹配

二分图

遍历他的节点寻找对应边，如果对应点没有被自己选择过，则预定此节点，如果这个节点没有对应点或者他的对应节点可以选择另外一个节点，那么把这个节点的主人归于他自己

实现

#include<bits/stdc++.h> using namespace std; const int N=510,M=5e4+10; int book[N],match[N]; vector<int> G[N]; bool dfs(int x) { //遍历节点x寻找它的匹配边 for(auto edge:G[x]) { if(book[edge]==0) { //如果这个节点没有被选择 book[edge]=1;//有人配对了这个点 if(!match[edge]||dfs(match[edge])) { //如果这个点没有节点配对使用或者那个节点可以选择其他节点配对 match[edge]=x;//节点edge的对应节点改为节点x return 1; } } } return 0;//配对失败 } int main() { int n1,n2,m,a,b,ans=0; scanf("%d%d%d",&n1,&n2,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); G[a].push_back(b); } for(int i=1;i<=n1;i++) { memset(book,0,sizeof(book)); if(dfs(i)) ans++;//如果这个节点能找到配对点 } cout<<ans; return 0; }