服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|

服务器之家 - 编程语言 - JAVA教程 - Java实现利用广度优先遍历(BFS)计算最短路径的方法

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

2019-12-16 13:33司青 JAVA教程

这篇文章主要介绍了Java实现利用广度优先遍历(BFS)计算最短路径的方法,实例分析了广度优先遍历算法的原理与使用技巧,具有一定参考借鉴价值,需要的朋友可以参考下

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

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

如下图所示:

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

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

?
1
2
3
4
BFS: From [North Gate] to [Canteen]:
North Gate
Square
Canteen

首先定义一个算法接口Algorithm:

?
1
2
3
4
5
6
7
8
9
10
public interface Algorithm {
  /**
   * 执行算法
   */
  void perform(Graph g, String sourceVertex);
  /**
   * 得到路径
   */
  Map<String, String> getPath();
}

然后,定义图:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
 * (无向)图
 */
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选择遍历算法。

?
1
2
3
public Graph(Algorithm algorithm) {
    this.algorithm = algorithm;
  }

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

?
1
2
// 邻接表
  private Map<String, List<String>> adj = new HashMap<>();

然后,编写Algorithm接口的BFS实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 封装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,直到队列为空。

测试用例:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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程序设计有所帮助。

延伸 · 阅读

精彩推荐