MST（Minimum Spanning Tree，最小生成树）

青旅半醒 2022-08-07 14:46 13阅读 0赞

![Center][]

**今天从志权师兄那里学会了最小生成树。所谓生成树，就是n个点之间连成n-1条边的图形。**

**而最小生成树，就是权值（两点间直线的值）之和的最小值！**

**首先，要用二维数组记录点和权值。如上图所示无向图：**

**nt map\[7\]\[7\];  
       map\[1\]\[2\]=map\[2\]\[1\]=4;  
       map\[1\]\[3\]=map\[3\]\[1\]=2;  
       ......**

** 然后再求最小生成树。具体方法是：**

**1.先选取一个点作起始点，然后选择它邻近的权值最小的点（如果有多个与其相连的**

**相同最小权值的点，随便选取一个）。如1作为起点。**

**visited\[1\]=1;**

pos=1;

**//用low\[\]数组不断刷新最小权值，low\[i\](0<i<=点数)的值为：i点到邻近点（未被标**

**记）的最小距离。**

low\[1\]=0;  //起始点i到邻近点的最小距离为0

low\[2\]=map\[pos\]\[2\]=4;

low\[3\]=map\[pos\]\[3\]=2;

low\[4\]==map\[pos\]\[4\]=3;

low\[5\]=map\[pos\]\[5\]=MaxInt;  //无法直达

low\[6\]=map\[pos\]\[6\]=MaxInt;

2.再在伸延的点找与它邻近的两者权值最小的点。

**//low\[\]以3作当前位置进行更新**

visited\[3\]=1;

pos=3;

low\[1\]=0;   //已标记，不更新

low\[2\]=map\[1\]\[2\]=4;  //比5小，不更新

low\[3\]=2;  //已标记，不更新

low\[4\]=map\[1\]\[4\]=3;   //比1大，更新后为：low\[4\]=map\[3\]\[4\]=1;

low\[5\]=map\[1\]\[5\]=MaxInt;//无法直达，不更新

low\[6\]=map\[1\]\[6\]=MaxInt;//比2大，更新后为：low\[6\]=map\[3\]\[6\]=2;

![Center 1][]

[Center]: /images/20220805/e0514c620b23415cbad2bd2f13ff3358.png
[Center 1]: /images/20220805/186a068ce1e94ecbb5f357f4c297785f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，13人围观）

还没有评论，来说两句吧...

相关阅读

相关最小生成树 | 市政道路拓宽预算的优化 (Minimum Spanning Tree)

![6e5720b3741f50079776db4e3d2ff90a.png][] 任务描述：市政投资拓宽市区道路，本着执政为民，节省纳税人钱的目的，论证是否有必要对每一

本是古典何须时尚/ 2024年02月28日 03:17/ 0 赞/ 34 阅读

相关【最小生成树问题（Minimum Spanning Tree）——图】

最小生成树问题（Minimum Spanning Tree）——图 1、最小生成树（Minimum Spanning Tree） 2、最小生成树

r囧r小猫/ 2022年12月20日 05:42/ 0 赞/ 108 阅读

相关最小生成树

最小生成树定义：在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即![(u, v)\\in E][u_ v_in E]），而

末蓝、/ 2022年09月20日 15:18/ 0 赞/ 205 阅读

相关生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）

生成树相关问题（最小生成树变形，次小生成树，最小度限度生成树，极差最小生成树）视频：[https://www.bilibili.com/video/BV1G64y187ke

Bertha 。/ 2022年09月12日 05:52/ 0 赞/ 215 阅读

相关 MST（Minimum Spanning Tree，最小生成树）

![Center][] 今天从志权师兄那里学会了最小生成树。所谓生成树，就是n个点之间连成n-1条边的图形。而最小生成树，就是权值（两点间直线的值）之和的最小值！

青旅半醒/ 2022年08月07日 14:46/ 0 赞/ 14 阅读

相关 Slim Span UVA - 1395 ——Kruskal算法生成最小树

Think: 1Kruskal算法生成最小树 2题意理解: 1>生成一颗最小树使得他的边的最大权值减去边的最小权值最小 3思路:从权值最小的边出发建立最小生成树

待我称王封你为后i/ 2022年06月15日 06:57/ 0 赞/ 141 阅读

相关最小生成树

有n个城市，m条道路，现在输入n到m的道路的长度，用最少的边将图连接，输出让图连接的最小值这道题我研究了好长时间才把答案看明白，现在给大家分享一下具体代码如下

爱被打了一巴掌/ 2022年05月30日 08:56/ 0 赞/ 183 阅读

相关 HDU 4786Fibonacci Tree(最小生成树)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total

怼烎@/ 2022年04月10日 11:45/ 0 赞/ 167 阅读

相关最小生成树

问题提出：要在n个城市间建立通信联络网。顶点：表示城市，权：城市间通信线路的花费代价。希望此通信网花费代价最小。问题分析：答案只能从生成树中找，因为要做到任何

雨点打透心脏的1/2处/ 2022年03月18日 12:28/ 0 赞/ 298 阅读

相关最小生成树

Jungle Roads [http://poj.org/problem?id=1251][http_poj.org_problem_id_1251] Descrip

逃离我推掉我的手/ 2021年11月29日 22:28/ 0 赞/ 434 阅读