MoCuishle

之前，我们介绍了单源最短路径问题：Dijkstra算法——解决正权边图上的单源最短路径；Bellman-Ford算法——解决图上带负权边的单源最短路径问题。而今天，我们将主要介绍一种解决图上多元最短路径的算法——Floyd算法。

在前一篇文章中，主要介绍了如何利用Dijkstra算法解决正权图上的单源最短路径问题。然而，在现实生活中的许多图模型中，其权值并不一定全部为正。因此，本文将讨论带负权图上的单源最短路径问题。

最短路径问题始终是图算法中一类重要的研究问题，目前也有众多工作提出了一些高效的解决策略。然而，就单源最短路径问题而言，Dijkstra算法和Bellman-Ford算法历经多年仍然是最经典的算法。本文将重点介绍Dijkstra算法。

最小生成树问题是图算法问题中一类经典的问题，其在大量其他的图算法问题中也有广泛的应用。最小生成树问题，其核心是“贪心策略”在图算法中的应用，并由此产生了两类经典的最小生成树算法：Prim算法&Kruskal算法。

本文主要介绍两类最基本的图搜索策略——BFS与DFS。BFS与DFS是一种最基础的，但也是最重要的图算法，其被大量应用在图算法的各个领域，众多高级的图算法，其核心其实仍是这两种最基础的图搜索算法。
本文主要依据北京航空航天大学童咏昕教授《算法设计与分析》课程内容，并结合本人对于图数据的研究课题内容，对图搜索上的两类基础算法进行总结。
P.s：本文主要关注无向图上的BFS与DFS算法，关于有向图的搜索算法会在后续进行讨论。

本文主要介绍图搜索算法（DFS & BFS）的应用实例，其包括：拓扑排序、环路检验和强连通分量计算。
P.s：考虑到强连通分量算法是一个较为难以理解的算法，故将强连通分量问题放在下章单独介绍。

本文主要介绍图搜索算法（DFS & BFS）的应用实例，其包括：拓扑排序、环路检验和强连通分量计算。
本章主要介绍强连通分量计算问题～

本文从“柯尼斯堡七桥问题”作为引入，介绍“图”这一重要数据类型上的相关的一些定义、定理。
<本文涉及的概念均采用目前公认的定义、及描述方法>