题目：
https://i.imgur.com/jZlEzBr.png
我的想法：
https://i.imgur.com/JDGuqyF.jpg
谢谢大家

adjacency list实作的时候应该就有用到array了答案应该是O(V^2) 吧？

个人看法：答案是O(VE)没错，因为使用adjacency list的缘故，每扫一次list来找lightest edge或decrease key都是O(V+E)，而由于目的是要寻找minimum spanning tree，代表只需要做V-1回，故时间复杂度为O((V-1)*(V+E))=O(V^2+VE)=O(VE)=O(V^2.5)另外原Po可以不必管Queue，就像题目要求的，没有额外的data structure被拿来应用，只需考虑adjacency list即可。

decrease key应该只要O(V)吧?这题不可能不用额外的空间存 不然根本不知道哪个点visit过了抱歉打错 decrease key应该是O(1) find min才是O(V)这题就算直接在整个adj list找min 也是需要一个array来存哪个点visit过了 总之我觉得因为adj list实做时已经用到array了 所以使用array不算额外的DS 再者退一步来说我也可以直接再用一条adj list来当array

完全不需要array啊，今天扫完取完第一个边之后，就把该边的list从adjacency list里删掉，而且list根本就不会用到array啊

就算删掉还是需要知道哪些点已经被找过了吧@@

我觉得没有硬凑啊，adjacency list是用linked list实作的欸，根本不关array的事情啊；另外我这边decrease key应该可以不用管，我后来重写一次code发现其实只需要用union, find_set就可以了，所以就只是简单的做(V-1)回找最小边，并透过union, find_set来验证acyclic，这样时间复杂度仍是O(VE)，a大能否提供您的详细算法让我参考看看？我仍认为答案是O(V^2.5)没错，谢谢另外我发现一件事情，a大其实你的答案是对的欸，只是你一个地方弄错了，find_min不是O(V)哦，找最小是在所有边中找最小权重，所以理论上应该会是O(E)

请教一下真男人，这题我刚刚用您的讲解模拟了几次。我在由start点出发后的每次decreasekey把全部linklist搜一遍也就是说，不识别已搜索过的点，每次都跑2E来进行decrease这样子我才有办法算出O(VE)不然我怎么算都是O(V눫2E)O(V^2+2E)也就是O(V^2)

Prim并不是在找最小"边"权重 而是每次找距离树最小的"点"所以find_min是O(V)http://www.csie.ntnu.edu.tw/~u91029/Algorithm.htmlhttps://i.imgur.com/0b3iEJP.jpgR大不好意思 看了你后面的推文 感觉好像是kruskal的算法我们是不是在讨论不同的东西 才会互相觉得奇怪@@

@@我是用Prim’s没错啊

这题不管怎样都得需要额外的空间吧 至少需要存 distance

Prim怎么会有union, find_set,验证acyclic 和kruskal有9成像