Chinaunix首页 | 论坛 | 博客
  • 博客访问: 843047
  • 博文数量: 77
  • 博客积分: 821
  • 博客等级: 军士长
  • 技术积分: 1905
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-23 16:17
个人简介

学校:上海交通大学软件工程 学历:硕士 行业:从事流媒体移动开发 QQ: 412595942 邮箱:yiikai1987910@gmail.com

文章分类

全部博文(77)

文章存档

2016年(4)

2015年(15)

2014年(16)

2013年(12)

2012年(21)

2011年(9)

分类: C/C++

2014-12-24 15:22:44

      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很容易就能解出,给出以下自己实现的代码:

点击(此处)折叠或打开

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

  3. #include "stdafx.h"
  4. #include <list>
  5. #include <vector>
  6. #include <vld.h>

  7. typedef enum
  8. {
  9.     WHITE = 0,
  10.     GRAY,
  11.     BLACK
  12. }Vcolor;

  13. typedef struct {
  14.     int connectX;
  15.     int connectY;
  16.     int X;
  17.     int y;
  18.     Vcolor color; //0 white 1 gray 2 black
  19.     int value;
  20. }routeNode;

  21. bool checkBalck(std::vector<routeNode>& bv,int n, int m )
  22. {
  23.     std::vector<routeNode>::iterator itr;
  24.     for (itr = bv.begin(); itr != bv.end(); itr++)
  25.     {
  26.         if ((*itr).X == n && (*itr).y == m)
  27.         {
  28.             if ((*itr).color == Vcolor::BLACK)
  29.             {
  30.                 return true;
  31.             }
  32.             else
  33.             {
  34.                 return false;
  35.             }
  36.         }
  37.     }
  38. }

  39. void printRoute(std::vector<routeNode>& bv)
  40. {
  41.     std::list<routeNode> shortestRoute;
  42.     routeNode end = bv.back();
  43.     bv.pop_back();
  44.     shortestRoute.push_front(end);
  45.     while (1)
  46.     {
  47.         std::vector<routeNode>::iterator itr;
  48.         for (itr = bv.begin(); itr != bv.end(); itr++)
  49.         {
  50.             if ((*itr).X == end.connectX && (*itr).y == end.connectY)
  51.             {
  52.                 shortestRoute.push_front((*itr));
  53.                 break;
  54.             }
  55.         
  56.         }
  57.         end = (*itr);
  58.         if (end.X == 0 && end.y == 0)
  59.         {
  60.             break;
  61.         }
  62.     }
  63.     
  64.     std::list<routeNode>::iterator itr;
  65.     for (itr = shortestRoute.begin(); itr != shortestRoute.end(); itr++)
  66.     {
  67.         printf("%d,%d\n",itr->X,itr->y);
  68.     }
  69. }

  70. void clearMem(std::list<routeNode*>& glist)
  71. {
  72.     std::list<routeNode*>::iterator itr;
  73.     for (itr = glist.begin(); itr != glist.end(); itr++)
  74.     {
  75.         delete (*itr);
  76.     }
  77.     glist.clear();
  78. }

  79. void BFS(const int mazes[][5],routeNode* in,routeNode* out)
  80. {
  81.     int n=0 , m = 0;
  82.     std::vector<routeNode> blackVec;
  83.     std::list<routeNode*> grayList;
  84.     std::list<routeNode*> copylist;
  85.     in->color = Vcolor::GRAY;
  86.     grayList.push_back(in);
  87.     while (1)
  88.     {
  89.         if (grayList.empty())
  90.         {
  91.             printf("not found a shortest route");
  92.             return;
  93.         }
  94.         routeNode *tmpV;
  95.         tmpV = grayList.front();
  96.         copylist.push_back(tmpV);
  97.         grayList.pop_front();
  98.         if (tmpV->X == out->X && tmpV->y == out->y)
  99.         {
  100.             routeNode *tmpnode = new routeNode;
  101.             tmpnode->connectX = tmpV->connectX;
  102.             tmpnode->connectY = tmpV->connectY;
  103.             tmpnode->X = tmpV->X;
  104.             tmpnode->y = tmpV->y;
  105.             tmpnode->color = Vcolor::BLACK;
  106.             tmpnode->value = mazes[tmpV->X][tmpV->y];
  107.             blackVec.push_back(*tmpnode);
  108.             printf("This is Terminate route\n");
  109.             printRoute(blackVec);
  110.             delete tmpnode;
  111.             clearMem(copylist);
  112.             return;
  113.         }
  114.         tmpV->color = Vcolor::BLACK;
  115.         blackVec.push_back(*tmpV);
  116.         if (tmpV->X - 1 >= 0 && tmpV->X - 1 < 5 && mazes[tmpV->X - 1][tmpV->y] != 1 && !checkBalck(blackVec, tmpV->X - 1, tmpV->y))
  117.         {

  118.             routeNode *tmpnode = new routeNode;
  119.             tmpnode->connectX = tmpV->X;
  120.             tmpnode->connectY = tmpV->y;
  121.             tmpnode->X = tmpV->X - 1;
  122.             tmpnode->y = tmpV->y;
  123.             tmpnode->color = Vcolor::GRAY;
  124.             tmpnode->value = mazes[tmpV->X - 1][tmpV->y];
  125.             grayList.push_back(tmpnode);
  126.         }
  127.         if (tmpV->X + 1 >= 0 && tmpV->X + 1 < 5 && mazes[tmpV->X + 1][tmpV->y] != 1 && !checkBalck(blackVec, tmpV->X + 1, tmpV->y))
  128.         {
  129.             routeNode *tmpnode = new routeNode;
  130.             tmpnode->connectX = tmpV->X;
  131.             tmpnode->connectY = tmpV->y;
  132.             tmpnode->X = tmpV->X + 1;
  133.             tmpnode->y = tmpV->y;
  134.             tmpnode->color = Vcolor::GRAY;
  135.             tmpnode->value = mazes[tmpV->X + 1][tmpV->y];
  136.             grayList.push_back(tmpnode);
  137.         }
  138.         if (tmpV->y + 1 >= 0 && tmpV->y + 1 < 5 && mazes[tmpV->X][tmpV->y + 1] != 1 && !checkBalck(blackVec, tmpV->X, tmpV->y+1))
  139.         {
  140.             routeNode *tmpnode = new routeNode;
  141.             tmpnode->connectX = tmpV->X;
  142.             tmpnode->connectY = tmpV->y;
  143.             tmpnode->X = tmpV->X;
  144.             tmpnode->y = tmpV->y + 1;
  145.             tmpnode->color = Vcolor::GRAY;
  146.             tmpnode->value = mazes[tmpV->X][tmpV->y+1];
  147.             grayList.push_back(tmpnode);
  148.         }
  149.         if (tmpV->y - 1 >= 0 && tmpV->y - 1 < 5 && mazes[tmpV->X][tmpV->y - 1] != 1 && !checkBalck(blackVec, tmpV->X, tmpV->y-1))
  150.         {
  151.             routeNode *tmpnode = new routeNode;
  152.             tmpnode->connectX = tmpV->X;
  153.             tmpnode->connectY = tmpV->y;
  154.             tmpnode->X = tmpV->X;
  155.             tmpnode->y = tmpV->y - 1;
  156.             tmpnode->color = Vcolor::GRAY;
  157.             tmpnode->value = mazes[tmpV->X][tmpV->y - 1];
  158.             grayList.push_back(tmpnode);
  159.         }
  160.     }

  161. }


  162. int _tmain(int argc, _TCHAR* argv[])
  163. {
  164.     const int mazes[5][5] = {
  165.         0, 1, 0, 0, 0,
  166.         0, 1, 0, 1, 0,
  167.         0, 0, 0, 0, 0,
  168.         0, 1, 1, 1, 0,
  169.         0, 0, 0, 1, 0,
  170.     };
  171.     routeNode *in = new routeNode; *in = { 0, 0, 0, 0, Vcolor::WHITE, 0 };
  172.     routeNode *out = new routeNode; *out = { 0, 0, 4, 4, Vcolor::WHITE, 0 };
  173.     BFS(mazes, in, out);
  174.     delete out;
  175.     getchar();
  176.     return 0;
  177. }


阅读(1929) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~