bfs，即广度优先遍历，在搜索方面常用于搜寻最短路，其基本实现方式是通过队列存储节点：将初始节点放入队列，再依次将该节点相邻的节点依次放入队列。遍历完成后就弹出初始节点，周而复始，直到队列为空。

下面给出几种bfs的实现方法(每种方法的图存储方式不同)

直接存边bfs：

1 #include 
2 #include 
3 using namespace std;
4 typedef struct edge{
5     int u,v;
6 }edge;
7 edge e[100];
8 int vis[100];
9 int n;//边数
10 void bfs(int m){//bfs起始点
11     queue q;
12     q.push(m);
13     vis[m]=1;
14     cout<>n;
29     for (int i=1;i<=n;i++)
30         cin>>e[i].u>>e[i].v;
31     bfs(1);
32     return 0;
33 }

邻接矩阵bfs：

1 #include 
2 #include 
3 using namespace std;
4 int adj[100][100];
5 int k;//点数
6 int n;//边数
7 int vis[100];
8 void bfs(int m){
9     queue q;
10     q.push(m);
11     cout<>k>>n;
27     for (int i=1;i<=n;i++){
28         int u,v;
29         cin>>u>>v;
30         adj[u][v]=1;
31         adj[v][u]=1;
32     }
33     bfs(1);
34     return 0;
35 }

邻接表bfs：

2 #include 
3 #include 
4 using namespace std;
5 vector >adj;
6 int vis[100];
7 int k;//点数
8 int n;//边数
9 void bfs(int m){
10     queue q;
11     q.push(m);
12     cout<>k>>n;
28     adj.resize(k+1);
29     for (int i=1;i<=n;i++){
30         int u,v;
31         cin>>u>>v;
32         adj[u].push_back(v);
33         adj[v].push_back(u);
34     }
35     bfs(1);
36     return 0;
37 }

链式前向星实现：

2 #include 
3 using namespace std;
4 int cnt=0;
5 int nxt[100];
6 int head[100];
7 int to[100];
8 int vis[100];
9 int k;
10 int n;
11 void insert(int u,int v){
12     nxt[++cnt]=head[u];
13     head[u]=cnt;
14     to[cnt]=v;
15 }
16 void bfs(int m){
17     queue q;
18     q.push(m);
19     cout<>k>>n;
35     for (int i=1;i<=n;i++){
36         int u,v;
37         cin>>u>>v;
38         insert(u,v);
39         insert(v,u);
40     }
41     bfs(1);
42     return 0;
43 }