参数说明 环境变量 描述 值示例 http_proxy 为 http 变量设置代理;默认不填开头以http协议传输。 192.168.22.2:1080br>user:password@192.168.22.2:1080
参数说明 环境变量 描述 值示例 http_proxy 为 http 变量设置代理;默认不填开头以http协议传输。 192.168.22.2:1080br>user:password@192.168.22.2:1080
简介 迪杰斯特拉算法(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 是否相连。比如下图: 问红色的两个点是否相连,毫无疑问,一眼就看出来,是相连的。 问绿色的两个点是否相连,可能就需要看一会了,才能观察出来是否相连,如果更多,那可能就无法观察出来了,所以就引出了并查集这种数据结构。 同时,他也可以用在人与人关系中,比如社交网络,每个人就相当于一个点。计算机网络,每台计算机点等等。 并查集可以解决两点是否连接的问题,但是无法提供详细的连接路径。相当于只关心两者是否认识,而不关心两者是通过介绍认识或者通过网络认识等等。有失就有得,…