图的遍历模板

图的遍历

BFS

求距离

#include<bits/stdc++.h>using namespace std;int n, m, k,q[20001],dist[20001];
vector<int> edge[20001];int main(){scanf("%d%d%d",&n,&m,&k);for (int i = 1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);edge[x].push_back(y);edge[y].push_back(x);}while(k--){int s,t;scanf("%d%d",&s,&t);memset(dist,255,sizeof(dist));dist[s]=0;int front=1,rear=1;q[1] = s;while(front<=rear){int x=q[front];front++;for(auto y:edge[x]){if(dist[y]==-1){dist[y]=dist[x]+1;q[++rear] = y;}}}printf("%d\n", dist[t]);}
}
/*
输入
3 2 2
1 2
2 3
1 2
1 3*/

迷宫

#include<bits/stdc++.h>using namespace std;int D[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int n,m,q[1000001][2],dist[1001][1001];
char s[1001][1002];int main(){scanf("%d%d",&n,&m);for (int i = 1; i <= n;i++){scanf("%s", s[i] + 1);}int sx,sy,ex,ey;for(int i=1;i<=n;i++){for (int j = 1; j <= m;j++){if(s[i][j]=='S'){sx = i,sy = j;}else if(s[i][j]=='E'){ex = i, ey = j;}}}memset(dist,255,sizeof(dist));dist[sx][sy]=0;int front =1,rear=1;q[1][0]=sx,q[1][1]=sy;while(front <= rear){int x=q[front][0],y=q[front][1];++front;for (int i = 0; i < 4;i++){int xx = x + D[i][0],yy=y+D[i][1];if(xx<1||xx>n||yy<1||yy>m){continue;}if(s[xx][yy]!='X'&&dist[xx][yy]==-1){dist[xx][yy]=dist[x][y]+1;q[++rear][0]=xx;q[rear][1] = yy;}}}printf("%d\n", dist[ex][ey]);
}

马的遍历

#include <bits/stdc++.h>using namespace std;int D[8][2] = {{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};
int n,m,x,y,dist[401][401];
int q[160001][2];
bool b[401][401];int main(){scanf("%d%d%d%d",&n,&m,&x,&y);memset(dist,-1,sizeof(dist));memset(b, false, sizeof(b));int front = 1,rear=1;q[1][0]=x,q[1][1]=y;dist[x][y] = 0, b[x][y] = true;while(front<=rear){int xx=q[front][0],yy=q[front][1];front++;for (int i = 0; i < 8;i++){int xxx = xx + D[i][0], yyy = yy + D[i][1];if (xxx < 1 || xxx > n || yyy < 1 || yyy > m){continue;}else if(!b[xxx][yyy]){b[xxx][yyy]=true;dist[xxx][yyy] = dist[xx][yy] + 1;q[++rear][0] = xxx, q[rear][1] = yyy;}}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%d ", dist[i][j]);}printf("\n");}
}

求距离2

#include <bits/stdc++.h>using namespace std;int n,m,k,s,t,dist[20001];
vector<pair<int, int>> edge[100001];
vector<int> c[100001];int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);edge[a].push_back({b,c});edge[b].push_back({a, c});}for (; k--;){scanf("%d%d",&s,&t);memset(dist, 255, sizeof(dist));for (int i = 0; i <= n;i++)c[i].clear();dist[s] = 0;c[0].push_back(s);for (int i = 0; !c[i].empty();i++){int front = 0, rear = c[i].size() - 1;while (front <= rear){int x = c[i][front];front++;for (auto y : edge[x]){if (!y.second && dist[y.first] == -1){dist[y.first]=dist[x];c[i].push_back(y.first);++rear;}}if(dist[t]!=-1){break;}for(auto y:edge[x]){if(y.second&&dist[y.first]==-1){dist[y.first]=dist[x]+1;c[i+1].push_back(y.first);}}}}printf("%d\n", dist[t]);}
}/*
4 4 1
1 2 0
1 3 1
2 4 1
3 4 1
1 4*/

DFS

连通块计数

#include <bits/stdc++.h>using namespace std;int n,m;
vector<int > edge[20001];
bool b[20001];inline void dfs(int x){b[x]=true;for(auto y:edge[x]){if(!b[y]){dfs(y);}}
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);edge[x].push_back(y);edge[y].push_back(x);}int cnt = 0;memset(b,false,sizeof(b));for(int i=1;i<=n;i++){if(!b[i]){dfs(i);cnt++;}}printf("%d", cnt);
}

哈密顿回路

#include <bits/stdc++.h>using namespace std;int n,m,k;
vector<int> edge[30];
bool b[9];bool dfs(int x,int c){if(c==n&&x==k) return true;for(auto i:edge[x]){if(!b[i]){b[i]=true;if(dfs(i,c+1))return true;b[i] = false;}}return false;
}int main(){scanf("%d%d",&n,&m);for (int i = 1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);edge[x].push_back(y);edge[y].push_back(x);}scanf("%d", &k);if(dfs(k,0))printf("Yes");elseprintf("No");}
/*
4 5
1 2
2 3
1 3
1 4
2 4
4
*/