本文主要叙述了图的遍历算法中的广度优先搜索（Breadth-First-Search）算法，是非常经典的算法，可供C++程序员参考借鉴之用。具体如下：
首先，图的遍历是指从图中的某一个顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊的图的遍历。图的遍历主要有两种算法：广度优先搜索（Breadth-First-Search）和深度优先搜索（Depth-First-Search）。
一、广度优先搜索（BFS）的算法思想
广度优先搜索类似于二叉树的层序遍历，它的基本思想就是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，…，wi，然后再依次访问w1，w2，…，wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点……依次类推，直到图中所有顶点都被访问过为止。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记录正在访问的顶点的下一层顶点。
如上图所示，为一个有向图，从顶点2开始广度优先遍历整个图，可知结果为2，0，3，1。
二、BFS算法实现
与树相比，图的不同之处在于它存在回路/环，因此在遍历时一个顶点可能被访问多次。为了防止这种情况出现，我们使用一个访问标记数组visited[]来标记顶点是否已经被访问过。
在广度优先搜索一个图之前，我们首先要构造一个图，图的存储方式主要有两种：邻接矩阵、邻接表。这里我们使用邻接表来存储图：
简单起见，我们先假设从起始顶点可以达到其他所有顶点。以有向图为例，C++代码实现：
/*************************************************************************
> File Name: BFS.cpp
> Author: SongLee
************************************************************************/
#include
#include
using namespace std;
/* 邻接表存储有向图 */
class Graph
{
int V; // 顶点的数量
list *adj; // 邻接表
void BFSUtil(int v, bool visited[]);
public:
Graph(int V); // 构造函数
void addEdge(int v, int w); // 向图中添加一条边
void BFS(int v); // BFS遍历
};
/***** 构造函数 *****/
Graph::Graph(int V)
{
this->V = V;
adj = new list[V]; // 初始化V条链表
}
/* 添加边，构造邻接表 */
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // 将w加到v的list
}
/* 从顶点v出发广度优先搜索 */
void Graph::BFSUtil(int v, bool visited[])
{
// BFS辅助队列
list queue;
// 将当前顶点标记为已访问并压入队列
visited[v] = true;
queue.push_back(v);
list::iterator i;
while(!queue.empty())
{
// 出队
v = queue.front();
cout