离散数学中的图
由节点和连接节点的边构成的图形就是图。
我们还可以再给每条边加上一个值，这个值叫做边的权重或者权。
加了权的图被称为加权图，没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的“连接程度”。
而当我们想在路线图中表示该路线只能单向行驶的时候，就给边加上箭头，而这样的图就叫做“有向图”。
图的搜索指的就是从图的某一个顶点开始，通过边到达不同的顶点，最终找到目标顶点的过程。根据搜索的顺序的不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”。
Tips：没有闭环的图就是树。
广度优先搜索 BFS
广度优先搜索的特征是从起点开始，由近及远的进行广泛的搜索。因此，目标顶点离起点越近，搜索结束的就越快。
深度优先搜索 DFS
深度优先搜索的特征为沿着一条路径不断向下，进行深度搜索。虽然DFS和BFS在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，就是选择哪一个候补顶点作为下一个顶点的基准不同。
BFS选择的是最早成为候补的顶点，因为顶点离起点越近就越早进入候补，所以会从离起点越近的地方开始搜索；而DFS选择的是最新成为候补的顶点，所以会一路向下，沿着新发现的路径不断深入搜索。
贝尔曼 - 福特算法
贝尔曼 - 福特算法是一种在图中求解最短路径问题的算法。最短路径问题就是在加权图指定了起点和终点的前提下，寻找从起点到终点的路径中权重和最小的那条路径。
具体做法是，首先设置各个顶点的初识权重：起点为0，其他顶点为无穷大，这个权重表示的是从最开始的顶点到该顶点的最短路径的暂定距离。随着计算往下进行，这个值会变的越来越小，最终收敛到正确的数值。
从所有的边中选出一条边，分别计算这条边从一端到另一端的权重，计算方法是“顶点原本的权重+边的权重”。对所有的边都执行同样的操作，虽然在执行顺序上没有特定要求，但是先计算执行过的边相邻的边会减少很多操作。更新完一轮以后，重复对所有边的更新操作，直到权重不能被更新为止。
将图的顶点数设为n，边数设为m，该算法经过n轮更新操作以后就会停止，每次更新m次，所以整体时间复杂度为O(mn)。
Tips：如果在一个闭环中边的权重总和是负数，那么只要不断遍历这个闭环，那么路径的权重就能不断减小，也就是说根本不存在最短路径，遇到这种进行了n次更新操作还可以继续更新的情况，就可以认定它“不存在最短路径”。
狄克斯特拉算法
和贝尔曼 - 福特算法一样，狄克斯特拉算法也是在图中求解最短路径问题的算法。
具体做法是，从顶点出发，寻找可以从目前所在的顶点直达且尚未被搜索过的顶点，将它们设为下一步的候补顶点。计算各个候补顶点的权重，如果计算结果小于候补顶点的值，就更新这个值。然后从候补顶点中选出权重最小的顶点，将可以从新的顶点直达的顶点设为新的候补顶点，用同样的方法计算各个候补顶点的权重。重复操作直到到达终点为止。
比起贝尔曼 - 福特算法，狄克斯特拉算法多了一步选择顶点的操作，使得它在寻求最短路径上更加高效。
将图的顶点数设为n，边数设为m，如果事先不进行任何处理，该算法的时间复杂度为O(nn)，不过，如果对数据结构进行优化的话，那么时间复杂度就会变为O(m+nlogn)。
Tips：如果图中含有负数权重，那么狄克斯特拉算法会解出一条错误路径。如果闭环中存在负数权重，也就是说贝尔曼 - 福特算法可以认定不存在最短路径，狄克斯特拉算法则会解出错误路径。 所以，在不存在负数权重的时候，更适合使用效率更高的狄克斯特拉算法，而存在负数权重的时候，即便较为耗时，也应该使用可以得到正确答案的贝尔曼 - 福特算法。
A* 算法
A* 算法由狄克斯特拉算法发展而来。狄克斯特拉算法会从离起点近的顶点开始，按顺序求出起点到各个顶点的最短路径。也就是说，一些离终点较远的顶点的最短路径也会被计算出来，但是这些部分是无用的。A*算法会预先估算一个值，并利用这个值来省去一些无用的计算。
具体做法是，从顶点开始，分别计算周围每个顶点的权重，计算方法是“从顶点到该顶点的距离”加上“距离估算值”。
Tips：由人工预先设定的估算距离被称为“距离估算值”。如果事先根据已知信息设定合适的距离估算值，再将它作为启发信息辅助计算，搜索就会变得更加高效。因此，这样的算法也被称为启发式算法。
如果我们能得到一些启发信息，即各个顶点到终点的大致距离，我们就能使用A* 算法。这个大致距离越接近当前顶点到终点的实际值，A* 算法的效率就越高，反之则有可能比狄克斯特拉算法效率低，如果远大于实际距离，甚至无法得到正确答案。当然，当距离估算值小于实际距离的时候，是一定可以得到正确答案的。