数据结构与算法——广度优先搜索BFS

广度优先搜索：从一个顶点开始，搜索所有可到达的顶点的方法叫做广度优先搜索。
思想：从起始顶点1开始，访问邻接于他的顶点B={2， 3， 4}，再访问邻接于B的顶点C={5， 6， 7}……

这种搜索方式可以用队列实现。


伪代码如下：

BreadthFirstSearch(v)
	//从顶点v开始的广度优先搜索
	把顶点v标记为已到达顶点；
	初始化队列Q，其中仅包含一个元素v;
	while (Q不空)
	{
		从队列中删除顶点w;
	 	令u为邻接于w的顶点;
		while (u!=NULL)
		{
			if ( u 尚未被标记) 
			{
				把u 加入队列；
				把u 标记为已到达顶点； 
			}
			u = 邻接于w 的下一个顶点；
		} 	
	}
}

C++代码如下：

void bfs(int v, int reach[], int label)
{
	arrayQueue<int> q(10); // 创建一个队列 
	reach[v] = label; // v是出发的点，标记上label，表示已经到达过	
	q.push(v); // 将顶点v加入到队列q中
	while (!q.empty()) // 队列不为空就继续 
	{
		int w = q.front(); // 队列首元素
		q.pop(); // 删除队列的首元素
		vertexIterator<T> *iw = iterator(w); // 顶点w的迭代器，返回所有邻接于w的顶点 
		int u; 
		while ((u = iw->next()) != 0) // 判断w是否还有邻接于他的顶点 
		{
			if (reach[u] == 0) // 判断邻接于w的顶点是否已经标记过  
			{
				q.push(u); // 将顶点u加入队列
				reach[u] = label; // 将顶点u标记为已到达
			} 
		} 
		delete iw; // 释放空间
	} 
} 

时间复杂度分析：
1.从顶点v 出发，可到达的每一个顶点都被加上标记，且每个顶点只加入到队列中一次，也只从队列中删除一次。
2.当一个顶点从队列中删除时，需要考察它的邻接点

• 当使用邻接矩阵时，它的邻接矩阵中的行只遍历一次。 Q(n).
• 当使用邻接链表时，它的邻接链表只遍历一次。 Q(顶点的出度) .

3.总时间(如果有s 个顶点被标记)

• 当使用邻接矩阵时， Q(sn)
• 当使用邻接链表时， Q(dout) (对于无向图／网络来说，顶点的出度就等于它的度。)