栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【数据结构与算法】二维数组的深度和广度优先搜索

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【数据结构与算法】二维数组的深度和广度优先搜索

1.深度优先搜索

定义:深度优先搜索如字面意思,朝着一个方向先找到底,如果不满足条件了就返回上一个节点,直到找不到了

图示:

 代码:

        /// 
        /// 寻路四个方向
        /// 
        private static Vector2Int[] _path = new Vector2Int[4]
        {
            new Vector2Int(-1, 0),
            new Vector2Int(1, 0),
            new Vector2Int(0, 1),
            new Vector2Int(0, -1)
        };
        
        /// 
        /// 深度优先搜索
        /// 
        public static void DepthFristSearch(INode[,] _board,INode target,ref List blocks)
        {
            int count = 0;
            for (int i = 0; i < _path.Length; i++)
            {
                count++;
                Vector2Int pos = _path[i] + target.ArrayPos;
                if (pos.x > _board.GetLength(0) - 1 
                    || pos.y > _board.GetLength(1) - 1
                    ||pos.x < 0 || pos.y < 0)
                {
                    Debug.Log("越界");
                }
                else
                {
                    INode block = _board[pos.x, pos.y];
                    if (block != null && block.NodeType == target.NodeType && !ListIsHaveBlock(blocks, block))
                    {
                        blocks.Add(_board[pos.x, pos.y]);
                        GameUtlis.Waits(blocks.Count*0.1f, () =>
                        {
                            _board[pos.x, pos.y].SetColor();
                        });
                        DepthFristSearch(_board,block, ref blocks);
                    }
                    else if (count == _path.Length)
                    {
                        return;
                    }
                }
            }
        }

        /// 
        /// 是否重复节点
        /// 
        private static bool ListIsHaveBlock(List list,INode block)
        {
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i].GUID == block.GUID)
                {
                    return true;
                }
            }
            return false;
        }

2.广度优先搜索

定义:广度优先搜索字面含义就是先找完当前的节点,找完之后找下一层的节点,如此重复,直到无法继续,则停止

图示:

 代码:

        public static void BreadthFristSearch(INode[,] _board, INode target, ref List blocks)
        {
            List nodes = new List();
            nodes.Add(target);
            BreadthFrist(_board, nodes, ref blocks);
        }
        
        /// 
        /// 二维数组的广度优先搜索
        /// 
        private static void BreadthFrist(INode[,] _board,List target,ref List blocks)
        {
            List nodes = new List();
            for (int i = 0; i < target.Count; i++)
            {
                for (int j = 0; j < _path.Length; j++)
                {
                    Vector2Int pos = _path[j] + target[i].ArrayPos;
                    if (pos.x > _board.GetLength(0) - 1 
                        || pos.y > _board.GetLength(1) - 1
                        ||pos.x < 0 || pos.y < 0)
                    {
                        Debug.Log("越界");
                    }
                    else
                    {
                        INode block = _board[pos.x, pos.y];
                        if (block != null && block.NodeType == target[i].NodeType && !ListIsHaveBlock(blocks, block))
                        {
                            nodes.Add(block);
                            GameUtlis.Waits(blocks.Count*0.1f, () =>
                            {
                                _board[pos.x, pos.y].SetColor();
                            });
                            blocks.Add(block);
                        }
                    }
                    if (j == _path.Length-1)//达到最大搜索阈值
                    {
                        BreadthFrist(_board,nodes,ref blocks);
                    }
                }
            }
        }
        
        /// 
        /// 是否重复节点
        /// 
        private static bool ListIsHaveBlock(List list,INode block)
        {
            for (int i = 0; i < list.Count; i++)
            {
                if (list[i].GUID == block.GUID)
                {
                    return true;
                }
            }
            return false;
        }

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/959796.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号