bfs导航算法java,Java实现利用广度优先遍历(BFS)计算最短路径的方法-程序员宅基地
技术标签： bfs导航算法java
本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法。分享给大家供大家参考。具体分析如下：
我们用字符串代表图的顶点(vertax)，来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点，然后计算任意两点之间的最短路径。
如下图所示：
如，我想从North Gate去Canteen, 程序的输出结果应为：
?
首先定义一个算法接口Algorithm:
?
然后，定义图:
?
这里我们使用策略设计模式，将算法与Graph类分离，通过在构造Graph对象时传入一个Algorithm接口的实现来为Graph选择遍历算法。
?
无向图的存储结构为邻接表，这里用一个Map表示邻接表，map的key是学校地点(String)，value是一个与该地点相连通的地点表(List)。
?
然后，编写Algorithm接口的BFS实现：
?
其中，path是Map类型，意为从 value 到 key 的一条路径。
BFS算法描述：
1. 将起点标记为已访问并放入队列。
2. 从队列中取出一个顶点，得到与该顶点相通的所有顶点。
3. 遍历这些顶点，先判断顶点是否已被访问过，如果否，标记该点为已访问，记录当前路径，并将当前顶点入列。
4. 重复2、3，直到队列为空。
测试用例：
?
希望本文所述对大家的java程序设计有所帮助。
智能推荐
如何下载Chrome离线安装包 MSI系统级安装包_chrome离线版msi-程序员宅基地
文章浏览阅读1w次。http://blog.163.com/yangji008@126/blog/static/70036935201010200270623/_chrome离线版msi
在Outlook 2013中发送给多个收件人时如何隐藏电子邮件地址-程序员宅基地
文章浏览阅读5.5k次。When you send email to multiple recipients (some of whom may be unknown to each other), it’s betternot to display everyone’s email address. Here’s how to get that donein Outlook. 将电子邮件发送给多个收件人(其中一些..._如何隐藏多个收件人的电邮地址信息
Mobile Edge Computing学习笔记（一）从通信领域看移动边缘计算：现有的经典结构与模型_binary offloading-程序员宅基地
文章浏览阅读5.7k次，点赞19次，收藏74次。MEC最近越来越火了，inforcom，mobicom各种顶会每年都有大量产出。看了一篇 IEEE COMMUNICATIONS SURVEYS & TUTORIALS的综述：A Survey on Mobile Edge Computing: The Communication Perspective，记录一下收获。文章目录一、前言二、简介1：5G技术包含的移动计算2：移动边缘计算与移..._binary offloading
洛谷题解 P1713 【麦当劳叔叔的难题】_洛谷p1713-程序员宅基地
文章浏览阅读532次。这是一道很好的搜索题。既然是最大时间与最小时间的差，所以可以先用BFS求出最少时间；再用DFS求出最大时间（但注意要剪枝，不然会超时）。话不多说，进入正题。既然可以有四个方向可以走，那么我们可以定义两个方向增量数组，一个记录X，一个记录Y。像这样：int dx[5]={1,-1,0,0}, dy[5]={0,0,1,-1};BFS：定义一个队列，分别存X，Y和最小步数。DFS：用两个量，一个记录行，一个记录列。更多解释详见代码中的注释。#include <cstdio>#_洛谷p1713
.net的TreeView控件绑定数据库表建立树架构_vb.net treeview 与表关联-程序员宅基地
文章浏览阅读2.5k次。net本身自带的TreeView控件本身可以提供简单快捷的树结构控件，不过需要是在前台界面手动输入静态数据，只能预先设定好值，一一录入。这次使用到的方法是通过在后台代码绑定数据库表，实现动态的数据树显示。 首先先在.net前台界面注册一个TreeView控件，并且将其放置在asp:UpdatePanel标签内，以方便以后实行异步刷新功能。如图 数据库中会设置两张表，一张为根_vb.net treeview 与表关联
EMC防护--端口浪涌和防雷设计_网口浪涌防护电路-程序员宅基地
文章浏览阅读6.8k次，点赞3次，收藏41次。在工作中，产品设计经常要考虑EMC设计，特别是端口防护，主要包括信号口、天馈口和电源口。其中信号口又分普通网口、POE网口、RS232/RS485、GPS数据网口。此类问题在大部分产品中均会遇到。本文内容是根据本人多年从业经验和同事们的经验撰写的，主要以通信类产品为例，介绍端口浪涌防护、防雷等方面的电路设计，希望能对读者有较大的帮助。更多应用实例可以下载本人的学习资源--端口EMC防护电路设计1、端口防护电路种类信号口的防护要求多为过电压防护要求，即浪涌防护；天馈口及电源口的防护要求多为过电流防_网口浪涌防护电路
随便推点
vue强制更新数据$forceUpdate()和this.$set()-程序员宅基地
文章浏览阅读1.8w次，点赞13次，收藏57次。方法一、添加this.$forceUpdate();进行强制渲染，效果实现可以实现。从搜索资料得出结果：因为数据层次（for循环太多）太多，render函数没有自动更新，需手动强制刷新。调用强制更新方法this.$forceUpdate()会更新视图和数据，触发updated生命周期。我是在使用多层for循环嵌套时出现的页面没有及时刷新改变后的值的问题( 使用this.$forceUpdate() )使用方法:input( ) { // vue2的引_$forceupdate()
vue + elemetui — upload解决跨域、实现图片上传_vue 图片跨域-程序员宅基地
文章浏览阅读7.9k次，点赞3次，收藏16次。 最近做Vue项目，需要用到图片上传的功能，因为是PC端后台项目，故而采用了element-ui组件库里的upload上传的组件。本文主要解决上传时的跨域问题。 action属性便是上传的地址，需要进行跨域。话..._vue 图片跨域
kubernetes 【组件】ingress controller 如何通过域名访问您的应用_ingress 域名-程序员宅基地
文章浏览阅读5.7k次，点赞2次，收藏8次。文章目录1. 简介2. 安装3. 测试1. 简介Ingress 是 Kubernetes 的一种 API 对象，将集群内部的 Service 通过 HTTP/HTTPS 方式暴露到集群外部，并通过规则定义 HTTP/HTTPS 的路由。Ingress 具备如下特性：集群外部可访问的 URL、负载均衡、SSL Termination、按域名路由（name-based virtual hosting）。增加了7层的识别能力，可以根据 http header, path 等进行路由转发。2. 安装安装指_ingress 域名
Android开发之完整的个人练手项目的开放API接口_android 开源api接口-程序员宅基地
文章浏览阅读2.1k次，点赞2次，收藏13次。项目地址：https://www.wanandroid.com1.首页相关1.1 首页文章列表https://www.wanandroid.com/article/list/0/json方法：GET参数：页码，拼接在连接中，从0开始。很多 H5 页面会恶意跳转淘宝等，可以在 webview 的 shouldOverrideUrlLoading 中做一下拦截，非常影响用户体验。可直接点击查看示例：https://www.wanandroid.com/article/l._android 开源api接口
highcharts坐标轴实现字符串换行_highchartsx轴文本换行-程序员宅基地
文章浏览阅读2.6k次。Title $(function(){ debugger; Highcharts.setOptions({ lang:{ loading:"数据载入中......" } }); $('#container').high_highchartsx轴文本换行
搭建数据平台_如何搭建一个数据接口查询平台-程序员宅基地
文章浏览阅读1.5k次。数据平台分层结构DataPlatform-user —-DataPlatform-user-repository 数据存储，提供存储数据的能力 —-DataPlatform-user-repository-interface 数据存储接口，对内、外提供接口 —-DataPlatform-user-model 数据模型 —-DataPlatform-user-dao 数据持久_如何搭建一个数据接口查询平台