图论总结

搜索

DFS

dfs可以说是选择一条可行的路径一直走到头，到头之后就是往回走，往回走也有一定的程度，比如往回走了一步，发现又可以往下走了，就继续走。dfs函数写在什么位置，可以这么理解，等于dfs()是一条分界线，他的上边的逻辑我要做什么，修改标志之类的，他的下边就是我做上边的那些没有成功，就要恢复现场

排列数字

#include<iostream>
using namespace std;
const int N=11;
int path[N];
bool st[N];
int n;void dfs(int u){if(u==n){for(int i=0;i<n;i++) printf("%d ",path[i]);puts("");}for(int i=1;i<=n;i++){if(!st[i]){path[u]=i;st[i]=true;dfs(u+1);st[i]=false;}}
}int main(){scanf("%d",&n);dfs(0);
}

n皇后问题

#include<iostream>
using namespace std;
const int N=11,M=22;
char q[N][N];
bool col[M],dg[M],udg[M];
int n;void dfs(int u){if(u==n){for(int i=0;i<n;i++) puts(q[i]);puts("");}for(int i=0;i<n;i++){if(!col[i] && !dg[u+i] && !udg[u+n-i]){q[u][i]='Q';col[i]=dg[u+i]=udg[u+n-i]=true;dfs(u+1);col[i]=dg[u+i]=udg[u+n-i]=false;q[u][i]='.';}}
}int main(){scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)q[i][j]='.';dfs(0);
}

BFS

BFS就是一层一层往下走，如果符合条件就把他装入队列中，并且维护一些东西，然后每次也是取队头元素进行下一步操作

走迷宫(经典例题)

#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;
const int N=110;
int g[N][N],d[N][N];
int n,m;
PII q[N*N];void bfs(){int hh=0,tt=-1;memset(d,-1,sizeof d);d[0][0]=0;q[++tt] = {0,0};int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};while(hh<=tt){PII t=q[hh++];for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x>=0 && x<n && y>=0 && y<m && !g[x][y] && d[x][y]==-1){d[x][y]=d[t.first][t.second]+1;q[++tt] = {x,y};}}}printf("%d",d[n-1][m-1]);
}int main(){scanf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<m;j++)scanf("%d",&g[i][j]);}bfs();
}

树与图的深度优先遍历

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],ne[N*2],idx;
bool st[N];
int n;
int ans = N;void add(int a,int b){e[idx] = b;ne[idx]=h[a];h[a]=idx++;
} int dfs(int u){st[u]=true;int sum=1,res=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){int s=dfs(j);sum += s;res=max(res,s);}}res=max(res,n-sum);ans=min(res,ans);return sum;
}int main(){scanf("%d",&n);memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a);}dfs(1);printf("%d",ans);
}

树与图的广度优先遍历

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N],q[N];void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}void bfs(){int hh=0,tt=-1;q[++tt] = 1;memset(d,-1,sizeof d);d[1]=0;while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){d[j]=d[t]+1;q[++tt] = j;}}}printf("%d",d[n]);
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);}bfs();
}

有向图的拓扑序列

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N],ne[N],idx;
int d[N];
int n,m;
int q[N];
void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}bool topsort(){int hh=0,tt=-1;for(int i=1;i<=n;i++){if(!d[i]) q[++tt] = i;}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0){q[++tt] = j;}}}return tt==n-1;
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);d[b]++;}if(topsort()){for(int i=0;i<n;i++) printf("%d ",q[i]);}else puts("-1");
}

Dijkstra算法求解最短路问题

#include<iostream>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N];
int dist[N];
bool st[N];
int n,m;int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j] && (t==-1 || dist[t]>dist[j]))t=j;}for(int j=1;j<=n;j++)dist[j]=min(dist[j],dist[t]+g[t][j]);st[t]=true;}return dist[n];
}int main(){scanf("%d%d",&n,&m);memset(g,0x3f,sizeof g);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b]=min(g[a][b],c);}int t=dijkstra();if(t==0x3f3f3f3f) puts("-1");else printf("%d",t);
}

Dijkstra算法求解最短路问题(小根堆优化)

主要是通过小根堆优化每次找最小值的过程

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=100010,M=200010;
typedef pair<int,int> PII;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int n,m;void add(int a,int b,int c){e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx ++;
}int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1});while(heap.size()){PII t=heap.top();heap.pop();int ver=t.second;if(st[ver]) continue;st[ver] = true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[ver]+w[i]){dist[j]=dist[ver]+w[i];heap.push({dist[j],j});}}}return dist[n];
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int t=dijkstra();if(t==0x3f3f3f3f) puts("-1");else printf("%d",t);
}

bellman-ford算法求解有负边的最短路

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=10010;
int n,m,k;
int dist[N],last[N];
struct Edge{int a,b,c;
}edges[M];int bellman_ford(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<k;i++){memcpy(last,dist,sizeof dist);for(int j=0;j<m;j++){Edge e=edges[j];dist[e.b]=min(dist[e.b],last[e.a]+e.c);}}return dist[n];
}int main(){scanf("%d%d%d",&n,&m,&k);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);edges[i]={a,b,c};}int t=bellman_ford();if(t>0x3f3f3f3f/2) puts("impossible");else printf("%d",t);
}

spfa算法

spfa求解最短路

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010;
int h[N],e[N*2],w[N*2],ne[N*2],idx;
int dist[N],q[N];
bool st[N];
int n,m;void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}int spfa(){memset(dist,0x3f,sizeof dist);dist[1]=0;int hh=0,tt=-1;q[++tt] = 1;while(hh<=tt){int t=q[hh++];st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){st[j]=true;q[++tt] = j;}}}}return dist[n];
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}int t=spfa();if(t==0x3f3f3f3f) puts("impossible");else printf("%d",t);
}

spfa求负环

#include<iostream>
#include<cstring>
using namespace std;
const int N=2010,M=10010;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],q[N*M],cnt[N];
bool st[N];
int n,m;void add(int a,int b,int c){e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx ++;
}bool spfa(){memset(dist,0x3f,sizeof dist);dist[1]=0;int hh=0,tt=-1;for(int i=1;i<=n;i++){q[++tt] = i;}while(hh<=tt){int t=q[hh++];st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n) return true;if(!st[j]){st[j]=true;q[++tt] = j;}}}}return false;
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);}if(spfa()) puts("Yes");else puts("No");
}

floyd求解多源最短路

#include<iostream>
using namespace std;
const int N=210,INF=1e9;
int d[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++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}int main(){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) d[i][j]=0;else d[i][j]=INF;}}while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);d[a][b]=min(d[a][b],c);}floyd();while(q--){int a,b;scanf("%d%d",&a,&b);if(d[a][b]> INF/2 ) puts("impossible");else printf("%d\n",d[a][b]);}
}

prim算法求解最短生成树

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int dist[N];
bool st[N];
int n,m;int prim(){memset(dist,0x3f,sizeof dist);int res=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j] && (t==-1 || dist[t]>dist[j]))t=j;}if(i && dist[t]==INF) return INF;if(i) res += dist[t];for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);st[t]=true;}return res;
}int main(){scanf("%d%d",&n,&m);memset(g,0x3f,sizeof g);while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b]=g[b][a]=min(g[a][b],c);}int t=prim();if(t==INF) puts("impossible");else printf("%d",t);
}

kruskal算法求解最小生成树

kruskal算法其中就有一些并查集的思想，把边从权值小的往大的找，当连通了之后就停止，也就是他们的父节点相同。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=200010,INF=0x3f3f3f3f;
int p[N];
struct Edge{int a,b,w;
}edges[M];
int res,cnt;
int n,m;bool cmp(struct Edge a,struct Edge b){return a.w<b.w;
}int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}int kruskal(){sort(edges,edges+m,cmp);for(int i=0;i<m;i++){int a=edges[i].a,b=edges[i].b,w=edges[i].w;a=find(a),b=find(b);if(a!=b){	p[a]=b;res += w;cnt++;}}return cnt<n-1 ? INF : res;
}int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);edges[i]={a,b,c};}for(int i=1;i<=n;i++) p[i]=i;int t=kruskal();if(t==INF) puts("impossible");else printf("%d",t);
}

染色法判定二分图

**总体思想：**二分图就是分成两边，然后一边染一个色，如果最后的出现重复染色的情况（即染色冲突），就不是二分图

#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=200010;
int h[N],e[M],ne[M],idx;
int color[N];
int n,m;
void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}bool dfs(int u,int c){color[u]=c;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!color[j]){if(!dfs(j,3-c)) return false;}else if(color[j]==c) return false;}return true;
}int main(){scanf("%d%d",&n,&m);memset(h,-1,sizeof h);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);add(b,a);}bool flag=true;for(int i=1;i<=n;i++){if(!color[i]){if(!dfs(i,1)){flag=false;break;}}}if(flag) puts("Yes");else puts("No");
}

匈牙利算法求解二分图最大匹配

#include<iostream>
#include<cstring>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
bool st[N];
int n1,n2,m;
int match[N];void add(int a,int b){e[idx] = b;ne[idx] = h[a];h[a] = idx ++;
}bool find(int u){for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=true;if(!match[j] || find(match[j])){match[j]=u;return true;}}}return false;
}int main(){scanf("%d%d%d",&n1,&n2,&m);memset(h,-1,sizeof h);while(m--){int a,b;scanf("%d%d",&a,&b);add(a,b);}int res=0;for(int i=1;i<=n1;i++){memset(st,false,sizeof st);if(find(i)) res++;}printf("%d",res);
}