[理工] Prim’s MST NTUmaki PTT批踢踢实业坊

[理工] Prim’s MST

楼主: NTUmaki (西木野真姬) 2020-09-12 20:14:23

想问他的边顺序怎么是 {a,b}马上接 {b,f}？
而且以这题来说，过程中应该会有边被砍掉才对吧（像 be被砍掉改成 eg）
https://i.imgur.com/VbHSk4M.jpg

作者: cossetannie (paa) 2020-09-12 21:27:00

因为(b,f)weight是最小啊或是要选(b,g)也可以为什么要砍(b,e) 本来就不会选那条edge吧

楼主: NTUmaki (西木野真姬) 2020-09-13 22:06:00

我大概知道了@@ 你说的方法好像是另一个版本的Prim’s 立宇这边的版本会先extract min然后所有相邻点key>weight的都会更新那这样没事了～CLRS的版本边会改动这题应该是用另一个版本的prim’s

继续阅读

[理工] 线代正交tcbt32 [理工] 离散 101中山资工try66889 机率贝氏定理AdonisLam [理工] 黄子嘉离散1-18 例19nick9362 [理工] 线代线性代数两小题try66889 [理工] pseudo polynomial timeNTUmaki [理工][热力]焓讨论Handanrevery [理工] 线代-黄子嘉下 p8-152范例8 97交大电控a123543 [理工] 线代 5-53aa871220 Re: [理工] 算法 NP-complete证明mi981027

Contact Us: admin [ a t ] ucptt.com