动态连通性问题中的并查集
简介 union-find 是为了解决动态连通性问题而提出来的一个算法，而对应的数据结构被称为并查集，集即集合。 动态连通性问题，可以联想到编程中两个变量名是否等价、集合中两个元素是否属于同一个集合、图中两个节点是否连通等。 简单地说，给你一些相连的节点对，让你判断一个新的节点对是否相连。
阅读更多四则运算表达式求值：中缀改后缀
简介 在提到栈的应用时，有一个很典型的例子就是表达式求值。 具体应用时体现在： 中缀表达式转后缀表达式：运算符栈 后缀表达式求值：操作数栈 若直接进行中缀表达式求值，需同时操作两个栈，而将中缀表达式转为后缀表达式再求值时，每个步骤只需要专注于一个栈，操作起来更简单。本文就介绍这种方法。
阅读更多KMP 算法：找子串的位置
简介 字符串的算法中，有一个是做模式匹配，让你找子串的位置。 如果用暴力解法，那就是一个双重 for 循环，以主串的每个字符为开头，往后走，看是不是跟子串完全一致。这样的算法时间复杂度是 $O(n \times m)$。有没有更好的算法呢？
阅读更多最小生成树
最小生成树：Kruskal算法和Prim算法的实现 这里直接给出离散数学中的几个定理和推论： 无向图G具有生成树当且仅当G连通. G为n阶m条边的无向连通图，则 m >= n - 1. G是树 $\Leftrightarrow$ G中任意两个顶点之间存在唯一路径 $\Leftrightarrow$ G中无回路且m=n-1$\Leftrightarrow$ G是连通的且m=n-1$\Leftrightarrow$ G中没有回路但在任何2个不同的顶点间加一条新边就能在图中得到唯一的含新边的环圈. 生成子图指的是顶点集相同，但边集是图G的子集的图. 生成树指的是图G的生成子图并且是树. 最小生成树指的是图G的所有生成树中权最小的. 算法第4版中这样定义：
阅读更多