Java中图路径查找算法的详细解析是怎样的？

本文共计1172个文字，预计阅读时间需要5分钟。

目录+前言+算法详解+实现+API设计+代码实现+前言+在日常生活中，地图是我们经常使用的一种工具，常用来进行导航。输入一个出发城市，输入一个目的地，即可把路线显示出来。

目录

• 前言
• 算法详解
• 实现
• API设计
• 代码实现

前言

在实际生活中，地图是我们经常使用的一种工具，通常我们会用它进行导航，输入一个出发城市，输入一个目的地

城市，就可以把路线规划好，而在规划好的这个路线上，会路过很多中间的城市。这类问题翻译成专业问题就是：

从s顶点到v顶点是否存在一条路径？如果存在，请找出这条路径。

例如在上图上查找顶点0到顶点4的路径用红色标识出来,那么我们可以把该路径表示为 0-2-3-4。

如果对图的前置知识不了解，请查看系列文章：

图的基础概念和数据模型

图的两种搜索算法

算法详解

我们实现路径查找，最基本的操作还是得遍历并搜索图，所以，我们的实现暂且基于深度优先搜索来完成。其搜索

的过程是比较简单的。我们添加了edgeTo[]整型数组，这个整型数组会记录从每个顶点回到起点s的路径。