Bfs

文章和代码曾经归档至【Github仓库：algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。首先，计算机中罕用的数据结构是栈和队列。 栈：先进后出，通常利用是递归，DFS。队列：先进先出，通常利用是 BFS 。过程如下所示： 每次取出队头元素，并且把其拓展的元素放在队尾。 下面过程可知，遍历的过程以及入队的过程都是依照BFS(1 2 3...10)的程序进行的 BFS宽搜：每次扩大最早的点。（因而能够找到一条最短的门路） DFS深搜：每次扩大第一个点。 BFS中常见问题，迷宫问题。 模板1.判重 入队时判重，保障每个边只会入队一次，从而保障工夫复杂度是线性的。（因而有判重数组的存在，宽搜也能够搜寻环），st[ ]。 2.队列 queue <--- 初始状态 // 队列保留初始状态while(queue 非空){ t < --- 队头 // t保留队头 for(拓展t) { ver < --- 新节点 // 拓展t失去的新节点 if(!st[ver]) // 如果拓展的新节点没有被搜寻过 { ver ----> 队尾 // 保留至队尾 } }}献给阿尔吉侬的花束阿尔吉侬是一只聪慧又慵懒的小白鼠，它最善于的就是走各种各样的迷宫。 明天它要挑战一个十分大的迷宫，研究员们为了激励阿尔吉侬尽快达到起点，就在起点放了一块阿尔吉侬最喜爱的奶酪。 当初研究员们想晓得，如果阿尔吉侬足够聪慧，它起码须要多少工夫就能吃到奶酪。 迷宫用一个 R×C 的字符矩阵来示意。 字符 S 示意阿尔吉侬所在的地位，字符 E 示意奶酪所在的地位，字符 # 示意墙壁，字符 . 示意能够通行。 阿尔吉侬在 1 个单位工夫内能够从以后的地位走到它上下左右四个方向上的任意一个地位，但不能走出地图边界。 输出格局 第一行是一个正整数 T，示意一共有 T 组数据。 ...