BFS - 广度优先搜索

      BFS的原理介绍网上比较多，参考这个http://blog.csdn.net/raphealguo/article/details/7523411
     举个应用的例子：
      定义一个二维数组： 
int maze[5][5] = {
    0, 1, 0, 0, 0,
    0, 1, 0, 1, 0,
    0, 0, 0, 0, 0,
    0, 1, 1, 1, 0,
    0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 

这个是典型的寻找最短路径问题，用BFS很容易就能解出，给出以下自己实现的代码：

// BFS.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <list>
#include <vector>
#include <vld.h>

typedef enum
{
    WHITE = 0,
    GRAY,
    BLACK
}Vcolor;

typedef struct {
    int connectX;
    int connectY;
    int X;
    int y;
    Vcolor color; //0 white 1 gray 2 black
    int value;
}routeNode;

bool checkBalck(std::vector<routeNode>& bv,int n, int m )
{
    std::vector<routeNode>::iterator itr;
    for (itr = bv.begin(); itr != bv.end(); itr++)
    {
        if ((*itr).X == n && (*itr).y == m)
        {
            if ((*itr).color == Vcolor::BLACK)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

void printRoute(std::vector<routeNode>& bv)
{
    std::list<routeNode> shortestRoute;
    routeNode end = bv.back();
    bv.pop_back();
    shortestRoute.push_front(end);
    while (1)
    {
        std::vector<routeNode>::iterator itr;
        for (itr = bv.begin(); itr != bv.end(); itr++)
        {
            if ((*itr).X == end.connectX && (*itr).y == end.connectY)
            {
                shortestRoute.push_front((*itr));
                break;
            }

        }
        end = (*itr);
        if (end.X == 0 && end.y == 0)
        {
            break;
        }
    }

    std::list<routeNode>::iterator itr;
    for (itr = shortestRoute.begin(); itr != shortestRoute.end(); itr++)
    {
        printf("%d,%d\n",itr->X,itr->y);
    }
}

void clearMem(std::list<routeNode*>& glist)
{
    std::list<routeNode*>::iterator itr;
    for (itr = glist.begin(); itr != glist.end(); itr++)
    {
        delete (*itr);
    }
    glist.clear();
}

void BFS(const int mazes[][5],routeNode* in,routeNode* out)
{
    int n=0 , m = 0;
    std::vector<routeNode> blackVec;
    std::list<routeNode*> grayList;
    std::list<routeNode*> copylist;
    in->color = Vcolor::GRAY;
    grayList.push_back(in);
    while (1)
    {
        if (grayList.empty())
        {
            printf("not found a shortest route");
            return;
        }
        routeNode *tmpV;
        tmpV = grayList.front();
        copylist.push_back(tmpV);
        grayList.pop_front();
        if (tmpV->X == out->X && tmpV->y == out->y)
        {
            routeNode *tmpnode = new routeNode;
            tmpnode->connectX = tmpV->connectX;
            tmpnode->connectY = tmpV->connectY;
            tmpnode->X = tmpV->X;
            tmpnode->y = tmpV->y;
            tmpnode->color = Vcolor::BLACK;
            tmpnode->value = mazes[tmpV->X][tmpV->y];
            blackVec.push_back(*tmpnode);
            printf("This is Terminate route\n");
            printRoute(blackVec);
            delete tmpnode;
            clearMem(copylist);
            return;
        }
        tmpV->color = Vcolor::BLACK;
        blackVec.push_back(*tmpV);
        if (tmpV->X - 1 >= 0 && tmpV->X - 1 < 5 && mazes[tmpV->X - 1][tmpV->y] != 1 && !checkBalck(blackVec, tmpV->X - 1, tmpV->y))
        {

            routeNode *tmpnode = new routeNode;
            tmpnode->connectX = tmpV->X;
            tmpnode->connectY = tmpV->y;
            tmpnode->X = tmpV->X - 1;
            tmpnode->y = tmpV->y;
            tmpnode->color = Vcolor::GRAY;
            tmpnode->value = mazes[tmpV->X - 1][tmpV->y];
            grayList.push_back(tmpnode);
        }
        if (tmpV->X + 1 >= 0 && tmpV->X + 1 < 5 && mazes[tmpV->X + 1][tmpV->y] != 1 && !checkBalck(blackVec, tmpV->X + 1, tmpV->y))
        {
            routeNode *tmpnode = new routeNode;
            tmpnode->connectX = tmpV->X;
            tmpnode->connectY = tmpV->y;
            tmpnode->X = tmpV->X + 1;
            tmpnode->y = tmpV->y;
            tmpnode->color = Vcolor::GRAY;
            tmpnode->value = mazes[tmpV->X + 1][tmpV->y];
            grayList.push_back(tmpnode);
        }
        if (tmpV->y + 1 >= 0 && tmpV->y + 1 < 5 && mazes[tmpV->X][tmpV->y + 1] != 1 && !checkBalck(blackVec, tmpV->X, tmpV->y+1))
        {
            routeNode *tmpnode = new routeNode;
            tmpnode->connectX = tmpV->X;
            tmpnode->connectY = tmpV->y;
            tmpnode->X = tmpV->X;
            tmpnode->y = tmpV->y + 1;
            tmpnode->color = Vcolor::GRAY;
            tmpnode->value = mazes[tmpV->X][tmpV->y+1];
            grayList.push_back(tmpnode);
        }
        if (tmpV->y - 1 >= 0 && tmpV->y - 1 < 5 && mazes[tmpV->X][tmpV->y - 1] != 1 && !checkBalck(blackVec, tmpV->X, tmpV->y-1))
        {
            routeNode *tmpnode = new routeNode;
            tmpnode->connectX = tmpV->X;
            tmpnode->connectY = tmpV->y;
            tmpnode->X = tmpV->X;
            tmpnode->y = tmpV->y - 1;
            tmpnode->color = Vcolor::GRAY;
            tmpnode->value = mazes[tmpV->X][tmpV->y - 1];
            grayList.push_back(tmpnode);
        }
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    const int mazes[5][5] = {
        0, 1, 0, 0, 0,
        0, 1, 0, 1, 0,
        0, 0, 0, 0, 0,
        0, 1, 1, 1, 0,
        0, 0, 0, 1, 0,
    };
    routeNode *in = new routeNode; *in = { 0, 0, 0, 0, Vcolor::WHITE, 0 };
    routeNode *out = new routeNode; *out = { 0, 0, 4, 4, Vcolor::WHITE, 0 };
    BFS(mazes, in, out);
    delete out;
    getchar();
    return 0;
}