---
title: "Discussion on \"最小生成树（Minimum Spanning Tree, MST）\" | Hashnode"
description: "Discussion on \"最小生成树（Minimum Spanning Tree, MST）\". 这玩意儿听起来挺唬人，但其实思想特别朴素。想象一下，现在有几个村庄，你要负责修路把它们都连起来，并且想花最少的钱。每条备选的路都有一个造价。你怎么设计这个路网，才能保证所有村庄都能互相到达，并且总造价最低？\n这就是最小生成树。给你一张带权重的无向图，找一棵能连接所有顶点的树，并且这棵树所有边的权重之和最小。\n扯远了，拉回来。搞定这个问题，有两个经典的“骚操作”，一个叫Kruskal，一个叫Prim。这两个都是贪心算法，但贪心的角度不太一样。今天咱们把这俩都盘明白了。\n准备工作：图怎么表示？\n在撸..."
url: "https://hashnode.com/posts/minimum-spanning-tree-mst/68dfdf4d937c67cba0b916b5"
---

[Feed](https://hashnode.com/feed) /

Discussion

# [最小生成树（Minimum Spanning Tree, MST）](https://xiaoh.hashnode.dev/minimum-spanning-tree-mst?utm_source=hashnode&utm_medium=feed)

这玩意儿听起来挺唬人，但其实思想特别朴素。想象一下，现在有几个村庄，你要负责修路把它们都连起来，并且想花最少的钱。每条备选的路都有一个造价。你怎么设计这个路网，才能保证所有村庄都能互相到达，并且总造价最低？ 这就是最小生成树。给你一张带权重的无向图，找一棵能连接所有顶点的树，并且这棵树所有边的权重之和最小。 扯远了，拉回来。搞定这个问题，有两个经典的“骚操作”，一个叫Kruskal，一个叫Prim。这两个都是贪心算法，但贪心的角度不太一样。今天咱们把这俩都盘明白了。 准备工作：图怎么表示？ 在撸...

Oct 3, 2025 · 5 min read · xiaoh.hashnode.dev  
Read the article

-   [#minimum-spanning-tree-mst](https://hashnode.com/tag/minimum-spanning-tree-mst)

## Written by

[MrHe](https://hashnode.com/@MrHe)

@MrHe

  
[View profile](https://hashnode.com/@MrHe)

河南科技大学-软件工程

## Responses

Markdown supported · ⌘↵ to post

No responses yet.
