【题目描述】
基于“链式前向星”存图，请编程输出下图的 DFS、BFS 序列。
【基于“链式前向星”的 DFS 代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int h[N],e[N<<1],ne[N<<1],idx;
bool st[N];
int n,m,x;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u) {cout<<u<<" ";st[u]=true;for(int i=h[u]; ~i; i=ne[i]) {int j=e[i];if(!st[j]) dfs(j);}
}int main() {cin>>n>>m;memset(h,-1,sizeof(h));while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a); //undirected graph}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 7 6 5 3 2 1
*/
【基于“链式前向星”的 BFS 代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+5;
int h[N],e[N<<1],ne[N<<1],idx;
bool st[N];
int n,m,x;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}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=h[t]; ~i; i=ne[i]) {int j=e[i];if(!st[j]) {q.push(j);st[j]=true;}}}
}int main() {cin>>n>>m;memset(h,-1,sizeof(h));while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a); //undirected graph}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 7 5 3 6 2 1
*/