广度寻路算法(BFS算法)

思路

步骤一：选择一个节点，搜索该节点的所有邻接节点，
步骤二：选择其中一个邻接节点进行访问，访问完后，
步骤三：再选择该节点的另一个邻接节点，直到该节点的所有邻接节点都访问完
步骤四：选择邻接节点的下一个节点，重新进行上面的步骤
步骤五：选择没有访问过的节点继续访问，直到全部访问完，结束访问

图示讲解

原始图

步骤一：

选择一个节点

步骤二，三：

访问该节点所有邻接节点(从左到右，从上到下)，先2后3

步骤四：

节点1的邻接节点全部访问完了，选择节点2的邻接节点访问，没有邻接节点或访问完了，就选择节点3的邻接节点继续访问，发现节点3的邻接节点4被访问，就访问节点4的邻接节点

步骤五：

发现节点4没有邻接节点，结束当前当前的访问，选择未被访问的节点5继续访问，重新执行以上步骤，直到没有可访问的节点，即结束访问

核心代码

/// <summary>
/// 广度优先算法/BFS算法
        /// </summary>
        /// <param name="origin">开始节点</param>
        /// <param name="target">目标节点</param>
        /// <param name="passNodeList">最短路径列表</param>
        public static void Search(Node origin, Node target, ref List<Node> passNodeList)
        {
            //清除地图数据
            passNodeList.Clear();
            for(int i = 1; i < mapLengh; i++)
            {
                for(int j = 0; j < mapWidth; j++)
                {
                    //是否访问过
                    if(!map[i, j].bVisit)
                    {
                        //没访问
                        BFSSearch(map[i, j], origin, target, ref passNodeList);
                        
                    }
                }
            }

            //保存路径
            Node currentNode = map[target.X, target.Y];
            while(currentNode.Value != origin.Value)
            {
                passNodeList.Add(currentNode);
                currentNode = currentNode.parent;
            }

            passNodeList.Add(origin);
        }

        /// <summary>
        /// 根据当前节点，检查自己的邻接节点
        /// </summary>
        /// <param name="currentNode">当前节点</param>
        /// <param name="origiNode">原始节点</param>
        /// <param name="target">目标节点</param>
        /// <param name="passNodeList">最短路径列表</param>
        private static void BFSSearch(Node currentNode, Node origiNode, Node target, ref List<Node> passNodeList)
        {
            //将当前节点加入到队列中
            Queue<Node> queue = new Queue<Node>();
            queue.Enqueue(currentNode);

            //当前节点
            while(queue.Count > 0)
            {
               //获取第一个节点
                Node head = queue.Dequeue();
                //检查四个邻居(上下左右)
                List<Node> neighbors = getNeighbor(head);
                for(int i = 0; i < neighbors.Count; i++)
                {
                    //没有访问才可以访问
                    if(!neighbors[i].bVisit && neighbors[i].Value != NODE_BLOCK)
                    {
                        //标记节点为已经访问
                        neighbors[i].bVisit = true;
                        neighbors[i].parent = head;
                        queue.Enqueue(neighbors[i]);

                        //记录中间路径节点
                        if(neighbors[i].Value == target.Value)
                        {
                            return;
                        }
                    }
                }
            }

        }


        /// <summary>
        /// 邻接节点
        /// </summary>
        /// <param name="currentNode">当前节点</param>
        /// <returns></returns>
        private static List<Node> getNeighbor(Node currentNode)
        {
            List<Node> nodes = new List<Node>();
            int x = currentNode.X;
            int y = currentNode.Y;
            if(x - 1 >= 0)
            {
                //左边
                nodes.Add(map[x - 1, y]);
            }
            if(x + 1 >= 0 && x + 1 < mapLengh)
            {
                //右边
                nodes.Add(map[x + 1, y]);
            }

            if(y - 1 >= 0)
            {
                //上边
                nodes.Add(map[x, y - 1]);
            }

            if(y + 1 >= 0 && y + 1 < mapWidth)
            {
                //下边                
                nodes.Add(map[x, y + 1]);
            }
            return nodes;
        }
    }

完整代码

BFS完整代码

@RequestMapping("/save")
public R save(@Valid @RequestBody BrandEntity brand){
    brandService.save(brand);

    return R.ok();
}