Java中图搜索算法：深度优先与广度优先搜索方法详解？

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

目录+前言+深度优先搜索算法+API设计+代码实现+广度优先搜索算法+API设计+代码实现+案例应用+前言+在许多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定顶点相邻的所有顶点。

目录

• 前言
• 深度优先搜索算法
• API设计
• 代码实现
• 广度优先搜素算法
• API设计
• 代码实现
• 案例应用

前言

在很多情况下，我们需要遍历图，得到图的一些性质，例如，找出图中与指定的顶点相连的所有顶点，或者判定某个顶点与指定顶点是否相通，是非常常见的需求。

有关图的搜索，最经典的算法有深度优先搜索和广度优先搜索，接下来我们分别讲解这两种搜索算法。

学习本文前请先阅读这篇文章 图的基础概念和数据模型。

深度优先搜索算法

所谓的深度优先搜索，指的是在搜索时，如果遇到一个结点既有子结点，又有兄弟结点，那么先找子结点，然后找兄弟结点。

如上图所示：

由于边是没有方向的，所以，如果4和5顶点相连，那么4会出现在5的相邻链表中，5也会出现在4的相邻链表中。