个人中心
gpt4 book ai didi

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

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章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程序设计有所帮助.

最后此篇关于Java实现利用广度优先遍历(BFS)计算最短路径的方法的文章就讲到这里了,如果你想了解更多关于Java实现利用广度优先遍历(BFS)计算最短路径的方法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： JAVA时间日期处理类实例
文章推荐： java区分绝对路径和相对路径的方法
文章推荐： JavaMail实现邮件发送的方法
文章推荐： Java网络编程之简单的服务端客户端应用实例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com