图：
图有顶点和顶点之间的边组成；
图分为有向图和无向图，还可以根据边长分为有权图和无权图；
我们用临结表来构造图，label表示顶点，动态数组vector中存储从当前顶点出发与当前顶点相通的顶点；
例如，从顶点 0 出发，顶点 0 和 1，2相通，那么我们就令label = 0，vector中存入顶点1，顶点2的图结构即可；
图结构：
struct GraphNode {
int label;
vector<GraphNode *> neighbors; //临接表
GraphNode(int x) : label(x) {};
};
输入图中所示的图结构，对其进行宽度优先搜索：
依然是用数据结构：队列 来帮助实现宽搜的过程：
原因可参考：二叉树的宽度优先搜索：https://www.jianshu.com/p/9a0f3e29b479
宽搜过程：
由于顶点 0 未被访问，将 0 存入队列；
对于队头元素顶点 0 ，所以依次找出由顶点 0 出发的路径相通的点中所有未被访问的点：顶点 1 ，顶点 4，将1，4存入队列；此时顶点 0 判断结束，打印 0 ，弹出队列；
此时，队列头部由原来的 0 变更为第二个存入队列中的顶点 1；
对于队头元素顶点 1 ，依次找出由顶点 1 出发的路径相通的点中所有未被访问的点：顶点 2，将 2 存入队列；此时顶点 1 判断结束，打印 1 ，弹出队列；
此时，队列头部由原来的 1 变更为第三个存入队列中的顶点 4；
对于队头元素顶点 4 ，发现由顶点 4 出发的路径相通的点为被访问过的点，因此顶点 4 判断结束，打印 4，弹出队列；
此时，队列头部由原来的 4 变更为第四个存入队列中的顶点 2；
对于队头元素顶点 2 ，发现由顶点 2 出发的路径相通的点为被访问过的点，因此顶点 2 判断结束，打印 2，弹出队列；
由于顶点 1 被访问过，不再宽搜；
由于顶点 2 被访问过，不再宽搜；
由于顶点 3 未被访问，将 3 存入队列；
此时，队列头部由原来的 2 变更为第五个存入队列中的顶点 3；
对于队头元素顶点 3 ，发现由顶点 3 出发的路径相通的点不存在未访问过的点，因此顶点 3 判断结束，打印 3，弹出队列；
由于顶点 4 被访问过，不再宽搜；
队列为空且全部顶点遍历结束，图的宽搜全过程结束。
My Solution(C/C++)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
struct GraphNode {
int label;
vector<GraphNode *> neighbors;
GraphNode(int x) : label(x) {}
};
class Solution {
public:
void BFS_graph(GraphNode *root, int visit[]) {
queue<GraphNode *> q;
q.push(root);
visit[root->label] = 1;
while (!q.empty()) {
for (int i = 0; i < q.front()->neighbors.size(); i++) {
if (visit[q.front()->neighbors[i]->label] == 0) {
visit[q.front()->neighbors[i]->label] = 1;
q.push(q.front()->neighbors[i]);
}
}
printf("%d ", q.front()->label);
q.pop();
}
}
};
int main() {
const int MAX_N = 5;
GraphNode *Graph[MAX_N];
for (int i = 0; i < MAX_N; i++) {
Graph[i] = new GraphNode(i);
}
Graph[0]->neighbors.push_back(Graph[1]);
Graph[0]->neighbors.push_back(Graph[4]);
Graph[1]->neighbors.push_back(Graph[2]);
Graph[2]->neighbors.push_back(Graph[0]);
Graph[3]->neighbors.push_back(Graph[2]);
Graph[3]->neighbors.push_back(Graph[4]);
Graph[4]->neighbors.push_back(Graph[0]);
int visit[MAX_N] = { 0 };
Solution s;
for (int i = 0; i < MAX_N; i++) {
if (visit[i] == 0) {
printf("从顶点 %d 出发：", Graph[i]->label);
s.BFS_graph(Graph[i], visit);
printf("\n");
}
}
for (int i = 0; i < MAX_N; i++) {
delete Graph[i];
}
return 0;
}
结果
从顶点 0 出发：0 1 4 2
从顶点 3 出发：3
