本文共 3432 字,大约阅读时间需要 11 分钟。
广度优先搜索算法(Breadth-First-Search),又译作宽度优先搜索,或横向优先搜索,简称BFS,是一种。简单的说,BFS是从开始,沿着树的宽度遍历树的。如果所有节点均被访问,则算法中止。广度优先搜索的实现一般采用open-closed表。
因为所有节点都必须被储存,因此BFS的空间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。注:另一种说法称BFS的空间复杂度为 O(BM),其中 B 是最大分支系数,而 M 是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题。
最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为 O(|V| + |E|),其中 |V| 是节点的数目,而 |E| 是图中边的数目。
若所有边的长度相等,广度优先搜索算法是最佳解——亦即它找到的第一个解,距离根节点的边数目一定最少;但对一般的图来说,BFS并不一定回传最佳解。这是因为当图形为加权图(亦即各边长度不同)时,BFS仍然回传从根节点开始,经过边数目最少的解;而这个解距离根节点的距离不一定最短。这个问题可以使用考虑各边权值,BFS的改良算法()来解决。然而,若非加权图形,则所有边的长度相等,BFS就能找到最近的最佳解。
广度优先搜索算法能用来解决图论中的许多问题,例如:
由起点开始,执行广度优先搜索算法后所经过的所有节点,即为包含起点的一个连接元件。
广度优先搜索,即BFS(Breadth First Search),是一种相当常用的图算法,其特点是:每次搜索指定点,并将其所有未访问过的邻近节点加入搜索队列,循环搜索过程直到队列为空。
算法描述如下:
(1)将起始节点放入队列尾部
(2)While(队列不为空)
取得并删除队列首节点Node
处理该节点Node
把Node的未处理相邻节点加入队列尾部
使用该算法注意的问题:
(1)使用该算法关键的数据结构为:队列,队列保证了广度渡优先,并且每个节点都被处理到
(2)新加入的节点一般要是未处理过的,所以某些情况下最初要对所有节点进行标记
(3)广度优先在实际使用时,很对情况已超出图论的范围,将新节点加入队列的条件不再局限于
相邻节点这个概念。例如,使用广度优先的网络爬虫在抓取网页时,会把一个链接指向的网页中的所有
URL加入队列供后续处理。
典型实例:
1.图的遍历(VC6.0/VS2005)
//
//广度优先之节点遍历 //1-----5----------9 //| | | //| | | //2-----4----6-----8 //| | | //| | | //3----------7-----10 // 1 2 3 4 5 6 7 8 //1 0 1 0 0 1 0 0 0 //2 1 0 1 1 0 0 0 0 //3 0 1 0 0 0 0 1 0 //4 0 1 0 0 1 1 0 0 //5 1 0 0 1 0 0 0 0 //6 0 0 0 1 0 0 1 1 //7 0 0 1 0 0 1 0 0 //8 0 0 0 0 0 1 0 0#include
#include using namespace std;//节点数
#define M 10//图的矩阵表示
int matrix[M][M] = { 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0};
//访问标记,初始化为0, int visited[M + 1];//graph traverse
void GT_BFS() { visited[1] = 1; queue q; q.push(1); while(!q.empty()) { int top = q.front(); cout << top<<" ";//输出 q.pop(); int i ; for(i = 1; i <= M; ++i) { if(visited[i] == 0 && matrix[top - 1][i - 1 ] == 1) { visited[i] = 1; q.push(i); } } } }int main()
{ GT_BFS();//输出结果为1 2 5 3 4 9 7 6 8 10 system("pause"); return 0; }2.有权最短路径,Dijkstra
///
//广度优先搜索之有权最短路径,Dijkstra算法 // 1---(1)-->5 // | | //(2) (12) // | | // 2--(13)---4---(2)--6--(2)--8 // | | //(4) (5) // | | // 3----(1)----------7 // 1 2 3 4 5 6 7 8 //1 0 2 0 0 1 0 0 0 //2 2 0 4 7 0 0 0 0 //3 0 4 0 0 0 0 1 0 //4 0 7 0 0 12 2 0 0 //5 1 0 0 12 0 0 0 0 //6 0 0 0 2 0 0 5 2 //7 0 0 1 0 0 5 0 0 //8 0 0 0 0 0 2 0 0#include
#include using namespace std;//节点数
#define M 8//图的矩阵表示
int matrix[M][M] = { 0, 2, 0, 0, 1, 0, 0, 0, 2, 0, 4, 13, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 1, 0, 0, 13, 0, 0, 12, 2, 0, 0, 1, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 5, 2, 0, 0, 1, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0};
//保存每个节点的最短路径,初始化为0xFFFF
int dist[M + 1] ={0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF}; //calculate the distance void Dijkstra_BFS(int startNodeNum) { dist[startNodeNum] = 0; queue q; q.push(startNodeNum); while(!q.empty()) { int top = q.front(); q.pop(); cout< int i ; for(i = 1; i <= M; ++i) { if(matrix[top - 1][i - 1 ] != 0 && (dist[top] + matrix[top - 1][i -1]) < dist[i] ) { dist[i] = dist[top] + matrix[top - 1][i -1]; q.push(i); } } } } void PrintDist() {for(int i = 1; i <= M; ++i)
cout<}int main()
{ Dijkstra_BFS(1); PrintDist(); system("pause"); return 0; }转载地址:http://fphbi.baihongyu.com/