[亚马逊OA2] 最小生成树_MST
发布网友
发布时间：2022-12-05 17:41
共1个回答
热心网友
时间：2024-01-13 09:50
首先要感谢
白马书院的姑娘
提供的解题思路和面经。
我都知道你们这些人都不愿意查资料，所以就先讲讲什么是MST。
也就是在一个无向有权图（edge-weighted undirected graph）中，存在的一棵spanning tree，不成环的情况下连接所有的节点，并且具有最小权重总和，这颗树，就是MST。（节点数 = N，边数 = N - 1）
那么万恶的亚马逊会绕着弯给你出这个题。
抽象出来就是在无向权重图中找MST的题。我的解法也是根据Kruskal's Algorithm来的（维基百科里面解释得挺好的，有兴趣的同学可以去看看）。
算法里面涉及到Union Find，所以比较繁杂。大家做好准备一起来。
由于前一篇Order Dependency有同学说看不懂，我就尽量写得更好一点
先上图：
这里的MST：
再上例子图：
AD, BC, DC, EF, CF
最后的权重和为9
看到这儿了都不点个赞，是不是有点说不过去了？
