【题目来源】
【题目描述】
一个有 n 个结点的无向连通图，这些结点以编号：1，2，...，n 进行编号，现给出结点间的连接关系。
请以结点 1 为起点，按广度优先搜索（bfs）、优先访问小编号结点的顺序遍历并输出该图。
【输入格式】
第一行为两整数，n 和 e，表示 n 个顶点，e 条边。（2≤n，e≤10）
以下 e 行每行两个数，表示两个结点是连通的。
【输出格式】
只有一行，为节点按照广度优先、小编号结点优先访问的结果。
【输入样例】
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5
【输出样例】
1 2 3 4 5
【数据范围】
2≤n，e≤10
【算法分析】
● 链式前向星：
大佬 yxc 指出“链式前向星”就是“多单链表”，每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中：
e[idx]：存储序号为 idx 的边的终点值
ne[idx]：存储序号为 idx 的边指向的边的序号（模拟链表指针）
h[a]：存储头结点 a 指向的边的序号
val[idx]：存储序号为 idx 的边的权值（可选）
【算法代码一：链式前向星】
本代码需注意的是“小编号结点优先访问”。
请详阅代码，注意实现技巧。特别注意第 20 行的 vector<int> v; 以及第 26 行的 sort(v.begin(),v.end());。
#include <bits/stdc++.h>
using namespace std;const int N=12;
int h[N],e[N<<1],ne[N<<1],idx;
bool st[N];void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void bfs(int u) {queue<int> q;q.push(u);st[u]=true;cout<<u<<" ";while(!q.empty()) {int t=q.front();q.pop();vector<int> v;for(int i=h[t]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) v.push_back(j);}sort(v.begin(),v.end());for(int x:v) {if(st[x]) continue;st[x]=true;q.push(x);cout<<x<<" ";}}
}int main() {int n,m;cin>>n>>m;memset(h,-1,sizeof h);while(m--) {int a,b;cin>>a>>b;add(a,b),add(b,a);}bfs(1);return 0;
}/*
in:
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5out:
1 2 3 4 5
*/
【算法代码二：邻接矩阵】
#include <bits/stdc++.h>
using namespace std;const int N=12;
int g[N][N];
bool st[N];
int n,m;void bfs(int u) {queue<int> q;q.push(u);st[u]=true;cout<<u<<" ";while(!q.empty()) {int t=q.front();q.pop();for(int i=1; i<=n; i++) {if(g[t][i]==1 && !st[i]) {st[i]=true;q.push(i);cout<<i<<" ";}}}
}int main() {cin>>n>>m;while(m--) {int a,b;cin>>a>>b;g[a][b]=1,g[b][a]=1;}bfs(1);return 0;
}/*
in:
5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5out:
1 2 3 4 5
*/
【参考文献】