欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-02 22:08:16
本文实例讲述了java实现利用广度优先遍历(bfs)计算最短路径的方法。分享给大家供大家参考。具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中cla...

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

我们用字符串代表图的顶点(vertax),来模拟学校中classroom, square, toilet, canteen, south gate, north gate几个地点,然后计算任意两点之间的最短路径。

如下图所示:

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

如,我想从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程序设计有所帮助。