Java实现利用广度优先遍历(BFS)计算最短路径的方法

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 getPath();

}

然后，定义图:

/**

* (无向)图

*/

public class Graph {

// 图的起点

private String firstVertax;

// 邻接表

privatWTqxtZpHBe Map> 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 findPathTo(String vertex) {

Stack stack = new Stack<>();

stack.add(vertex);

Map 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 = http://fromVertex;

}

adj.get(fromVertex).add(toVertex);

adj.get(toVertex).add(fromVertex);

}

/**

* 添加一个顶点

*/

public void addVertex(String vertex) {

adj.put(vertex, new ArrayList<>());

}

public Map> getAdj() {

return adj;

}

}

这里我们使用策略设计模式，将算法与Graph类分离，通过在构造Graph对象时传入一个Algorithm接口的实现来为Graph选择遍历算法。

public Graph(Algorithm algorithm) {

this.algorithm = algorithm;

}

无向图的存储结构为邻接表，这里用一个Map表示邻接表，map的key是学校地点(String)，value是一个与该地点相连通的地点表(List)。

// 邻接表

private Map adj = new HashMap<>();

然后，编写Ahttp://lgorithm接口的BFS实现：

/**

* 封装BFS算法

*/

public class BroadFristSearchAlgorithm implements Algorithm {

// 保存已经访问过的地点

private List visitedVertex;

// 保存最短路径

private Map 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 getPath() {

return path;

}

private void BFS(Graph g, String sourceVertex) {

Queue queue = new LinkedList<>();

// 标记起点

visitedVertex.add(sourceVertex);

// 起点入列

queue.add(sourceVertex);

while (false == queue.isEmpty()) {

String ver = queue.poll();

List 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. 遍历这些顶点，先判断顶点是否已被访问过，如果否，标记该点为已访问，记录当前路径，并将WTqxtZpHB当前顶点入列。

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 result = g.findPathTo("Canteen");

System.out.println("BFS: From [North Gate] to [Canteen]:");

while (!result.isEmpty()) {

System.out.println(result.pop());

}

}

希望本文所述对大家的java程序设计有所帮助。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。