C# 广度优先遍历(BFS)算法实现

Gretel ·

更新时间:2024-11-13

· 616 次阅读

定义

在这里插入图片描述
【假设先访问左子树在访问右子树】
那么广度遍历的顺序就是ABCDEF
从上到下，从左到右去访问
运用到格子游戏中，找寻某点到某点的路径
【假设只记录四方位（遍历顺序上左下右）】
向队列中存入起点，遍历该点周围的点，边界看做障碍，遍历到结束点返回
注意需要把该点设置为已访问过的【防止重复访问导致死循环】
当然障碍也是不访问的。最后把符合要求的放入队列中
遍历完该点四周，就移除该点，继续遍历队列中的点。
在这里插入图片描述

次数	队列中元素
1	1
2	1 ，2，11
3	~~1，2，~~ 11，3
4	~~1，2，11，~~ 3，21
5	~~1，2，11，3，~~ 21 ，4
5	~~1，2，11，3，21~~ ，4，22
6	~~1，2，11，3，21 ，4，~~ 22，14
7	~~1，2，11，3，21 ，4，22，~~ 14，32，23

结束。

代码

public IEnumerator PutPosToPath(int target,int end)
{
    yield return null;
    //广度遍历所需【起点，终点，队列】
    Queue path=new Queue();
    //判断终点对应的格子是否能通过
    if(PosDicLabyrinth[end-1].GetComponent().IsObs)
    {
       Debug.Log("终点是障碍");
       isOk=false;
       yield break;
    }
    //////////////////////一口气算出路径/////////////////////////
    //进队
    int front=path.Peek();
    //设置该点为已访问
    ChangeVisited(target,true);
    //如果path队列不为空【如果找不到，就遍历所有能遍历的点的意思】
    while(path.Count!=0)
    {
         //取对头
         path.Euqueue(target);
       //设为已浏览过的
         ChangeVisited(target,true);
         //如果对头等于end，就返回
         if(front==end)
         {
             isOk=true;
             yield break;
         }
         //得到该点四周的点的id值
         int[] s=PosDicLabyrinth[front-1].GetComponent().GirdGroud;
         //遍历
         for(int i=0;i<s.Length;i++)
         {
            if(!IsObsORVisited(s[i]))//如果该点没有访问过而且不是障碍
            {
               path.Enqueue(s[i]);//加入队列中
               ChangeBefore(s[i],front);//改变其父值
               ChangeVisited(s[i],true);//设为已访问
               if(s[i]==end)
               {
                  isOk=true;
                  yield break;
               }
             }
         }
         isOk=false;
   }

效果

在这里插入图片描述