Java利用广度优先遍历(BFS)计算最短路径 Java实现利用广度优先遍历(BFS)计算最短路径的方法
司青 人气:0想了解Java实现利用广度优先遍历(BFS)计算最短路径的方法的相关内容吗，司青在本文为您仔细讲解Java利用广度优先遍历(BFS)计算最短路径的相关知识和一些Code实例，欢迎阅读和指正，我们先划重点：Java,广度优先遍历,最短路径，下面大家一起来学习吧。
本文实例讲述了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程序设计有所帮助。
加载全部内容