转载

广度优先搜索

广度优先搜索:

      可确保找到最优解,但是因扩展出来的节点较多,且多数节点都需要保存,因此需要的存储空间较大。用队列保存节点。

算法:

  1. 把初始节点放入队列中;
  2. 如果队列为空,则问题无解,失败退出;
  3. 把队列的第一节点取出,并记该节点为n;
  4. 考察节点n是否为目标节点。若是,则得到问题的解,成功退出;
  5. 若节点不可扩展,则转第2步;
  6. 扩展节点n,将其不没有入队(没有标记)的子节点(弹出队列的节点是已标记的)放入队列中(这一步需要判重),并为每一个子节点设置指向父节点的指针(或记录节点的层次),然后转第2步。

广度优先搜索的代码框架:

      BFS()

      {

           初始化队列

           while(队列不为空且未找到目标节点)

            {

                 取队首节点扩展,并将扩展出的非重复节点放入队尾;

                  必要时要记住每个节点的父节点(求最短路径);

              }

          }

转载于:https://www.cnblogs.com/cynthia-dcg/p/6723459.html

正文到此结束
本文目录