【算法小知识】|图及图搜索

何谓图？

定义：由顶点和链接每对顶点的边所构成的图形就是图。

图的分类

• 加权图：边上有权重值的图
• 有向图：边上具有箭头，可指向由一个顶点到另一个顶点，也可加上权重
• 无向图：边上没有箭头，不可指向的图

图的作用

1. 计算从一顶点到另一顶点的权重最小路径，即路线最短路径
2. 例如计算通信网络中，通信时间最小的路径
3. 路线图中耗时最短的路径
4. 路线图中最省车费的路径等等

图的搜索算法

图的搜索算法
广度优先搜索
深度优先搜索
贝尔曼-福特算法
狄克斯特拉算法
A*算法
…

---

广度优先搜索

广度优先是一种对图搜索的一种规则。假设从某一个顶点开始，此时并不知道图的整体结构，目的是从起点开始顺着边搜索，直至到达指定顶点，。在此过程中，没走一个顶点，都会判断一次它是否为终点。广度优先原则会优先从离起点近的顶点开始搜索。

搜索规则

• 任选一个顶点
• 将与该顶点直接相连的顶点作为候补顶点
• 从候补顶点中选择一个，优先选择最早称为候补的，若存在多个候补顶点，可以任选一个。
• 选择后，进行判断，若不是，继续添加候补顶点，重复以上步骤
• 直至所有顶点被检测完
  解释：广度优先是从近到远开始，由近到远进行广泛搜索。因此目标顶点离顶点越近，搜索速度越快

---

深度优先搜索

深度优先是图搜索的另一种规则。深度优先搜索会沿着一条路径不断往下搜索，直到不能再继续为止，然后再折返，开始另一条候补路径。

搜索路径

• 选择一个顶点，即最根部的顶点
• 添加候补顶点
• 从候补顶点中选择一个顶点，若存在多个可以任选，优先选择最新称为候补顶点的顶点
• 搜索该选择的候补顶点，重复第二步之后步骤
• 直至搜索完毕所有顶点

---

贝尔曼-福特算法

该算法是一种在图中求解最短路径问题的算法。
最短路径问题，是在加权图中指定了起点和终点的前提下，寻找从起点到终点的权重和最小的路径。

规则

• 最初不知道要走多远才能到达其他顶点因此，将起点以外的其他顶点的权重设置为无穷大。
• 首先设置起点的权重为0，其他顶点为无穷大；（该权重为从顶点到该顶点的最短路径的暂定距离）
• 从选择的该点连线中任选一条边，计算该点到边另一点的权重，计算方法为顶点原本的权重+边权重 ，默认按照顶点权重从小到达的方向开始计算，若计算权重小于另一点权重则替换，否则不变。接下来计算权重从大到小的方向，若计算出权重小于该点权重则替换，否则不变。
• 对所有的边执行同样的 *** 作，执行顺序上面没有要求，
• 对所有的边进行更新 *** 作，直到权重不能被更新为止。
  时间复杂度:图定点数为n，边数为m，复杂度为O（nm）
  计算最短路径时，一般都为时间，距离或者路费等等，非负数。即使是负数该算法也能够进行使用。
  若该图像进行n次重复更新后仍然能够进行更新，则认为该图像不存在最短的路径。

---

狄克斯特拉算法

作用与上述算法类似，同样为求解最短路径问题的算法，该算法可求出从起点到终点的路径中权重总和最小的路径。

规则

• 设起点顶点的权重为0，其他顶点的权重为无穷大
• 添加候选顶点，计算候选顶点的权重
• 若候选顶点的权重相等，任选一个顶点，否则选择权重最小的顶点。
• 重复第二步的添加候选顶点，重复计算权重，若计算权重小，则替换原始顶点权重，否则不变，重复。
• 直至找到路径最短的路径。
  若存在负数，则改算法可能得不出正确答案

---

A*算法

该算法也是一种求解最短路径的算法，由狄克斯特拉算法发展而来。