嗯...

 

BFS是图的搜索算法之一，与深度优先搜索不同的是：广度优先搜索会先搜索到与起始点距离较近的点，而深搜却是沿着一个分支递归到最后....

 

与深搜的对比：

 

深搜用栈(stack)来实现：

 

1.把起始顶点压入栈中

2.每次从栈顶取出一个顶点，搜索所有它的未访问相邻顶点，把这些顶点压入栈中

3.重复执行第二步操作，直到找到所要找的站的顶点货着栈为空时结束程序

 

广搜用队列(queue)来实现：

1.把起始顶点放到队列中

2.每次从队首取出一个顶点，查看这个顶点所有的未访问相邻顶点，把它们那放到队尾

 

BFS的一般写法：

1 void bfs(起始点){ 2     将起始点放入队列中; 3     while (如果队列不为空){ 4         访问队列中队首元素x; 5         删除队首元素； 6         for (x 所有相邻点){ 7             if (该点未被访问过且合法){ 8                 将该点加入队列末尾;  9             } 10         } 11     } 12     队列为空，广搜结束; 13 }

 

嗯.....那就先说到这吧....