作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
标题[理工] Prim’s MST
时间Sat Sep 12 20:14:23 2020
想问他的边顺序怎麽是 {a,b}马上接 {b,f}？
而且以这题来说，过程中应该会有边被砍掉 才对吧（像 be被砍掉改成 eg）
https://i.imgur.com/VbHSk4M.jpg
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 110.30.113.166 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1599912865.A.2BC.html
1F：推 cossetannie: 因为(b,f)weight是最小啊 09/12 21:27
prims会先选第一个被extract的点的相邻点
2F：→ cossetannie: 或是要选(b,g)也可以 09/12 21:28
3F：→ cossetannie: 为什麽要砍(b,e) 本来就不会选那条edge吧 09/12 21:29
因为过程中更动key值，所以边会砍掉（pi换人） 很正常吧！？
※ 编辑: NTUmaki (39.11.35.180 台湾), 09/13/2020 22:02:04
※ 编辑: NTUmaki (39.11.35.180 台湾), 09/13/2020 22:03:37
4F：→ NTUmaki: 我大概知道了@@ 你说的方法好像是另一个版本的Prim’s 立 09/13 22:06
5F：→ NTUmaki: 宇这边的版本会先extract min然後所有相邻点key>weight的 09/13 22:06
6F：→ NTUmaki: 都会更新 09/13 22:06
7F：→ NTUmaki: 那这样没事了～CLRS的版本边会改动 这题应该是用另一个版 09/13 22:11
8F：→ NTUmaki: 本的prim’s 09/13 22:11