本文主要论述了图的遍历算法中的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
* * * * * * * * * * * * * * * * *
#包含
#包含
用户命名空间STD；
/*旁边的桌子有向图*/
类图形
{
int V； //顶点数
list *adj； //旁边的桌子
voidbfsutil(intv，bool visited[]；
公共：
图形(Intv )； //构造函数
voidaddedge(intv，int w； //向图中添加边
voidBFS(intv )； //BFS导线测量
(；
/*****构造函数*****/
图形：3360图形(intv ) )。
{
this-V=V；
adj=new list[V]； 初始化//V链表
}
/*添加边，做邻桌*
(添加的ge (intv，int w ) ) ) ) ) ) ) ) ) ) )。
{
ADJ[v].push_back(w； //V的list加上w
}
/*从顶点v开始广度优先搜索*
(voidgraph:bfsutil(intv，bool visited[] ) ) ) ) ) ) ) ) ) )。
{
//BFS次队列
列表队列；
//将当前顶点标记为已访问并推入队列
可视[ v ]=true；
queue.push_back(v
list :3360迭代器I；
while (！ queue.empty () )
{
//离开队伍
v=queue.front (；
cout v ' '；
queue.pop_front (；
//检测出队伍的顶点s的所有邻接顶点
//如果有尚未访问的相邻节点，请访问它并将其推入队列
for(I=adj[v].Begin )； I！=adj[v].end (； I )
{
if (！ 可视[ * I ] )
{
可视[ * I ]=true；
queue.push_back(*I；
}
}
}
}
/** 广度优先搜索 **/void Graph::BFS(int v)
{
// 初始化访问标记数组
bool *visited = new bool[V];
for(int i=0; i
visited[i] = false;
// 假设从给定顶点可以到达图的所有顶点
BFSUtil(v, visited);
}
/* 测试 */
int main()
{
// 创建图
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Following is BFS Traversal (starting from vertex 2) n";
g.BFS(2);
cout << endl;
return 0;
}
上面是假设从起始顶点开始能够访问到图的所有顶点。如果不能到达所有顶点，即存在多个连通分量呢？那么我们就要对每个连通分量都进行一次广度优先搜索。
伪代码如下：
bool visited[MAX_VERTEXT_NUM]; // 访问标记数组
void BFS(Graph G) // 设访问函数为visit()
{
for(i=0; i
visited[i] = false; // 初始化
for(i=0; i
if(!visited[i]) // 对每个连通分量调用一次BFS
BFS(G,i); // Vi未访问过，从Vi开始BFS
}
void BFSUtil(Graph G, int v)
{
visit(v); // 访问初始顶点
visited[v] = true; // v已访问
Enqueue(Q, v); // 顶点v入队列
while(!isEmpty(Q))
{
Dequeue(Q, v); // 顶点v出队列
for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v))
if(!visited[w]) // 检测v的所有邻接点
{
visit(w); // 若w未访问，访问之
visited[w]=true; // 标记
Enqueue(Q, w); // 顶点w入队列
}
}
}
根据伪代码，相信不难写出对于多个连通分量的图的广度优先搜索。我们只需要修改BFS()函数部分：
void Graph::BFS()
{
// 初始化访问标记数组
bool *visited = new bool[V];
for(int i=0; i
visited[i] = false;
// 对每个连通分量调用一次BFSUtil()，从0号顶点开始遍历
for(int i=0; i
if(!visited[i])
BFSUtil(i, visited);
}
对于无向图的广度优先搜索，只是邻接表不一样，其他的都是一样的。我们只需要修改addEdge(v, w)函数：
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // 将w加到v的list
adj[w].push_back(v);
}
三、BFS算法性能分析
1 . 空间复杂度
无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点都需要入队一次，在最坏的情况下，空间复杂度为O(|V|)。
2 . 时间复杂度
当采用邻接表存储时，每个顶点均需搜索一次，故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)。
当采用邻接矩阵存储时，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O(|V|^2)。
注：广度优先搜索(BFS)算法思想有很多应用，比如Dijkstra单源最短路径算法和Prim最小生成树算法。