作者cschenptt (chen)
看板Grad-ProbAsk
标题[理工] 104台大资演 Prim's
时间Sat Jan 5 22:37:19 2019
题目：
https://i.imgur.com/jZlEzBr.png
我的想法：
https://i.imgur.com/JDGuqyF.jpg
谢谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.25.121
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1546699043.A.B3F.html
※ 编辑: cschenptt (140.112.25.121), 01/05/2019 22:38:58
1F：推 anonimo: adjacency list实作的时候应该就有用到array了 01/05 23:57
2F：→ anonimo: 答案应该是O(V^2) 吧？ 01/06 00:14
3F：推 realmanKG: 个人看法：答案是O(VE)没错，因为使用adjacency list的 01/06 01:23
4F：→ realmanKG: 缘故，每扫一次list来找lightest edge或decrease key都 01/06 01:23
5F：→ realmanKG: 是O(V+E)，而由於目的是要寻找minimum spanning tree， 01/06 01:23
6F：→ realmanKG: 代表只需要做V-1回，故时间复杂度为O((V-1)*(V+E))=O(V 01/06 01:23
7F：→ realmanKG: ^2+VE)=O(VE)=O(V^2.5) 01/06 01:23
8F：→ realmanKG: 另外原Po可以不必管Queue，就像题目要求的，没有额外的 01/06 01:25
9F：→ realmanKG: data structure被拿来应用，只需考虑adjacency list即 01/06 01:25
10F：→ realmanKG: 可。 01/06 01:25
11F：→ anonimo: decrease key应该只要O(V)吧? 01/06 02:13
12F：→ anonimo: 这题不可能不用额外的空间存 不然根本不知道哪个点visit 01/06 02:14
13F：→ anonimo: 过了 01/06 02:15
14F：→ anonimo: 抱歉打错 decrease key应该是O(1) find min才是O(V) 01/06 02:16
15F：→ anonimo: 这题就算直接在整个adj list找min 也是需要一个array 01/06 02:34
16F：→ anonimo: 来存哪个点visit过了 总之我觉得因为adj list实做时已经 01/06 02:36
17F：→ anonimo: 用到array了 所以使用array不算额外的DS 再者退一步来说 01/06 02:36
18F：→ anonimo: 我也可以直接再用一条adj list来当array 01/06 02:37
19F：推 realmanKG: 完全不需要array啊，今天扫完取完第一个边之後，就把该 01/06 09:39
20F：→ realmanKG: 边的list从adjacency list里删掉，而且list根本就不会 01/06 09:39
21F：→ realmanKG: 用到array啊 01/06 09:39
22F：→ anonimo: 就算删掉还是需要知道哪些点已经被找过了吧@@ 01/06 12:20
我大概懂了
所以我的方式 其实是还没简化完时间复杂度
简化完後 会如真男人KG大所说的计算结果
同时也符合补习班的答案
感谢两位大大的讨论
我想a大所讨论的纪录细节 若在实际coding或许是必须的
例如可以开张table(应该就是您所说的array去纪录)
但我猜此处是可以忽略这部分的实作细节（？）
而且table的话 查找时间是O(1)
到时候简化时会被其他部分的时间吃掉
※ 编辑: cschenptt (140.112.25.121), 01/07/2019 02:28:12
23F：→ anonimo: 我不同意你的说法 明明有更快的时间为什麽不写? 01/07 11:25
24F：→ anonimo: 补习班答案不一定是对的吧 这样感觉根本是在凑补习班的 01/07 11:26
25F：→ anonimo: 答案 是说我这里刚好有一份补习班答案(讲义)就是写O(V^2) 01/07 11:27
26F：推 realmanKG: 我觉得没有硬凑啊，adjacency list是用linked list实作 01/07 17:16
27F：→ realmanKG: 的欸，根本不关array的事情啊；另外我这边decrease key 01/07 17:16
28F：→ realmanKG: 应该可以不用管，我後来重写一次code发现其实只需要用u 01/07 17:16
29F：→ realmanKG: nion, find_set就可以了，所以就只是简单的做(V-1)回找 01/07 17:16
30F：→ realmanKG: 最小边，并透过union, find_set来验证acyclic，这样时 01/07 17:16
31F：→ realmanKG: 间复杂度仍是O(VE)，a大能否提供您的详细算法让我参考 01/07 17:16
32F：→ realmanKG: 看看？我仍认为答案是O(V^2.5)没错，谢谢 01/07 17:16
33F：→ realmanKG: 另外我发现一件事情，a大其实你的答案是对的欸，只是你 01/07 17:19
34F：→ realmanKG: 一个地方弄错了，find_min不是O(V)哦，找最小是在所有 01/07 17:19
35F：→ realmanKG: 边中找最小权重，所以理论上应该会是O(E) 01/07 17:19
36F：推 leviliang: 请教一下真男人，这题我刚刚用您的讲解模拟了几次。 01/07 19:49
37F：→ leviliang: 我在由start点出发後的每次decreasekey把全部linklist 01/07 19:51
38F：→ leviliang: 搜一遍 01/07 19:51
39F：推 leviliang: 也就是说，不识别已搜索过的点，每次都跑2E来进行decre 01/07 19:53
40F：→ leviliang: ase 01/07 19:53
41F：→ leviliang: 这样子我才有办法算出O(VE) 01/07 19:53
42F：→ leviliang: 不然我怎麽算都是O(V눫2E) 01/07 19:55
43F：→ leviliang: O(V^2+2E) 01/07 19:55
44F：→ leviliang: 也就是O(V^2) 01/07 19:55
45F：→ anonimo: Prim并不是在找最小"边"权重 而是每次找距离树最小的"点" 01/07 21:30
46F：→ anonimo: 所以find_min是O(V) 01/07 21:30
49F：→ anonimo: R大不好意思 看了你後面的推文 感觉好像是kruskal的算法 01/07 22:08
50F：→ anonimo: 我们是不是在讨论不同的东西 才会互相觉得奇怪@@ 01/07 22:09
51F：推 realmanKG: @@我是用Prim’s没错啊 01/08 09:16
52F：推 FRAXIS: 这题不管怎样都得需要额外的空间吧 至少需要存 distance 01/08 12:04
53F：→ anonimo: Prim怎麽会有union, find_set,验证acyclic 和kruskal有9 01/08 12:58
54F：→ anonimo: 成像 01/08 12:58
55F：推 jimmy1112111: 不是O(VE)吧，adj list的每个node顶多只会拜访到V 01/26 11:27
56F：→ jimmy1112111: -1个vertices(假如graph是Kn的话)，又不是每个ver 01/26 11:27
57F：→ jimmy1112111: tex在一个回合内拜访到图中每个edge，所以第一小题 01/26 11:27
58F：→ jimmy1112111: 顶多O(V^2) 01/26 11:27