最小生成树：

带权连接图中最小生成树：含所有顶点（n个）和n-1条边且它们权值之和最小

Prime算法：拉点法

时间复杂度：O（n*2），n为顶点个数

先选一个顶点放入集合U中，然后把U外顶点和U中任一顶点连线权值最小的加入U中，这样每一步加入U的都是权值最小的，所以，得到的是最小生成树

例：求下图的最小生成树

第一步：假设从顶点0开始，把顶点0加入集合U

 

5到U中顶点权值最小，把5加入U

4到U中顶点权值最小，4加入U

3到U中顶点权值最小，3加入U

2到U中顶点权值最小，2加入U(不包括6，画错了)

下面是顶点1，顶点6依次加入U

Kruskal算法：拉边法

时间复杂度：O（e*2），e为边数

去掉图中的所有边，然后不断加入权值最小的边，如果加入后构成一个环，则舍弃这条边

直至加入n-1条边

例：求下图的最小生成树

第一步：去掉所有边

第二步：依次把最小权值的边拉入顶点中

 

拉入过程中判断是否构成环，如果构成环则舍弃这条边，找下一个最小的权值的边

 

 

 

# 算法 # 职场和发展 # leetcode
Logo
天工造物局

北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台

更多推荐

deck.gl TripsLayer 出租车轨迹动画示例实战：从示例运行到着色器原理

TripsLayer 是 deck.gl 中用于渲染**随时间流动的轨迹动画**（如出租车行程、物流路径、迁徙路线）的核心图层。本文以仓库中的最小独立示例 [examples/website/trips](https://link.gitcode.com/i/1442af8f442f4cff39ff546e050fceb5) 为骨架，带你完成从安装依赖、启动应用、理解曼哈顿出租车数据格式，到深入

avatar 天工造物局

Foundry Anvil 中 eth_simulateV1 的 Blob 交易与 Blob Gas 字段规范化：原理、实现与测试验证

本篇技术指南以 [anvil-simulate-blob-transactions.md](https://link.gitcode.com/i/3d2ebe227262de169335eb290af80da8) 这条 changelog 条目为起点，深入剖析 Foundry Anvil 对 `eth_simulateV1` RPC 返回结果中 blob（EIP-4844）交易与 blob gas

avatar 天工造物局

LMCache CLI 实战：用 `lmcache kvcache clear` 管理运行中服务的 KV Cache 状态

本文是一份针对 LMCache 官方 CLI 命令 `lmcache kvcache` 的完整技术指南。该命令用于在**运行中的 LMCache 服务（MP HTTP server）**上管理 KV cache 状态，当前提供 `clear` 子命令，用于清空 L1（CPU 内存）层中缓存的全部 KV 数据。读完本文，你将掌握该命令的完整参数体系、退出码语义、终端/JSON/静默三种输出模式，并能

avatar 天工造物局