Java实现利用广度优先遍历(BFS)计算最短路径的方法
本篇章节讲解Java实现利用广度优先遍历(BFS)计算最短路径的方法。分享给大家供大家参考。具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom,Square,Toilet,Canteen,South Gate,North Gate几个地点,然后计算任意两点之间的最短路径。 如下图所示: 如,我想从North Gate去Canteen,程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Gate Square Canteen 首先定义一个算法接口Algorithm: public interface Algorithm { /** * 执行算法 */ void perform(Graph g,String sourceVertex); /** * 得到路径 */ Map<String,String> getPath(); } 然后,定义图: /** * (无向)图 */ public class Graph { // 图的起点 private String firstVertax; // 邻接表 private Map<String,List<String>> adj = new HashMap<>(); // 遍历算法 private Algorithm algorithm; public Graph(Algorithm algorithm) { this.algorithm = algorithm; } /** * 执行算法 */ public void done() { algorithm.perform(this,firstVertax); } /** * 得到从起点到{@code vertex}点的最短路径 * @param vertex * @return */ public Stack<String> findPathTo(String vertex) { Stack<String> stack = new Stack<>(); stack.add(vertex); Map<String,String> path = algorithm.getPath(); for (String location = path.get(vertex) ; false == location.equals(firstVertax) ; location = path.get(location)) { stack.push(location); } stack.push(firstVertax); return stack; } /** * 添加一条边 */ public void addEdge(String fromVertex,String toVertex) { if (firstVertax == null) { firstVertax = fromVertex; } adj.get(fromVertex).add(toVertex); adj.get(toVertex).add(fromVertex); } /** * 添加一个顶点 */ public void addVertex(String vertex) { adj.put(vertex,new ArrayList<>()); } public Map<String,List<String>> getAdj() { return adj; } } 这里我们使用策略设计模式,将算法与Graph类分离,通过在构造Graph对象时传入一个Algorithm接口的实现来为Graph选择遍历算法。 public Graph(Algorithm algorithm) { this.algorithm = algorithm; } 无向图的存储结构为邻接表,这里用一个Map表示邻接表,map的key是学校地点(String),value是一个与该地点相连通的地点表(List<String>)。 // 邻接表 private Map<String,List<String>> adj = new HashMap<>(); 然后,编写Algorithm接口的BFS实现: /** * 封装BFS算法 */ public class BroadFristSearchAlgorithm implements Algorithm { // 保存已经访问过的地点 private List<String> visitedVertex; // 保存最短路径 private Map<String,String> path; @Override public void perform(Graph g,String sourceVertex) { if (null == visitedVertex) { visitedVertex = new ArrayList<>(); } if (null == path) { path = new HashMap<>(); } BFS(g,sourceVertex); } @Override public Map<String,String> getPath() { return path; } private void BFS(Graph g,String sourceVertex) { Queue<String> queue = new LinkedList<>(); // 标记起点 visitedVertex.add(sourceVertex); // 起点入列 queue.add(sourceVertex); while (false == queue.isEmpty()) { String ver = queue.poll(); List<String> toBeVisitedVertex = g.getAdj().get(ver); for (String v : toBeVisitedVertex) { if (false == visitedVertex.contains(v)) { visitedVertex.add(v); path.put(v,ver); queue.add(v); } } } } } 其中,path是Map类型,意为从 value 到 key 的一条路径。 BFS算法描述: 1. 将起点标记为已访问并放入队列。 测试用例: String[] vertex = {"North Gate","South Gate","Classroom","Square","Toilet","Canteen"}; Edge[] edges = { new Edge("North Gate","Classroom"),new Edge("North Gate","Square"),new Edge("Classroom","Toilet"),new Edge("Square","Canteen"),new Edge("Toilet","South Gate"),}; @Test public void testBFS() { Graph g = new Graph(new BroadFristSearchAlgorithm()); addVertex(g); addEdge(g); g.done(); Stack<String> result = g.findPathTo("Canteen"); System.out.println("BFS: From [North Gate] to [Canteen]:"); while (!result.isEmpty()) { System.out.println(result.pop()); } } 希望本文所述对大家的java程序设计有所帮助。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |