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

本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法。分享给大家供大家参考。具体分析如下：

我们用字符串代表图的顶点(vertax)，来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点，然后计算任意两点之间的最短路径。

如下图所示：

如，我想从North Gate去Canteen, 程序的输出结果应为：

BFS: From [North Gate] to [Canteen]:North GateSquareCanteen

首先定义一个算法接口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程序设计有所帮助。