时间复杂度 time complexity 计算机科学
时间复杂度 (time complexity) 用来描述算法运行时间随输入规模增长的变化趋势，而不是具体的运行时间（秒） 常用大O符号（Big O notation）表示 如 O(1) O(n)、O(n²)、O(log n) 等
广度优先遍历与最短路径
广度优先遍历与最短路径 广度优先遍历从某个顶点 v 出发，首先访问这个结点，并将其标记为已访问过，然后顺序访问结点v的所有未被访问的邻接点 {vi,..,vj} ，并将其标记为已访问过，然后将 {vi,...,vj} 中的每一个节点重复节点v的访问方法，直到所有结点都被访问完为止。我们可以分为三个步骤： （1）使用一个辅助队列 q，首先将顶点 v 入队，将其标记为已访问，然后循环检测队列是否为空。 （2）如果队列不为空，则取出队列第一..
寻路算法
寻路算法 图的寻路算法也可以通过深度优先遍历 dfs 实现，寻找图 graph 从起始 s 点到其他点的路径，在上一小节的实现类中添加全局变量 from数组记录路径，from[i] 表示查找的路径上i的上一个节点。 首先构造函数初始化寻路算法的初始条件，from = new int[G.V()] 和 from = new int[G.V()]，并在循环中设置默认值，visited 数组全部为false，from 数组全部为 -1 值，后..
深度优先遍历与连通分量
深度优先遍历与连通分量 深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直至所有的顶点都被访问过。 下图示例的图从 0 开始遍历顺序如右图所示： 无向图 G 的一个极大连通子图称为 G 的一个连通分量（或连通分支）。连通图只有一个连通分量，即其自身；非连通的无向图有多个连通分量。连通分..
相邻节点迭代器
相邻节点迭代器 图论中最常见的操作就是遍历邻边，通过一个顶点遍历相关的邻边。邻接矩阵的遍历邻边的时间复杂度为 O(V)，邻接表可以直接找到，效率更高。 邻接矩阵迭代: [mycode4 type='java'] ... public Iterable adj(int v) { assert v >= 0 && v < n; Vector adjV = new Vector..
图论基础和表示
图论基础和表示 概念及其介绍 图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问 图是用来对对象之间的成对关系建模的数学结构，由“节点”或“顶点”(Vertex）以及连接这些顶点的“边”（Edge）组成 图的顶点集合不能为空，但边的集合可以为空 图可能是无向的，这意味着图中的边在连接顶点时无需区分方向 否则，称图是有向的
并查集路径压缩
并查集路径压缩 并查集里的 find 函数里可以进行路径压缩，是为了更快速的查找一个点的根节点。对于一个集合树来说，它的根节点下面可以依附着许多的节点，因此，我们可以尝试在 find 的过程中，从底向上，如果此时访问的节点不是根节点的话，那么我们可以把这个节点尽量的往上挪一挪，减少数的层数，这个过程就叫做路径压缩。 如下图中，find(4) 的过程就可以路径压缩，让数的层数更少。 节点 4 往上寻找根节点时，压缩第一步，树的层数就减少..
并查集 rank 的优化
并查集 rank 的优化 上一小节介绍了并查集基于 size 的优化，但是某些场景下，也会存在某些问题，如下图所示，操作 union(4,2)。 根据上一小节，size 的优化，元素少的集合根节点指向元素多的根节点。操作完后，层数变为4，比之前增多了一层，如下图所示： 由此可知，依靠集合的 size 判断指向并不是完全正确的，更准确的是，根据两个集合层数，具体判断根节点的指向，层数少的集合根节点指向层数多的集合根节点，如下图所示，这..
并查集 size 的优化
并查集 size 的优化 按照上一小节的思路，我们把如下图所示的并查集，进行 union(4,9) 操作。 合并操作后的结构为： 可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进行判断，把元素少的集合根节点指向元素多的根节点，能更高概率的生成一个层数比较低的树。 构造并查集的时候需要多一个参数，sz 数组，sz[i] 表示以 i 为..
并查集快速合并
并查集快速合并 对于一组数据，并查集主要支持两个动作： union(p,q) - 将 p 和 q 两个元素连接起来。 find(p) - 查询 p 元素在哪个集合中。 isConnected(p,q) - 查看 p 和 q 两个元素是否相连接在一起。 在上一小节中，我们用 id 数组的形式表示并查集，实际操作过程中查找的时间复杂度为 O(1)，但连接效率并不高。本小节，我们将用另外一种方式实现并查集。把每一个元素，看做是一个..
