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<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程序设计有所帮助。

(0)

相关推荐

  • Java实现Dijkstra输出最短路径的实例

    Java实现Dijkstra输出指定起点到终点的最短路径 前言: 最近在公司参加了一个比赛,其中涉及的一个问题,可以简化成如是描述:一个二维矩阵,每个点都有权重,需要找出从指定起点到终点的最短路径. 马上就想到了Dijkstra算法,所以又重新温故了一遍,这里给出Java的实现. 而输出最短路径的时候,在网上也进行了查阅,没发现什么标准的方法,于是在下面的实现中,我给出了一种能够想到的比较精简的方式:利用prev[]数组进行递归输出. package graph.dijsktra; import

  • java实现最短路径算法之Dijkstra算法

    前言 Dijkstra算法是最短路径算法中为人熟知的一种,是单起点全路径算法.该算法被称为是"贪心算法"的成功典范.本文接下来将尝试以最通俗的语言来介绍这个伟大的算法,并赋予java实现代码. 一.知识准备: 1.表示图的数据结构 用于存储图的数据结构有多种,本算法中笔者使用的是邻接矩阵. 图的邻接矩阵存储方式是用两个数组来表示图.一个一维数组存储图中顶点信息,一个二维数组(邻接矩阵)存储图中的边或弧的信息. 设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为: 从上面可以看出,无

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

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • java中利用反射调用另一类的private方法的简单实例

    我们知道,Java应用程序不能访问持久化类的private方法,但Hibernate没有这个限制,它能够访问各种级别的方法,如private, default, protected, public. Hibernate是如何实现该功能的呢?答案是利用JAVA的反射机制,如下: import java.lang.reflect.InvocationTargetException; import java.lang.reflect.Method; public class ReflectDemo {

  • Java HashMap 如何正确遍历并删除元素的方法小结

    (一)HashMap的遍历 HashMap的遍历主要有两种方式: 第一种采用的是foreach模式,适用于不需要修改HashMap内元素的遍历,只需要获取元素的键/值的情况. HashMap<K, V> myHashMap; for (Map.entry<K, V> item : myHashMap.entrySet()){ K key = item.getKey(); V val = item.getValue(); //todo with key and val //WARNI

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • Java实现广度优先遍历的示例详解

    目录 什么是广度优先 一个简单的例子 程序实现 总结 什么是广度优先 广度就是扩展开,广度优先的意思就是尽量扩展开.所以在算法实现的时候,就是一个循环遍历枚举每一个邻接点.其基本思路就是按层扩展,扩得越广越好. 伪代码如下: for(int i = 0; i < children.size(); i++){ children.get(i); // 调用每一个子节点 } 一个简单的例子 我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫. 1 1 0 1 1 1 1 1

  • Java利用Dijkstra算法求解拓扑关系最短路径

    目录 算法简介 代码实现思路 算法思想 代码示例 算法简介 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学迪家迪杰斯特拉于1959年提出的,因此又叫狄克斯特拉算法.是从一个顶点到其余各顶点最短路劲算法,解决的是有权图中最短路径问题.迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止. 代码实现思路 1.先初始化源节点(起始点)到其他各个拓扑节点的最短距离,可以用map存放,key为节点,value为节点到源节点的距

  • Java分别利用深度优先和广度优先求解迷宫路径

    目录 深度优先 实现效果 示例代码 广度优先 实现效果 示例代码 知识点总结 深度优先 实现效果 示例代码 import java.awt.*; import javax.swing.*; public class AlgoFrame extends JFrame{ private int canvasWidth; private int canvasHeight; public AlgoFrame(String title, int canvasWidth, int canvasHeight)

  • Java list利用遍历进行删除操作3种方法解析

    这篇文章主要介绍了Java list利用遍历进行删除操作3种方法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 Java三种遍历如何进行list的便利删除: 1.for循环: 常见初五写法:(由于下标问题达不到想要效果) for(int i=0;i<list.size();i++){ if(list.get(i).equals("del")) list.remove(i); } 应该改为:(倒序操作避免下标问题) int s

  • Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】

    本文实例讲述了Java二叉搜索树遍历操作.分享给大家供大家参考,具体如下: 前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树. 对于二叉树,有深度遍历和广度遍历,深度遍历有前序.中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图: 因为树的定义本身就是递归定义,所以对于前序.中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历.

随机推荐

其他