无向图及树的深度和广度优先搜索 ← 链式前向星

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int M=N<<1;
int n;
int h[N],e[M],ne[M],idx;
bool st[N];

int ans;

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]) { //~i; equivalent to i!=-1;
		int j=e[i];
		if(!st[j]) {
			dfs(j);
		}
	}
}

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]) { //~i; equivalent to i!=-1;
			int j=e[i];
			if(!st[j]) {
				q.push(j);
				st[j]=true; //need to be flagged immediately after being queued
			}
		}
	}
}

int main() {
	cin>>n;
	memset(h,-1,sizeof(h));
	for(int i=0; i<n-1; i++) {
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a); //undirected graph
	}

	cout<<"A kind of DFS:"<<endl;
	dfs(2); //dfs(i),i is node's name

	memset(st,false,sizeof(st));
	cout<<endl;

	cout<<"A kind of BFS:"<<endl;
	bfs(2); //bfs(i),i is node's name

	return 0;
}



/*
in:
6
2 1
3 2
4 3
5 2
6 1

out:
A kind of DFS:
2 5 3 4 1 6
A kind of BFS:
2 5 3 1 4 6
*/

【参考文献】
https://blog.csdn.net/weixin_43350051/article/details/98745300