关键字:广度优先，搜索算法，图论，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 << top << endl;
        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 << i << ":" << dist[i] << endl;
}

int main()
{
    Dijkstra_BFS(1);
    PrintDist();
    system("pause");
    return 0;
}