并查集
并查集三步走 并查集，开始的时候大家都是孤岛，根节点就是自己，然后我们不断地合并、修改指针，直到所有边都访问到。 数组初始化，每个节点的 parent 指针都指向自己。数组 roots 存放所有节点的祖先节点（根节点，路径压缩）【如果要求子集中元素数量，那么还要再创建一个 counts 数组，存储一份子集元素中的数量，需要在 union 中更新】。 根据所有相连的边，不断地进行查找、合并。 查找用递归、同时能修改查找路径上的所有节点的 parent 指针，合并前先调用查找然后看是否同一子图，是则合并失败，不是则直接将 parent 指针修改一下即可。 **有向图是否有环？**拓扑排序 DAG ！
阅读更多最小生成树
最小生成树：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版中这样定义：
阅读更多