本文共 1911 字,大约阅读时间需要 6 分钟。
图是搜索算法的最常用数据结构,因此需要先储备一些图的概念。
我总结在另一篇博客: BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多广度优先的思路比较简单,写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。可以通过下面这张图直接理解:
1.BFS算法思路简述 设置一个数组visited[]存放每个结点是否被访问过 (1)访问第一个顶点,置已访问标志; (2)取第一个邻接点; (3)若未被访问过,则对其进行DFS; (4)取下一个邻接点; 重复(3)、(4)直至所有邻接顶点取完。 BFS是一种分层的搜索过程(典型:树的层次遍历) ,每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此, 广度优先搜索不是一个递归的过程。 2.图的代码实现public class Graph{ //无向图 private int v; //顶点的个数 private LinkedListadj[]; //邻接表 public Graph(int v){ this.v=v; adj = new LinkedList[v]; for(int i=0;i (); } } //无向图一条边存两次 public void addEdge(int s, int t){ adj[s].add(t); adj[t].add(s); }}
3.BFS代码实现
搜索一条从 s 到 t 的最短路径: 队列的作用:因为广度优先搜索是逐层访问的,当我们访问到第 k 层的顶点的时候,我们需要把第 k 层的顶点记录下来,稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以,我们用这个队列来实现记录的功能。 从顶点 s 开始,广度优先搜索到顶点 t 后,prev 数组中存储的就是搜索的路径。不过这个路径是反向存储的。比如,通过顶点 2 的邻接表访问到顶点 3,那 prev[3]就等于 2。public void bfs(int s, int t) { if (s == t) return; //visited 是用来记录已经被访问的顶点,用来避免顶点被重复访问。 boolean[] visited = new boolean[v]; visited[s]=true; //queue 用来存储本身已被访问、但相连的顶点还没有被访问的顶点。 Queuequeue = new LinkedList<>(); queue.add(s); //prev 用来记录搜索路径。 int[] prev = new int[v]; for (int i = 0; i < v; ++i) { prev[i] = -1; } // while (queue.size() != 0) { int w = queue.poll(); for (int i = 0; i < adj[w].size(); ++i) { int q = adj[w].get(i); if (!visited[q]) { prev[q] = w; if (q == t) { //搜索到t,直接返回prev数组,注意逆序 print(prev, s, t); return; } visited[q] = true;//顶点 q 被访问,visited[q]置为 true。 queue.add(q); } } }}//为了正向打印出路径,我们需要递归地来打印private void print(int[] prev, int s, int t) { // 递归打印s->t的路径 if (prev[t] != -1 && t != s) { print(prev, s, prev[t]); } System.out.print(t + " ");}
本文代码代码部分均来极客时间的《数据结构与算法之美》第31课
转载地址:http://cfrsi.baihongyu.com/