简介 迪杰斯特拉算法(Dijkstra) 是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。 注意，Dijkstra 算法无法处理负权边的情况，比如 0 到 2 点的距离为：-2。 松弛操作（Relaxation） 何为松弛操作，文字描述比较抽象，看图吧。 0 的邻点有 1、2、3，距离分别是 5…

Kruskal Kruskal 是一个简单、易于理解的算法，效率比 Prim 低，对要求不高的场景可以使用。 先把所有边进行排序（从小到大），开始遍历。 从遍历中挨个从小到大取出边，如果这条边被选为了最小生成树，是否会形成环？ 如果会形成环就不能选定这条边。不能形成环，那就可以选定为最小生成树中的一员。 直至循环结束。 循环也可以不必到最后一个索引，只需判断选中边达到 点数 - 1 即可。 以上的关键点在于要判断两点之间的边如果被选中了，是否会形成环？这里可以使用 Union Find 在遍历的过程中把已经相连的点…

简介 什么是最小生成树？假设有 N 个点，通过 N - 1 条边将它们相连接，就叫做生成树，而最小就是这 N - 1 条边的权重相加最小，综合起来就是最小生成树。 下面一张图： 按照最小生成树的规则，最终可以找到这样一条线： 0-7、7-5、5-4、7-1、0-2、2-3、2-6 7 条边把所有的点进行相连，形成了这张图的最小生成树。在这里也能看出来，想要找最小生成树，这个图必须是一个连通图，也就是没有其他的连通分量。 切分定理（Cut Property） 那通过什么样的方式可以求得总共有哪些边可以组成最小生成树？…

邻接矩阵从无权图进行改进 无权图的邻接矩阵 之前使用邻接矩阵实现的稠密图、无权图如下： 在一个 n * n 的二维数组中表示两点相连即为 1(true)，不连则为 0(false)。这在无权图中好使，但是如果是有权图，比如下： 这中间已经不止存在着连接关系了，还有权值，这里的权值如：3.6、3.8、2.9、1.8。这些权值可能表示着距离、时间等等，在复杂点可能不是数字，而是一个对象，所以不能再像无权图那样简单的使用 0、1 表示。 Edge 单独抽象出来一个 边类型，起名 Edge，属性包含了 两个相连接的点、权重…

广度遍历路径规划 简介 增加队列，用来存放待遍历的顶点。 先把起始顶点扔进队列。 从队列中取出第一个顶点，遍历其相邻顶点。 如果已经遍历过 或者 已经是在队列中等待遍历了，跳过。 否则就加入队列，等待遍历。 持续 3，直到没有待遍历的顶点。 广度遍历可以求最短路径。 实现 #include <iostream> #include <vector> #include <stack> #include <queue> /** * 广度遍历求最短路径 * * 时间复杂度： …

深度遍历 简介 遍历一开始，第一个开始遍历的顶点是没有被遍历过的顶点，依次递归遍历当前顶点下第一个相邻顶点，只要是没有被遍历过的顶点，就一直递归下去，如果是已经递归过的顶点就跳过。 深度遍历的特点是可以方便找到一张图的 连通分量。从一顶点开始，一直按照深度遍历的逻辑递归下去，等到递归完毕，如果图中还存在没有被遍历过的顶点，说明存在两个连通分量，若第二个递归完毕还有没有被遍历过的顶点，说明存在三个连通分量，以此类推。 实现 /** * 深度遍历求连通分量 */ template<typename Graph&g…

稠密图 #include <iostream> #include <cassert> #include <vector> /** * 稠密图 - 邻接矩阵 */ class DenseGraph { private: /** * 图中顶点数、边数 */ int n, m; /** * 是否为有向图 */ bool directed; /** * 矩阵，有边就是 true，无边就是 false。 */ std::vector<std::vector<bool>&g…

简介 图是用来对 对象之间 的成对关系建模的数学结构，由 节点 或 顶点(Vertex) 以及连接这些顶点的 边(Edge) 组成。 值得注意的是，图的顶点集合不能为空，但边的集合可以为空，通俗的讲，一张图，没有点不行，没有边可以，大不了点与点之间不相连。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图，无向图也可以看成是一种特殊的有向图。 图的分类： 无权图、有权图 连接顶点与顶点的边是否有数值与之对应，有的话就是有权图，否则就是无权图…

作用 并查集可以快速度的解决连接问题，比如 A 和 B 是否相连。比如下图： 问红色的两个点是否相连，毫无疑问，一眼就看出来，是相连的。 问绿色的两个点是否相连，可能就需要看一会了，才能观察出来是否相连，如果更多，那可能就无法观察出来了，所以就引出了并查集这种数据结构。 同时，他也可以用在人与人关系中，比如社交网络，每个人就相当于一个点。计算机网络，每台计算机点等等。 并查集可以解决两点是否连接的问题，但是无法提供详细的连接路径。相当于只关心两者是否认识，而不关心两者是通过介绍认识或者通过网络认识等等。有失就有得，…

二分查找 基础二分实现查找实现与动画 template<typename T> int binarySearch(T arr[], int len, T target) { int l = 0, r = len - 1; while (l <= r) { // 求中值 int mid = l + ((r - l) >> 1); if (arr[mid] == target) { return mid; } if (arr[mid] > target) { r = mid - 1;…