自学教程广度优先遍历与最短路径
广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结...
数据结构
寻路算法
图的寻路算法也可以通过深度优先遍历 dfs 实现，寻找图 graph 从起始 s 点到其他点的路径，在上一小节的实现类中添加全局变量 from数组记录路径，from[i] 表示查找的路径上i的上一个节点。 首先构造函数初始化寻路算法的初始条...
深度优先遍历与连通分量
深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。 下图示例的图从...
相邻节点迭代器
图论中最常见的操作就是遍历邻边，通过一个顶点遍历相关的邻边。邻接矩阵的遍历邻边的时间复杂度为 O(V)，邻接表可以直接找到，效率更高。 邻接矩阵迭代: 邻接表迭代： 对于这两种图的表达方式我们可以抽象出一个接口，生成这一套算法的框架，而不用...
图论基础和表示
一、概念及其介绍 图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。 图是用来对对象之间的成对关系建模的数学结构，由"节点"或"顶点"(Vertex）以及连接这些顶点的"边"（Edge）组成。 值得注意...
并查集路径压缩
并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个...
并查集 rank 的优化
上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。 根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操完后，层数变为4，比之前增多了一层，如下图所示：...
并查集 size 的优化
按照上一小节的思路，我们把如下图所示的并查集，进行 union(4,9) 操作。 合并操作后的结构为： 可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进...
并查集快速合并
对于一组数据，并查集主要支持两个动作： union(p,q) - 将 p 和 q 两个元素连接起来。 find(p) - 查询 p 元素在哪个集合中。 isConnected(p,q) - 查看 p 和 q 两...
并查集快速查找
本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。 查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 合并元素 p 和元素 q ...