广度优先搜索(Breadth-First-Search)

广度优先搜索的原理及应用是什么1. 原理广度优先搜索（Breadth-First Search, BFS）是一种图的遍历算法，它从图的起始顶点开始，逐层地向外探索，直到找到目标顶点或者遍历完整个图。

通过利用队列的数据结构，广度优先搜索保证了顶点的访问顺序是按照其距离起始顶点的距离递增的。

广度优先搜索的基本原理如下：1.选择一个起始顶点，将其加入一个待访问的队列（可以使用数组或链表实现）。

2.将起始顶点标记为已访问。

3.从队列中取出一个顶点，访问该顶点，并将其未访问过的邻居顶点加入队列。

4.标记访问过的邻居顶点为已访问。

5.重复步骤3和步骤4，直到队列为空。

广度优先搜索保证了先访问距离起始点近的顶点，然后才访问距离起始点远的顶点，因此可以用来解决一些问题，例如最短路径问题、连通性问题等。

2. 应用广度优先搜索在计算机科学和图论中有着广泛的应用，下面是一些常见的应用场景：2.1 最短路径问题广度优先搜索可以用来找出两个顶点之间的最短路径。

在无权图中，每条边的权值都为1，那么从起始顶点到目标顶点的最短路径就是通过广度优先搜索找到的路径。

2.2 连通性问题广度优先搜索可以用来判断两个顶点之间是否存在路径。

通过从起始顶点开始进行广度优先搜索，如果能够找到目标顶点，就说明两个顶点是连通的；如果搜索完成后仍然未找到目标顶点，那么两个顶点之间就是不连通的。

2.3 图的遍历广度优先搜索可以用来遍历整个图的顶点。

通过从起始顶点开始进行广度优先搜索，并在访问每个顶点时记录下访问的顺序，就可以完成对整个图的遍历。

2.4 社交网络分析广度优先搜索可以用来分析社交网络中的关系。

例如，在一个社交网络中，可以以某个人为起始节点，通过广度优先搜索找出与该人直接或间接连接的人，从而分析人际关系的密切程度、社区结构等。

2.5 网络爬虫广度优先搜索可以用来实现网络爬虫对网页的抓取。

通过从初始网页开始，一层层地向外发现新的链接，并将新的链接加入待抓取的队列中，从而实现对整个网站的全面抓取。

BFS与DFS常考算法整理BFS与DFS常考算法整理PrefaceBFS（Breath-First Search，⼴度优先搜索）与DFS（Depth-First Search，深度优先搜索）是两种针对树与图数据结构的遍历或搜索算法，在树与图相关算法的考察中是⾮常常见的两种解题思路。

Definition of DFS and BFSDFS的:Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.BFS的:Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (orsome arbitrary node of a graph, sometimes referred to as a ‘search key’[1]), and explores all of the neighbor nodes at thepresent depth prior to moving on to the nodes at the next depth level.It uses the opposite strategy as depth-first search, which instead explores the highest-depth nodes first before being forced tobacktrack and expand shallower nodes.So obviously, as their name suggest, DFS focuses on ‘depth’ when searching or traversing while BFS focuses on ‘breath’.By the way, because of DFS’s feature, it’s easy to relate it with ‘Backtracking’ algorithm as the wiki definition mentions. The relationship between DFS and backtracking is well explained by :Backtracking is a more general purpose algorithm.Depth-First search is a specific form of backtracking related to searching tree structures. From Wikipedia:One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along eachbranch before backtracking.It uses backtracking as part of its means of working with a tree, but is limited to a tree structure.Backtracking, though, can be used on any type of structure where portions of the domain can be eliminated - whether or not it isa logical tree. The Wiki example uses a chessboard and a specific problem - you can look at a specific move, and eliminate it,then backtrack to the next possible move, eliminate it, etc.How to Implement DFS and BFSDFSIn tree structure, DFS means we always start from a root node and try to reach the leaf node as direct as possible before we have to backtrack.Order in which the nodes are visitedIn graph, DFS means we start from a random assigned node in the graph, and explores as far as possible along the branch before we have to backtrack.So the key points for DFS are:- How to explore as far as possible?- How to backtrack?How to explore as far as possibleNormally, for tree node, it would have left child or right child, so we would continuously go on exploring current node’s child node until we encounter a null node, then we go back to last node. Repeat above procedures until all nodes have been visited.for graph node, we do the similar exploration: explore as further as possible according to the representation of graph (adjacency list, adjacency matrix or incidence matrix) until we find no more node that hasn’t been visited and connected with current node, then we go back to last node. Repeat above procedures until all nodes have been visited.How to backtrack/go back?‘Go back’ generally can be realized using data structure ——stack—— or by recursion. And if we use stack, it means we would need to push each node we visited in the process of exploring each branch, and pop when we can’t explore further starting from current node. BFSIn tree structure, BFS means we always start from a root node and try to all the other nodes in the same breath before we further try exploring nodes at next depth level. (The same explanation for graph)Order in which the nodes are visitedSo the key points for BFS are:How to explore all nodes of same depth level?How to explore all nodes of same depth level?We can use a queue to do this: Starting from root node of a tree (Or a random node in a graph), we add visit all nodes connected with the starting node and add them to the queue. Then, we poll node from queue one by one and repeat above procedures until all nodes have been visited.Typical Leetcode PrbolemsDFSPath Sum IIGiven a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.Note: A leaf is a node with no children.Example:Given the below binary tree and sum = 22,5/ \4 8/ / \11 13 4/ \ / \7 2 5 1Return:[[5,4,11,2],[5,8,4,5]]My Answerpackage medium2;import java.util.ArrayList;import java.util.List;/*** @author Tom Qian* @email tomqianmaple@* @github https:///bluemapleman* @date 2018年6⽉7⽇*/public class PathSumII{// DFS: make use of recursion to backtrackpublic List<List<Integer>> pathSum(TreeNode root, int sum) {List<List<Integer>> ans=new ArrayList<List<Integer>>();if(root==null)return ans;int goal=sum-root.val;if(goal==0) {if(root.left==null && root.right==null) {List<Integer> tempList=new ArrayList<>();tempList.add(root.val);ans.add(tempList);return ans;}}List<List<Integer>> temp;if((temp=pathSum(root.left, goal)).size()!=0) {for(List<Integer> list:temp) {list.add(0, root.val);ans.add(list);}}if((temp=pathSum(root.right, goal)).size()!=0) {for(List<Integer> list:temp) {list.add(0,root.val);ans.add(list);}}return ans;}}Convert Sorted List to Binary Search TreeGiven a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.Example:Given the sorted linked list: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:/ \-3 9/ /-10 5My Answerpackage medium2;/*** @author Tom Qian* @email tomqianmaple@* @github https:///bluemapleman* @date 2018年6⽉11⽇*/public class ConvertSortedListtoBinarySearchTree{// DFS: make use of recursion to backtrack// find the middle node of sorted linked list, and take it as the root node of the BST.public TreeNode sortedListToBST(ListNode head) {if(head==null)return null;ListNode slow=head,fast=head,followSlow=head;boolean moveFlag=false;while(fast!=null && fast.next!=null) {if(moveFlag)followSlow=followSlow.next;moveFlag=true;slow=slow.next;fast=fast.next.next;}TreeNode root=new TreeNode(slow.val);if(moveFlag) {followSlow.next=null;root.left=sortedListToBST(head);root.right=sortedListToBST(slow.next);}return root;}}Course ScheduleThere are a total of n courses you have to take, labeled from 0 to n-1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?Example 1:Input: 2, [[1,0]]Output: trueExplanation: There are a total of 2 courses to take.To take course 1 you should have finished course 0. So it is possible.Example 2:Input: 2, [[1,0],[0,1]]Output: falseExplanation: There are a total of 2 courses to take.To take course 1 you should have finished course 0, and to take course 0 you shouldalso have finished course 1. So it is impossible.Note:1.The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.2.You may assume that there are no duplicate edges in the input prerequisites.My Answer// DFSpublic boolean canFinish(int numCourses, int[][] prerequisites) {Map<Integer, List<Integer>> map=new HashMap<>();for(int i=0;i<numCourses;i++)map.put(i, new ArrayList<>());for(int i=0;i<prerequisites.length;i++) {map.get(prerequisites[i][0]).add(prerequisites[i][1]);}// start DFS: detect if there is any circle in course graph, i.e. whether DFS starting from certain start point i would lead to the start point again. for(int i=0;i<numCourses;i++) {// Use a set to avoid infinite loop: when met same node twice, ignore it.Set<Integer> set=new HashSet<>();// Use a stack to backtrackArrayDeque<Integer> stack=new ArrayDeque<>();List<Integer> preCourseList=map.get(i);for(Integer preCourse:preCourseList)stack.push(preCourse);while(!stack.isEmpty()) {int preCourse=stack.pop();if(set.contains(preCourse))continue;elseset.add(preCourse);if(preCourse==i)return false;else {preCourseList=map.get(preCourse);for(Integer tempPreCourse:preCourseList) {stack.push(tempPreCourse);}}}}return true;}BFSCourse ScheduleMy Answer// BFSpublic boolean canFinish(int numCourses, int[][] prerequisites) {Map<Integer, List<Integer>> map=new HashMap<>();for(int i=0;i<numCourses;i++)map.put(i, new ArrayList<>());for(int i=0;i<prerequisites.length;i++) {map.get(prerequisites[i][0]).add(prerequisites[i][1]);}// start DFS: detect if there is any circle in course graph, i.e. whether BFS starting from certain start point i would lead to the start point again. for(int i=0;i<numCourses;i++) {// Use a set to avoid infinite loop: when met same node twice, ignore it.Set<Integer> set=new HashSet<>();// Use a queue to remember nodes of same depth levelArrayDeque<Integer> queue=new ArrayDeque<>();List<Integer> preCourseList=map.get(i);for(Integer preCourse:preCourseList)queue.add(preCourse);while(!queue.isEmpty()) {int preCourse=queue.poll();if(set.contains(preCourse))continue;elseset.add(preCourse);if(preCourse==i)return false;else {preCourseList=map.get(preCourse);for(Integer tempPreCourse:preCourseList) {queue.add(tempPreCourse);}}}}return true;}Binary Tree Right Side ViewGiven a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. Example:Input: [1,2,3,null,5,null,4]Output: [1, 3, 4]Explanation:1 <---/ \2 3 <---\ \5 4 <---My Answerpackage medium2;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;/*** @author Tom Qian* @email tomqianmaple@* @github https:///bluemapleman* @date 2018年6⽉12⽇*/public class BinaryTreeRightSideView{public List<Integer> rightSideView(TreeNode root) {List<Integer> ans=new ArrayList<>();if(root==null)return ans;ans.add(root.val);ArrayDeque<TreeNode> queue1=new ArrayDeque<>(),queue2=new ArrayDeque<>();;queue1.add(root);while(!queue1.isEmpty() || !queue2.isEmpty()){TreeNode rightestNode=null;if(!queue1.isEmpty()) {while(!queue1.isEmpty()) {TreeNode fatherNode=queue1.poll();if(fatherNode.right!=null) {queue2.add(fatherNode.right);if(rightestNode==null)rightestNode=fatherNode.right;}if(fatherNode.left!=null) {queue2.add(fatherNode.left);if(rightestNode==null)rightestNode=fatherNode.left;}}}else{while(!queue2.isEmpty()) {TreeNode fatherNode=queue2.poll();if(fatherNode.right!=null) {queue1.add(fatherNode.right);if(rightestNode==null)rightestNode=fatherNode.right;}if(fatherNode.left!=null) {queue1.add(fatherNode.left);if(rightestNode==null)rightestNode=fatherNode.left;}}}if(rightestNode!=null)ans.add(rightestNode.val);}return ans; }}.。

宽度优先搜索的例子宽度优先搜索（或称广度优先搜索，Breadth-First Search，缩写为BFS）是一种用于遍历或搜索树或图结构中的所有节点的算法。

它是从根节点开始，沿着树的宽度遍历树的节点，也就是先遍历节点的所有子节点，然后遍历子节点的所有子节点，以此类推。

它试图尽可能快地找到搜索解决方案，而不考虑解决方案的最优性（optimal）。

历史背景宽度优先搜索是由英国数学家、计算机科学家Charles Darwin在1859年发明的。

他提出了一种以树形结构存储节点关系信息的数据结构，即树结构。

这种数据结构可以表示多个节点之间的父子关系，可以用来表示图的连通状态。

接下来，Darwin的学生Richard Stanley 发现，可以利用这个数据结构，用宽度优先搜索算法来遍历树的所有节点，从而开发出BFS算法。

宽度优先搜索的工作原理BFS的工作原理是从一个节点开始，沿着已经连接的节点，逐渐向外层级遍历。

BFS算法每次只访问一层节点，当发现某一层节点含有搜索目标时，便立即返回结果，不再继续往深层搜索。

BFS算法把要搜索的所有节点都存放在队列中，每次只取出队列头节点，这样保证了每个节点只被访问一次，而且保证了最短的路径会优先被搜索到。

宽度优先搜索的性质1. 点是按照宽度遍历的，即先看当前节点的所有子节点，然后才看到更深的节点。

2. 度优先搜索可以用来搜索图的最短路径，它可以保证搜索到的路径最短；3. 度优先搜索可以用来解决最大或最小化问题，可以用来求出一个最优解；4. 对空间复杂度和时间复杂度都有较高的要求，对于大数据量的图搜索，计算量会很大。

宽度优先搜索的应用1. 计算机网络中，宽度优先搜索算法可以用来查找网络中的最短路径，也可以用来查找最大流量；2. 社交网络中，它可以用来搜索最短路径，也可以用来寻找朋友关系，如从一个用户开始，搜索到他的朋友，再搜索朋友的朋友……；3. 度优先搜索算法可以用来求解地图上从一个城市到另一个城市的最短路径；4. 也可以用来解决八皇后问题，即在8×8的棋盘上摆放8个皇后，使得任意的两个皇后不能处于同一行、同一列或者同一斜线上。

bfs单源最短路径BFS单源最短路径BFS（Breadth First Search）是一种图的遍历算法，用于寻找图中从起点到目标节点的最短路径。

它是一种广度优先的搜索算法，通过逐层遍历，从起点开始向外扩展，直到找到目标节点或者遍历完所有节点。

在这篇文章中，我们将详细介绍BFS单源最短路径算法的原理和应用。

一、原理BFS单源最短路径算法的原理是基于图的遍历和队列的数据结构。

它从起点开始，将起点加入队列中，并标记为已访问。

然后，不断从队列中取出节点，并将其未访问的邻居节点加入队列，并标记为已访问。

这样，每一层的节点都会被逐个访问，直到找到目标节点或者遍历完所有节点。

为了记录每个节点的访问状态和路径长度，我们可以使用两个数组来实现。

一个是visited数组，用于记录节点是否已经访问过；另一个是distance数组，用于记录节点到起点的路径长度。

初始时，visited数组中所有元素都设置为未访问，distance数组中所有元素都设置为无穷大。

起点的visited值为已访问，distance值为0。

在BFS过程中，每当访问一个节点时，我们将其邻居节点的visited值设置为已访问，并将其distance值更新为当前节点的distance值加1。

二、应用BFS单源最短路径算法在实际应用中有着广泛的应用。

以下是几个常见的应用场景：1. 迷宫寻路：BFS算法可以用于解决迷宫寻路问题。

将迷宫中的每个格子看作图中的一个节点，通过BFS算法找到起点到终点的最短路径。

2. 社交网络：BFS算法可以用于社交网络中的好友关系分析。

将每个人看作图中的一个节点，通过BFS算法找到自己到目标用户的最短路径。

3. 网络路由：BFS算法可以用于计算网络中两个节点之间的最短路径。

将网络中的每个节点看作图中的一个节点，通过BFS算法找到起点到目标节点的最短路径。

4. 单词变换：BFS算法可以用于单词变换问题。

将每个单词看作图中的一个节点，通过BFS算法找到起始单词到目标单词的最短路径，每次只能变换一个字母。

浅析深度优先和⼴度优先遍历实现过程、区别及使⽤场景⼀、什么是深度/⼴度优先遍历？ 深度优先遍历简称DFS（Depth First Search），⼴度优先遍历简称BFS（Breadth First Search），它们是遍历图当中所有顶点的两种⽅式。

这两种遍历⽅式有什么不同呢？我们来举个栗⼦： 我们来到⼀个游乐场，游乐场⾥有11个景点。

我们从景点0开始，要玩遍游乐场的所有景点，可以有什么样的游玩次序呢？1、深度优先遍历 第⼀种是⼀头扎到底的玩法。

我们选择⼀条⽀路，尽可能不断地深⼊，如果遇到死路就往回退，回退过程中如果遇到没探索过的⽀路，就进⼊该⽀路继续深⼊。

在图中，我们⾸先选择景点1的这条路，继续深⼊到景点7、景点8，终于发现⾛不动了： 于是，我们退回到景点7，然后探索景点10，⼜⾛到了死胡同。

于是，退回到景点1，探索景点9： 按照这个思路，我们再退回到景点0，后续依次探索景点2、3、5、4、发现相邻的都玩过了，再回退到3，再接着玩6，终于玩遍了整个游乐场： 具体次序如下图，景点旁边的数字代表探索次序。

当然还可以有别的排法。

像这样先深⼊探索，⾛到头再回退寻找其他出路的遍历⽅式，就叫做深度优先遍历（DFS）。

这⽅式看起来很像⼆叉树的前序遍历。

没错，其实⼆叉树的前序、中序、后序遍历，本质上也可以认为是深度优先遍历。

2、⼴度优先遍历 除了像深度优先遍历这样⼀头扎到底的玩法以外，我们还有另⼀种玩法：⾸先把起点相邻的⼏个景点玩遍，然后去玩距离起点稍远⼀些（隔⼀层）的景点，然后再去玩距离起点更远⼀些（隔两层）的景点… 在图中，我们⾸先探索景点0的相邻景点1、2、3、4： 接着，我们探索与景点0相隔⼀层的景点7、9、5、6： 最后，我们探索与景点0相隔两层的景点8、10： 像这样⼀层⼀层由内⽽外的遍历⽅式，就叫做⼴度优先遍历（BFS）。

这⽅式看起来很像⼆叉树的层序遍历。

没错，其实⼆叉树的层序遍历，本质上也可以认为是⼴度优先遍历。

信息学竞赛常用算法一、贪心算法(Greedy Algorithm)贪心算法是一种简单而直观的算法，它的核心思想是每一步都选择最优解，希望最终的结果也能最优。

贪心算法常常用于求解最小生成树、最短路径、背包问题等。

例如，在最小生成树问题中，贪心算法可以根据边的权重选择最小的边，直到生成树包含所有节点。

二、动态规划(Dynamic Programming)动态规划是一种通过将问题分解为子问题，并存储子问题的解来解决复杂问题的方法。

它常常用于求解最长公共子序列、最大子数组和、背包问题等。

动态规划的核心思想是，通过计算和存储子问题的解，避免重复计算，从而提高算法的效率。

三、深度优先(Depth First Search)深度优先是一种用于遍历或图或树的算法，其核心思想是尽可能深入地一个分支，直到无法继续为止，然后回溯到上一个节点，继续其他分支。

深度优先可以用于求解拓扑排序、连通分量、可达性等问题。

四、广度优先(Breadth First Search)广度优先是一种用于遍历或图或树的算法，其核心思想是从根节点开始，依次与当前节点相邻的节点，直到找到目标节点为止。

广度优先可以用于求解最短路径、连通性、迷宫问题等。

五、并查集(Union Find)并查集是一种用于管理元素间的等价关系的数据结构。

并查集主要包括两个操作：查找和合并。

查找操作用于确定元素所属的集合，合并操作用于将两个元素所属的不同集合合并为一个集合。

并查集常常用于求解连通性问题、最小生成树问题等。

六、最小生成树(Minimum Spanning Tree)最小生成树是一种用于连接一个连通图的所有节点，并且边的权重之和最小的树形结构。

最小生成树算法主要包括Prim算法和Kruskal算法。

Prim算法是一种贪心算法，通过选择最小权重的边进行扩展，直到生成树包含所有节点。

Kruskal算法通过不断添加权重最小的边，直到生成树包含所有节点。

七、最短路径(Shortest Path)最短路径是一种从起点到终点的路径中，总权重最小的路径。

bfs dfs 的使用场景BFS和DFS的使用场景BFS（Breadth First Search，广度优先搜索）和DFS（Depth First Search，深度优先搜索）是图遍历算法中常用的两种方法。

它们在不同的场景下有着不同的应用。

本文将分别介绍BFS和DFS的使用场景，并对其特点进行分析。

一、BFS的使用场景1. 最短路径问题：BFS可以求解带权图中的最短路径问题。

通过BFS遍历图的过程中，记录每个顶点到起始顶点的距离，从而得到最短路径。

2. 连通性问题：BFS可以判断无向图或有向图中两个顶点之间是否存在路径。

从起始顶点开始，通过BFS遍历到目标顶点，若能找到路径，则说明两个顶点是连通的。

3. 拓扑排序：BFS可以对有向无环图（DAG）进行拓扑排序，得到图中各个顶点的拓扑序列。

通过BFS遍历图的过程中，记录每个顶点的入度，将入度为0的顶点依次加入拓扑序列中。

4. 游戏寻路：BFS可以用于游戏中的寻路算法。

例如，在迷宫游戏中，可以通过BFS找到从起点到终点的最短路径。

5. 网络爬虫：BFS可以用于网络爬虫的页面抓取。

通过BFS遍历页面链接，从而实现对整个网站的抓取。

二、DFS的使用场景1. 图的连通性：DFS可以判断无向图或有向图中两个顶点之间是否连通。

从起始顶点开始，通过DFS遍历到目标顶点，若能找到路径，则说明两个顶点是连通的。

2. 深度限制搜索：DFS可以用于解决深度限制的搜索问题。

例如在迷宫游戏中，可以通过DFS搜索所有可能的路径，直到找到终点或达到深度限制。

3. 生成树：DFS可以用于生成树的构建。

例如在最小生成树算法中，可以通过DFS遍历图的各个顶点，并按照一定规则选择边加入生成树中。

4. 拓扑排序：DFS也可以对有向无环图（DAG）进行拓扑排序。

通过DFS遍历图的过程中，将已访问的顶点添加到拓扑序列中，最后倒序输出即可得到拓扑排序结果。

5. 回溯算法：DFS可以用于解决回溯问题，如八皇后问题、0-1背包问题等。