图解BFS(图的广度遍历)，Java实现 |
您所在的位置：网站首页 › bfs代码实现 › 图解BFS(图的广度遍历)，Java实现 |
图解BFS(图的广度遍历)，Java实现
|
哈喽大家好，最近在刷题中经常用到bfs，今天整理一下给大家分享??????? 本篇博客参考于《算法图解》，个人感觉很不错的一本书推荐大家去看看，很适合新手理解！ 前言：《算法图解》的作者在书中说到：在我知道的算法中，图算法应该时最有用的。 确实如此！平常在刷算法题的时候感触很深，很多题目都用到了bfs和dfs，接下来就给大家先带来bfs的解析！ 正题：
这个是我画的一张图，非常简单的一个单向图 根据这个图，在这里提出一个问题：若从S到E，那么最短路径是几？ 若采取广度遍历，其主要思想是从起始点（s）开始，将其邻近的所有顶点都加到一个队列（FIFO）中去，然后标记下这些顶点离起始顶点的距离为1.最后将起始顶点标记为已访问，今后就不会再访问。然后再从队列中取出最先进队的顶点A，也取出其周边邻近节点，加入队列末尾，将这些顶点的距离相对A再加1，最后离开这个顶点A。依次下去，直到队列为空为止。 广度遍历过程可以用下面式子表示： I步: S->A S->B 2步: A->C A->D B->E 我们可以看出来，最快需要两步我们就可以到E了，也就是：S->A->E
广度优先搜索让你能够找出两样东西之间的最短距离，广度优先搜索是一种用于图的查找算法，可帮助回答两类问题。 第一类问题：从节点A出发，有前往节点B的路径吗？ 第二类问题：从节点A出发，前往节点B的哪条路径最短？ 使用这种算法将搜遍整个图，找到到达终点的最短路径。这就是广度优先搜索算法。 结合以上所说的，我们得出一个重要结论： 广度优先搜索不仅查找从A到B的路径，而且找到的是最短的路径。（这个很重要，bfs第一次找到的到达目标的路径就是最短路径！）
在代码实现方面： ①dfs需要用到队列，当一个元素被遍历完时，则与它相连的节点应该被顺序送入队列，然后再从队列中取出队首进行遍历操作。 ②需要一个表，来记录每一个图节点到达图顶点的距离 下面给出代码： import java.awt.font.GraphicAttribute; import java.util.*; public class Bfs { static HashMap graph; static HashMap dist; //bfs private static void bfs(HashMap graph,HashMap dist,char start) { Queue q= new LinkedList(); q.add(start); //将s作为起始顶点加入队列 dist.put(start, 0); //dist表是用来记录每一个图节点到顶点的距离 int i= 0; while(!q.isEmpty()) //队列不为空就一直遍历 { char top=q.poll(); //取出队首元素 i++; System.out.println( "The "+i+ "th element:"+top+ " Distance from S is:"+dist.get(top)); int d=dist.get(top)+ 1; //得出其周边还未被访问的节点的距离，例如：d(S->A)就是0+1=1 for (Character c : graph.get(top)) { if(!dist.containsKey(c)) //如果dist中还没有该元素说明还没有被访问 { dist.put(c, d); //将新访问到的元素与其和顶点相距的距离信息存入 dist q.offer(c); //将新访问到的元素入队 } } } } public static void main(String[] args) { // s顶点的邻接表 LinkedList list_s = new LinkedList(); list_s.add( 'A'); list_s.add( 'B'); LinkedList list_a = new LinkedList(); list_a.add( 'C'); list_a.add( 'D'); LinkedList list_b = new LinkedList(); list_b.add( 'D'); list_b.add( 'E'); LinkedList list_c = new LinkedList(); list_c.add( 'E'); LinkedList list_d = new LinkedList(); list_c.add( 'E'); //构造图 graph = new HashMap(); graph.put( 'S', list_s); graph.put( 'A', list_a); graph.put( 'B', list_b); graph.put( 'C', list_c); graph.put( 'D', list_d); graph.put( 'E', new LinkedList()); //调用 dist = new HashMap(); bfs(graph, dist, 'S'); } }
|
【本文地址】
今日新闻 |
推荐新闻 |