首页

投稿

最小生成树：从最短的边加起，成环的跳过

207

0

2026-09-25 17:01:35

用六个镇子铺光缆讲解最小生成树和 Kruskal 算法：最省的方案一定是一棵树；把边按长度排好，从最短的开始加，两头已经连通、会成环的就跳过，判断连通交给并查集。切分性质保证每一步都对；Prim 用同一个道理从一个点长出去。时间 O(E log E)。

大会员十周年

最小生成树

成富_Alex 发消息

全栈工程师 / 架构师 / 技术内容创作者 / 非畅销书作者

KMP 算法是如何工作的？

04:11

Boyer–Moore 算法：从右往左，越错越快

03:49

Rabin-Karp：滚动哈希如何找模式串？

05:50

Manacher：照着回文的镜像，一遍找出最长回文

05:38

Trie 树：搜索框为什么总能猜中你想输入什么？

03:43

Aho–Corasick：一次扫描，找出所有关键词

06:12

Radix 树：把只有一条路的 Trie 压成一条边

04:06

后缀树：一个文本的所有后缀，压进一棵树

03:29

Z 算法：每个位置能和开头对上多长？

03:37

后缀数组：把所有后缀排好队，找子串就是二分

03:48

二叉搜索树：左小右大，为什么还会退化成链表？

03:23

AVL 树：高度差一过 1，就转一下

05:59

红黑树：用颜色换掉大部分旋转

05:23

跳表：如何用链表实现期望 O(log n) 查找？

04:16

Fenwick 树：一个数组算出所有排名

04:05

线段树：区间修改，可以先欠着

03:51

Treap：随机优先级让树自己保持平衡

03:48

笛卡尔树：一个数组，线性时间建成一棵既有序又成堆的树

04:29

区间树：和这个时间段冲突的日程，一次找全

04:37

Merkle 树：一个哈希值担保整份数据

03:51

二叉堆：藏在数组里的树，只保证堆顶最小

04:59

Top-K 与中位数：一个堆守前 k 名，两个堆守中间

03:43

多路归并：堆里只放每一路的队头

03:38

左偏树：让右边永远最短，合并只走右脊

04:25

二项堆：像二进制加法一样合并两个堆

04:54

配对堆：合并只比一次根

04:08

斐波那契堆：先欠着，等弹出时再一次结算

04:43

BFS 和 DFS：队列换成栈，走法全变了

03:48

Dijkstra：为什么最短的路不是每一步都最短

03:18

并查集：两个点连通吗？几乎 O(1) 就能回答

04:36

最小生成树：从最短的边加起，成环的跳过

03:44

拓扑排序：谁也不等的，先走

03:36

A*：让 Dijkstra 知道终点在哪

03:50

哈希表：为什么装到四分之三就要扩容？

04:22

Robin Hood 哈希：冲突时让离家更远的先坐

04:44

跳房子哈希：空位就在前面，为什么不能直接用

04:24

布谷鸟哈希：一个 key 两个家，占了就踢走

03:56

布隆过滤器：说“不在”一定对，说“在”可能错

04:02

布谷鸟过滤器：和布隆一样小，但能删除

04:05

XOR 过滤器：比布隆更小、更快，只要集合不再变

06:48

Count-Min Sketch：几 KB 内存如何数清海量数据？

04:33

HyperLogLog：12KB 如何数清十亿用户？

04:40

MinHash：怎样用几个数字判断两个集合有多像？

04:37

SimHash：把一篇文章压成 64 位指纹

04:42

蓄水池抽样：从长度未知的流里公平地抽样

04:58

顶部