广度优先搜索

问题背景迷宫问题是一个经典的算法问题，指标是找到从迷宫的终点到起点的最短门路，在程序中能够简略的形象成一个M*N的二维数组矩阵，而后咱们须要从这个二维矩阵中找到从终点到起点的最短门路。其中，通常应用 0 示意可行走的路，用 1 示意障碍物，终点和起点别离标记为 S 和 E。例如，下图是一个简略的迷宫问题： 0 0 0 0 0 00 1 0 1 1 00 1 0 0 0 00 0 1 1 0 00 1 0 1 0 0S 0 0 0 E 0在这个迷宫中，数字 0 示意可行走的路，数字 1 示意障碍物，S 示意终点，E 示意起点。 利用场景迷宫问题在现实生活中有很多理论利用例子： 机器人导航：在机器人导航中，机器人须要依据传感器获取的信息来布局门路，从终点到起点。这个过程能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。游戏设计：迷宫问题能够利用于各种类型的游戏中，如谜题解决游戏和角色扮演游戏。在这些游戏中，玩家须要找到一条从终点到起点的门路，同时防止遇到障碍物或危险。主动驾驶：在主动驾驶汽车中，汽车须要遵循交通规则、防止障碍物并找到最短门路。这也能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。网络路由：网络路由器须要在各种网络拓扑中寻找最佳门路，以确保数据包在网络中传输时尽可能疾速和牢靠。这也能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。地图利用：在地图利用中，用户须要依据终点和起点寻找最佳门路。这能够应用迷宫问题的算法来实现，如应用 A* 算法来找到最短门路。罕用算法求解迷宫问题的算法有多种，其中最常见的是深度优先搜寻（DFS）算法、广度优先搜寻（BFS）算法和A*搜索算法。本文将别离介绍这两种算法的实现形式及其优缺点。 深度优先搜寻（DFS）算法深度优先搜寻（DFS）是一种基于栈或递归的搜索算法，从终点开始，一直地往深处遍历，直到找到起点或无奈持续往下搜寻。在迷宫问题中，DFS 会先选取一个方向往前走，直到无奈后退为止，而后返回上一个节点，尝试其余方向。 DFS 的核心思想是回溯，即在走到绝路时，返回上一个节点，从而摸索其余方向。具体实现上，能够应用递归函数或栈来保护待拜访的节点。 import java.util.*;public class MazeSolver { // 迷宫的行数和列数 static final int ROW = 5; static final int COL = 5; // 迷宫的地图，0 示意能够通过的路，1 示意墙壁，2 示意曾经走过的路 static int[][] map = new int[][]{ {0, 1, 1, 1, 1}, {0, 0, 0, 1, 1}, {1, 1, 0, 0, 1}, {1, 1, 1, 0, 1}, {1, 1, 1, 0, 0} }; // 迷宫的终点和起点 static final int startX = 0; static final int startY = 0; static final int endX = 4; static final int endY = 4; // 存储搜寻门路 static List<int[]> path = new ArrayList<>(); // DFS 搜寻迷宫 public static void dfs(int x, int y) { // 如果以后地位是起点，则搜寻实现 if (x == endX && y == endY) { // 打印搜寻门路 for (int[] p : path) { System.out.print("(" + p[0] + "," + p[1] + ") "); } System.out.println("(" + x + "," + y + ")"); return; } // 标记以后地位曾经走过 map[x][y] = 2; // 将以后地位退出搜寻门路 path.add(new int[]{x, y}); // 别离搜寻以后地位的上下左右四个方向 if (x > 0 && map[x-1][y] == 0) { dfs(x-1, y); } if (y > 0 && map[x][y-1] == 0) { dfs(x, y-1); } if (x < ROW-1 && map[x+1][y] == 0) { dfs(x+1, y); } if (y < COL-1 && map[x][y+1] == 0) { dfs(x, y+1); } // 如果没有找到起点，将以后地位从搜寻门路中移除 path.remove(path.size()-1); } public static void main(String[] args) { dfs(startX, startY); }}深度优先搜寻（DFS）的长处： ...

你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在“如何从迷宫中寻找出路”这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索可以:编写国际跳棋AI,计算最少走多少步就可获胜;编写拼写检查器,计算最少编辑多少个地方就可将错拼的单词改成正确的单词,如将READED改为READER需要编辑一个地方;根据你的人际关系网络找到关系最近的医生。要解决最短路径问题，需要两个步骤。使用图来建立问题模型。使用广度优先搜索解决问题。图是什么图用于模拟不同的东西是如何相连的。图由节点(node)和边(edge)组成。一个节点可能与众多节点直接相连,这些节点被称为邻居。树是一种特殊的图,其中没有往后指的边。在图中，边用来表示节点之间的关系，若关系是有方向的，则图为有向图(directed graph)，此时图中的边有箭头。若关系没有方向，则图为无向图(undirected graph),此时图中的边没有箭头，直接相连的节点互为邻居。如上图是有向图，Rama是Alex的邻居。广度优先搜索广度优先搜索是一种用于图的查找算法,可帮助回答两类问题。第一类问题:从节点A出发,有前往节点B的路径吗?第二类问题:从节点A出发,前往节点B的哪条路径最短?两类问题并没有本质区别，在实现层面仅仅第二类需要携带路径的信息，因为最终通常需要返回这个路径。示例：假设你经营着一个芒果农场,需要寻找芒果销售商,以便将芒果卖给他。在Facebook,你与芒果销售商有联系吗?为此,你可在朋友中查找。算法原理：（1）创建一个朋友名单。（2）依次检查名单中的每个人,看看他是否是芒果销售商。（3）假设你没有朋友是芒果销售商,那么你就必须在朋友的朋友中查找。检查名单中的每个人时,你都将其朋友加入名单。若找到，则表示你与芒果销售商有联系；由于在广度优先搜索的执行过程中,搜索范围从起点开始逐渐向外延伸,即先检查一度关系,再检查二度关系，我们找到的芒果销售商也是关系最近的。执行过程中，一度关系在二度关系之前加入查找名单，所以我们优先检查一度关系，然后才到二度，依次进行。这需要存储名单的数据结构有“先进先出”的特性，这种数据结构就是队列(queue)。队列类似于栈,队列也是一种操作受限的数据结构，你不能随机地访问队列中的元素。队列只支持两种操作:入队和出队。队列是一种先进先出(First In First Out,FIFO)的数据结构,而栈是一种后进先出(Last In First Out,LIFO)的数据结构。实现图使用散列表存储每个节点与邻近节点关系。graph = {}graph[“you”] = [“alice”, “bob”, “claire”]graph[“bob”] = [“anuj”, “peggy”]graph[“alice”] = [“peggy”]graph[“claire”] = [“thom”, “jonny”]graph[“anuj”] = []graph[“peggy”] = []graph[“thom”] = []graph[“jonny”] = []实现算法算法的工作原理：一点需要注意：检查一个人之前,要确认之前没检查过他,这很重要，因为有可能会导致无限循环。完整算法如下：from collections import dequegraph = {}graph[“you”] = [“alice”, “bob”, “claire”]graph[“bob”] = [“anuj”, “peggy”]graph[“alice”] = [“peggy”]graph[“claire”] = [“thom”, “jonny”]graph[“anuj”] = []graph[“peggy”] = []graph[“thom”] = []graph[“jonny”] = []def person_is_seller(name): return name[-1] == ’m’def search(name): search_queue = deque() search_queue += graph[name] searched = [] while search_queue: person = search_queue.popleft() if not person in searched: if person_is_seller(person): print(person + " is a mango seller!") return True else: search_queue += graph[person] searched.append(person) return Falsesearch(“you”)算法的时间复杂度：O(V + E)，其中V为顶点(vertice)数,E为边数。请继续关注我的公众号文章 ...

本人习惯使用pyhton2进行编程，因此beautifulsoup也是使用python2版本的，但据说python2明年就要停止支持了，忧伤得很。。。0x01 题目要求如图所示，在页面源码当中找到5个flag，然后拼接起来，还给了flagA的示例。flagA：打开站点是一个ctf-wiki的demo站点，了解这个站的人应该都知道它的体量，所以手动一个个找是不现实的，需要用到爬虫了（题目名称也暗示了）。0x02 解题思路我考虑使用广度优先搜索（BFS）实现一个网站爬虫，不了解广度搜索的童鞋可以自行百度。具体实现方法如下：建立待请求链接visiting_urls和已请求链接visited_urls的2个列表（也可看做队列）从visiting_urls取出一条链接，使用requrests.get请求页面源码在源码中正则匹配flag字段beautifulsoup获取页面中所有的a标签，符合要求的加入visiting_urlsvisiting_urls不为空，则执行[2]当中需要考虑2个问题：去重问题：当爬取链接时，难免会遇到存在不同位置的url指向同一个页面，爬取时不需要再请求相同页面，因此要对爬取到的url进行去重。方法如下：维护visiting_urls visited_urls列表，比对爬取url与已爬取过的url是否重复；根据mkdocs网站url特点，包含"../“的是回溯链接，此类链接不需要再次请求。正则匹配问题：这个方面没有多想，写个能使用的正则匹配规则就行，在本题中需要2种正则匹配：匹配flag：flag[ABCDE]，我的目的是匹配到flag的标志，而不是把flag整个都匹配出来，因为我不清楚flag当中有没有其他奇怪字符，防止出现漏匹配的情况；匹配url：[\w/]+index.html，目的是匹配路径为字母数字（不包含”.."）且末尾是"index.html"的url。到此，整个任务就完成了。0x03 完整脚本#coding=utf-8import requests,refrom bs4 import BeautifulSoups = requests.session()s.keep_alive=Falseflagre = re.compile(‘flag[ABCDE]’)urlre = re.compile(’[\w/]+index.html’)base_url = ‘http://23.236.125.55:1000/ctf-wiki/‘flagA_url = ‘http://23.236.125.55:1000/ctf-wiki/assembly/mips/readme/index.html’visiting_urls = [‘http://23.236.125.55:1000/ctf-wiki/index.html’]visited_urls = []def find_flag(url,html): flist = flagre.findall(html) if len(flist) > 0: print flist,urldef BFS(): url = visiting_urls[0] del(visiting_urls[0]) visited_urls.append(url) r = s.get(url) #r.encoding = ‘utf-8’ find_flag(url,r.text) soup = BeautifulSoup(r.text,’lxml’) for a in soup.find_all(‘a’): link = a[‘href’] if urlre.findall(link) and “..” not in link: new_url = base_url + link if new_url not in visited_urls and new_url not in visiting_urls: visiting_urls.append(new_url)if name == ‘main’: while len(visiting_urls) > 0: BFS()上面思路已经提到了，该脚本只能提取到包含flag标志的页面，而不是flag本身，因此还需要手动访问这些页面去寻找flag（手动狗头），如果还想直接显示flag，那就需要优化一下正则匹配了。提示一点，在获取到页面源码后，使用r.encoding = ‘utf-8’转码会导致EOFError，具体原因不详，本想能够匹配中文页面，结果画蛇添足搞了半天以为匹配没成功。提示两点，requests.session()的好处，相较于直接requests.get()，可以防止建立过多的HTTP连接，导致新连接无法建立的问题。参考页面：https://segmentfault.com/q/10…执行效果如下：最后拼接一下，完事了。 ...

题目You need to find the largest value in each row of a binary tree.Example:Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9]讲解又是树的层次遍历题。相同的题我已经做了两个了：637. Average of Levels in Binary Tree、429. N-ary Tree Level Order TraversalJava代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { List<Integer> result = new ArrayList<>(); public List<Integer> largestValues(TreeNode root) { if(root==null){ return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int count = 1; while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int floorSize = 0; for(int i=0;i<count;i++){ TreeNode now = queue.poll(); list.add(now.val); if(now.left!=null){ queue.offer(now.left); floorSize++; } if(now.right!=null){ queue.offer(now.right); floorSize++; } } int max = list.get(0); for(Integer x:list){ if(max<x){ max = x; } } count = floorSize; result.add(max); } return result; }} ...

题目Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.Example 1:Input: 3 / \ 9 20 / \ 15 7Output: [3, 14.5, 11]Explanation:The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].Note:The range of node’s value is in the range of 32-bit signed integer.讲解这题跟429. N-ary Tree Level Order Traversal很像。都是广度优先遍历树（也就是按层级遍历树）。java代码/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { List<Double> result = new ArrayList<>(); public List<Double> averageOfLevels(TreeNode root) { if(root==null){ return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); int children_num=1; while(!queue.isEmpty()){ double sum = 0; int count=0; for(int i=0;i<children_num;i++){ TreeNode now = queue.poll(); sum += now.val; if(now.left!=null){ count++; queue.offer(now.left); } if(now.right!=null){ count++; queue.offer(now.right); } } sum /= children_num; result.add(sum); children_num = count; } return result; }} ...

题目Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).For example, given a 3-ary tree:We should return its level order traversal:[ [1], [3,2,4], [5,6]]Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.[题目地址]https://leetcode.com/problems…讲解这道题我真的想了有很久，刚开始想用队列，但是发现不知道怎么分割每一层，于是就想还是用递归。后来越发想不明白，最后看了别人的解法。其实分割每一层是可以做到的。以后要多练习。java代码/// Definition for a Node.class Node { public int val; public List<Node> children; public Node() {} public Node(int _val,List<Node> _children) { val = _val; children = _children; }};/class Solution { List<List<Integer>> result = new ArrayList<List<Integer>>(); public List<List<Integer>> levelOrder(Node root) { if(root==null){ return result; } Queue<Node> queue = new LinkedList<>(); queue.offer(root); int children_num = 1; List<Integer> rootList = new ArrayList<Integer>(); rootList.add(root.val); result.add(rootList); while(!queue.isEmpty()){ List<Integer> list = new ArrayList<>(); int count=0; for(int i=0;i<children_num;i++){ Node now = queue.poll(); if(now.children!=null){ for(Node node:now.children){ queue.offer(node); list.add(node.val); count++; } } } children_num = count; if(list.size()>0){ result.add(list); } } return result; }} ...

题目There are N rooms and you start in room 0. Each room has a distinct number in 0, 1, 2, …, N-1, and each room may have some keys to access the next room. Formally, each room i has a list of keys rooms[i], and each key rooms[i][j] is an integer in [0, 1, …, N-1] where N = rooms.length. A key rooms[i][j] = v opens the room with number v.Initially, all the rooms start locked (except for room 0). You can walk back and forth between rooms freely.Return true if and only if you can enter every room.Example 1:Input: [[1],[2],[3],[]]Output: trueExplanation: We start in room 0, and pick up key 1.We then go to room 1, and pick up key 2.We then go to room 2, and pick up key 3.We then go to room 3. Since we were able to go to every room, we return true.Example 2:Input: [[1,3],[3,0,1],[2],[0]]Output: falseExplanation: We can’t enter the room with number 2.Note:1 <= rooms.length <= 10000 <= rooms[i].length <= 1000The number of keys in all rooms combined is at most 3000.题目地址讲解这是一道典型的图的遍历，这里我采用了广度优先遍历，广度优先遍历可以用队列这种数据结构来实现。同时还需要一个Set用于记录已经访问过的room。感觉这道题还是比较简单的java代码class Solution { public boolean canVisitAllRooms(List<List<Integer>> rooms) { Set<Integer> set = new HashSet(); Queue<Integer> queue = new LinkedList<>(); for(Integer x:rooms.get(0)){ queue.offer(x); } while(!queue.isEmpty()){ int room = queue.poll(); if(set.contains(room)){ continue; }else{ set.add(room); List<Integer> list = rooms.get(room); if(list!=null && list.size()>0){ for(Integer x: list){ queue.offer(x); } } } } for(int i=1;i<rooms.size();i++){ if(!set.contains(i)){ return false; } } return true; }} ...