【题目描述】
基于“邻接表”存图，请编程输出下图的 DFS、BFS 序列。
【基于“邻接表”的 DFS 代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<int> g[N];
bool st[N];
int n,m,x;void dfs(int u) {cout<<u<<" ";st[u]=true;for(int i=0; i<g[u].size(); i++) {int j=g[u][i];if(!st[j]) dfs(j);}
}int main() {cin>>n>>m;while(m--) {int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}cin>>x;dfs(x); //dfs(i),i is node's namereturn 0;
}/*
in:
7 7
3 4
1 2
3 2
4 5
6 5
6 7
7 4
4out:
4 3 2 1 5 6 7
*/
【基于“邻接表”的 BFS 代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<int> g[N];
bool st[N];
int n,m,x;void bfs(int u) {queue<int> q;st[u]=true;q.push(u);while(!q.empty()) {int t=q.front();q.pop();cout<<t<<" ";for(int i=0; i<g[t].size(); i++) {int j=g[t][i];if(!st[j]) {q.push(j);st[j]=true;}}}
}int main() {cin>>n>>m;while(m--) {int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}cin>>x;bfs(x); //bfs(i),i is node's namereturn 0;
}/*
in:
7 7
3 4
1 2
3 2
4 5
6 5
6 7
7 4
4out:
4 3 5 7 2 6 1
*/