Java实现利用广度优先遍历(BFS)计算最短路径的方法
程序员文章站
2024-03-02 22:08:16
本文实例讲述了java实现利用广度优先遍历(bfs)计算最短路径的方法。分享给大家供大家参考。具体分析如下:
我们用字符串代表图的顶点(vertax),来模拟学校中cla...
本文实例讲述了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. 将起点标记为已访问并放入队列。
2. 从队列中取出一个顶点,得到与该顶点相通的所有顶点。
3. 遍历这些顶点,先判断顶点是否已被访问过,如果否,标记该点为已访问,记录当前路径,并将当前顶点入列。
4. 重复2、3,直到队列为空。
测试用例:
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", "toilet"), new edge("square", "canteen"), new edge("toilet", "south gate"), 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程序设计有所帮助。