BFS求源代码及思路？

Python040

BFS求源代码及思路？,第1张

1、算法用途：

是一种图像搜索演算法。用于遍历图中的节点，有些类似于树的深度优先遍历。这里唯一的问题是，与树不同，图形可能包含循环，因此我们可能会再次来到同一节点。

2、主要思想：

主要借助一个队列、一个布尔类型数组、邻接矩阵完成（判断一个点是否查看过，用于避免重复到达同一个点，造成死循环等），先将各点以及各点的关系存入邻接矩阵。

再从第一个点开始，将一个点存入队列，然后在邻接表中找到他的相邻点，存入队列，每次pop出队列头部并将其打印出来（文字有些抽象，实际过程很简单），整个过程有点像往水中投入石子水花散开。

（邻接表是表示了图中与每一个顶点相邻的边集的集合，这里的集合指的是无序集）

3、代码（java）：

(以上图为例的代码）

1 import java.util.*2  3 //This class represents a directed graph using adjacency list

4 //representation  5 class Graph1 { 6     private static int V// No. of vertices 7     private LinkedList<Integer>awww.ynzzyx.com#Adjacency Lists 8  9     // Constructor10     Graph1(int v) {11         V = v12         adj = new LinkedList[v]13         for (int i = 0i <v++i)14             adj[i] = new LinkedList()15     }16 17     // Function to add an edge into the graph18     void addEdge(int v, int w) {19         adj[v].add(w)20     }21 22     // prints BFS traversal from a given source s23     public void BFS() {24         // Mark all the vertices as not visited(By default25         // set as false)26         boolean visited[] = new boolean[V]27         // Create a queue for BFS28         LinkedList<Integer>queue = new LinkedList<Integer>()29 30         for (int i = 0i <Vi++) {31             if (!visited[i]) {32                 BFSUtil(i, visited, queue)33             }34         }35     }36 37     public void BFSUtil(int s, boolean visited[], LinkedList<Integer>queue) {38         // Mark the current node as visited and enqueue it39         visited[s] = true40         queue.add(s)41 42         while (queue.size() != 0) {43             // Dequeue a vertex from queue and print it44             s = queue.poll()45             System.out.print(s + " ")46 47             // Get all adjacent vertices of the dequeued vertex s48             // If a adjacent has not been visited, then mark it49             // visited and enqueue it50             Iterator<Integer>i = adj[s].listIterator()51             while (i.hasNext()) {52                 int n = i.next()53                 if (!visited[n]) {54                     visited[n] = true55                     queue.add(n)56                 }57             }58         }59     }60 61     // Driver method to62     public static void main(String args[]) {63         Graph1 g = new Graph1(4)64 65         g.addEdge(0, 1)66         g.addEdge(0, 2)67         g.addEdge(1, 2)68         g.addEdge(2, 0)69         g.addEdge(2, 3)70         g.addEdge(3, 3)71 72         System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)")73         g.BFS()74     }75 }

4、复杂度分析：

算法借助了一个邻接表和队列，故它的空问复杂度为O(V）。 遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用结构。 邻接表表示时，查找所有顶点的邻接点所需时间为O(E)，访问顶点的邻接点所花时间为O（V）,此时，总的时间复杂度为O(V+E)。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

扩展资料：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]//表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}//表示上下左右4个方向，int visit[maxn][maxn]//表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

参考资料来源：百度百科-广度优化

参考资料来源：百度百科-深度优化