算法与数据结构无废话笔记（三）

  算法与数据结构是计算机专业学生的必修课，基础中的基础，所以快速上手，找到学习方向和感觉十分重要。我在学习过程中遇到一本好书，《我的第一本算法书》，把算法讲得很浅显易懂，所以基于这本书的内容，提炼出其中的精华，再加上个人的理解，旨在把最干的干货分享给大家。推荐大家去阅读原书！

图的搜索

图能给我们带来的便利

想一想图能给我们带来的好处吧。假设图中有两个顶点 s 和 t，而我们设计出了一种算法，可以找到“从 s 到 t 的权重之和最小”的那条路径。那么，这种算法就可以应用到这些问题上：寻找计算机网络中通信时间最短的路径，寻找路线图中耗时最短的路径，寻找路线图中最省乘车费的路径等 A。

就像这样，只要能用图来表示这些关系，我们就可以用解决图问题的算法来解决这些看似不一样的问题。

图的搜索指的就是从图的某一顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。

广度优先搜索

假设我们一开始位于某个顶点（即起点），此时并不知道图的整体结构，而我们的目的是从起点开始顺着边搜索，直到到达指定顶点（即终点）。在此过程中每走到一个顶点，就会判断一次它是否为终点。广度优先搜索会优先从离起点近的顶点开始搜索。

深度优先搜索

目的和广度优先搜索一样都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

就是一根筋，每条路都走到底。

最短路径算法

贝尔曼-福特算法

贝尔曼 - 福特（Bellman-Ford）算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重总和最小的那条路径。

这个算法很暴力！每一轮更新都比较每一条边！在一次更新中，如果一条边计算的权重小于顶点的权重，则顶点的权重更新！每次更新需要记录计算的是从哪个顶点到该顶点的路径。

重复对所有边的更新操作，直到权重不能被更新为止。

所以每一轮更新都要比较所有的n条边，理论至多n-1轮更新后找到最小路径。

一开始一般选从起点开始，假设其他顶点初始权重都是无穷大。

第一轮更新：

第二轮：重复对所有边的更新操作，直到权重不能被更新为止。

狄克斯特拉算法

狄克斯特拉（Dijkstra）算法也是求解最短路径问题的算法。走一步，算一步！一边逐一确定起点到各个顶点的最短路径，一边对图进行搜索。

从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径整个寻找过程一气呵成，不用多轮的更新！ 本质，不断选择顶点！

A* 算法

狄克斯特拉算法会把所有顶点的最短路径都算出来，但其实一些离终点较远的顶点的最短路径是无用的！ A* 算法会预先估算一个值（各顶点与终点的距离），并利用这个值来省去一些无用的计算。

上一篇 ！下一篇 ！加油！