自学教程Ruby 环境
本地环境设置 如果您想要设置 Ruby 编程语言的环境，请阅读本章节的内容。本章将向您讲解与环境设置有关的所有重要的主题。建议先学习下面几个主题，然后再进一步深入学习其他主题： Linux/Unix 上的 Ruby 安装：如果您想要在 Li...
服务端 第10页
脚本语言
Linux apt 命令
apt（Advanced Packaging Tool）是一个在 Debian 和 Ubuntu 中的 Shell 前端软件包管理器。 apt 命令提供了查找、安装、升级、删除某一个、一组甚至全部软件包的命令，而且命令简洁而又好记。 apt...
广度优先遍历与最短路径
广度优先遍历从某个顶点 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) 操作。 合并操作后的结构为： 可以发现，这个结构的树的层相对较高，若此时元素数量增多，这样产生的消耗就会相对较大。解决这个问题其实很简单，在进行具体指向操作的时候先进...