树的宽度优先遍历(c++)

 宽度优先遍历，又名广度优先遍历或层序遍历，英文缩写为BFS，全称是 Breadth First Search，也是一种用于遍历或搜索树或图的算法。所谓宽度优先，就是每次都尝试访问同一层的节点。如果同一层都访问完了，再访问下一层。

1. 创建一个队列，辅助 BFS
2. 根结点入队
3. 若队列不为空，队头结点出队并访问该结点，然后将该点的孩子依次入队
4. 重复 3 过程，直到队列为空

 代码1： 

//vector存储树
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
int n;
vector<int> edges[N]; //存树
bool st[N]; //标记哪些结点已经访问过了

void bfs()
{
	queue<int> q;
	q.push(1);
	st[1] = true;

	while (q.size())
	{
		int u = q.front(); q.pop();
		cout << u << " ";

		for (auto v : edges[u])
		{
			if (!st[v])
			{
				q.push(v);
				st[v] = true;
			}
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int a, b; cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}

	bfs();

	return 0;
}

 代码2：

//链式存储树
#include <iostream>
#include <queue>
using namespace std;

const int N = 1e5 + 10;
int h[N], e[N * 2], ne[N * 2], id;
int n;
bool st[N]; //标记哪些结点已经访问过了

void add(int a, int b)
{
	++id;
	e[id] = b;

	ne[id] = h[a];
	h[a] = id;
}

void bfs()
{
	queue<int> q;
	q.push(1);
	st[1] = true;

	while (q.size())
	{
		int u = q.front(); q.pop();
		cout << u << " ";

		for (int i = h[u]; i; i = ne[i])
		{
			int v = e[i];
			if (!st[v])
			{
				q.push(v);
				st[v] = true;
			}
		}
	}
}

int main()
{
	建树
	cin >> n;
	for (int i = 1; i < n; ++i)
	{
		int a, b; cin >> a >> b;
		add(a, b); add(b, a);
	}

	bfs();

	return 0;
}