一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 775|回复: 18
收起左侧

OA2 MST Prim算法

[复制链接] |试试Instant~ |关注本帖
NEO_FISH 发表于 2016-12-1 04:23:00 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Amazon - 内推 - 在线笔试 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
请问下OA2里MST为什么地里面经都用kruskal+Union方法啊?Prim可不可以?我觉得Prim写起来反而更简单,效率其实也差不太多。。。你们帮着参考一下这么写行不行?
        public static ArrayList<Connection> getLowCost(ArrayList<Connection> connections) {                . From 1point 3acres bbs
                //Output arraylist
                ArrayList<Connection> result=new ArrayList<>();
                //Edge case. visit 1point3acres.com for more.
                if(connections==null||connections.size()==0) return result;
                //Copy the given list to make sure it invariable during the operation
                //Linked list also has better performance on 'remove' function
                LinkedList<Connection> connectionsList = new LinkedList<>(connections);
                //Current MST
                HashSet<String> cities=new HashSet<>();
               
                //sort the list by the costs of the connections
.鐣欏璁哄潧-涓浜-涓夊垎鍦                Collections.sort(connectionsList,new Comparator<Connection>(){
                        @Override
                        public int compare(Connection A, Connection B) {
                                return Integer.compare(A.cost,B.cost);
                        }
                });               
                //After removing a connection from the list, break and check if it is empty
                while(!connectionsList.isEmpty()){
                        //this loop can make sure lower cost connection go first since the list is sorted 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        for(Connection connection:connectionsList){
                                String cityA=connection.node1;
                                String cityB=connection.node2;
                       
                                //first connection(MST is empty)
                                if(cities.isEmpty()){
                                        cities.add(cityA);
                                        cities.add(cityB);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                        result.add(connection);
                                        connectionsList.remove(connection);
                                        break;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                }else{                                       
                                        //If both cities of a connection are already in the MST, drop it 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                        if(cities.contains(cityA)&&cities.contains(cityB)){
                                                connectionsList.remove(connection);
                                                break;
                                        }
                                        //If only one city of a connection is in the MST, take it
                                        if(cities.contains(cityA)){
                                                result.add(connection);. From 1point 3acres bbs
                                                cities.add(cityB);
                                                connectionsList.remove(connection);
                                                break;
                                        }else if(cities.contains(cityB)){
                                                result.add(connection);
                                                cities.add(cityA);
                                                connectionsList.remove(connection);
                                                break;
                                        }
                                }
                                //if the list is not empty and no connections can be removed, the solution does not exist
                                return null;
                        }
                }
               
                //sort the result alphabetically        
                Collections.sort(result,new Comparator<Connection>(){
                        @Override
                        public int compare(Connection A,Connection B){
                                if(A.node1==B.node1) return A.node2.compareTo(B.node2);
                                return A.node1.compareTo(B.node1);
                        }
                });
                . Waral 鍗氬鏈夋洿澶氭枃绔,
                return result;
        }

. visit 1point3acres.com for more.


补充内容 (2016-12-2 13:03):
经过楼下两位提醒,修正了一些问题,见链接,带testcases,原贴代码作废。如果有兴趣的可以帮忙挑挑错:https://drive.google.com/file/d/0B2xvXF0mfGycZUtITEVVTzgzV28/view?usp=sharing

本帖被以下淘专辑推荐:

fireduck 发表于 2016-12-1 04:29:27 | 显示全部楼层
因为貌似现在的状况是code能做出来就行,就看ws部分了。。
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-12-1 13:58:32 | 显示全部楼层
if(A.node1==B.node1)
楼主这里有点问题,node是String,应该用 .equals
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-12-1 13:59:38 | 显示全部楼层
Henry要工作 发表于 2016-12-1 13:58
if(A.node1==B.node1)
楼主这里有点问题,node是String,应该用 .equals

                Collections.sort(result,new Comparator<Connection>(){.
                        @Override
                        public int compare(Connection A,Connection B){
                               if(A.node1==B.node1) return A.node2.compareTo(B.node2);
                                return A.node1.compareTo(B.node1);
                        }
                });
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-1 14:26:17 | 显示全部楼层
Henry要工作 发表于 2016-12-1 13:59
Collections.sort(result,new Comparator(){.
                        @Override
   ...
. from: 1point3acres.com/bbs
有道理!
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-1 14:57:54 | 显示全部楼层
NEO_FISH 发表于 2016-12-1 14:26.鐣欏璁哄潧-涓浜-涓夊垎鍦
有道理!

简单版的prim我记得复杂度是比kruskal高的,O(v^2)应该是。
Stack Overflow上是这么说的:
If you implement both Kruskal and Prim, in their optimal form : with a union find and a finbonacci heap respectively, then you will note how Kruskal is easy to implement compared to Prim.
. from: 1point3acres.com/bbs
Prim is harder with a fibonacci heap mainly because you have to maintain a book-keeping table to record the bi-directional link between graph nodes and heap nodes. With a Union Find, it's the opposite, the structure is simple and can even produce directly the mst at almost no additional cost.. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-1 15:21:18 | 显示全部楼层
oily 发表于 2016-12-1 14:57
简单版的prim我记得复杂度是比kruskal高的,O(v^2)应该是。
Stack Overflow上是这么说的:
If you impl ...
. from: 1point3acres.com/bbs
不会啊。我只用了一个hashset就存了,根本不用heap的, prim只需判断当前边两个顶点是否全在当前set里出现就行了,不用判断是否为同一union。所以只要当发现加不进边来的时候直接就知道MST不存在了。。。两个算法按理说一个是ElogE一个是ElogV,其实差不多。。。不过我提前按边sort了所以我这个的O(n)大概也是ElogE。。。
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-1 23:56:56 | 显示全部楼层
NEO_FISH 发表于 2016-12-1 15:21. visit 1point3acres.com for more.
不会啊。我只用了一个hashset就存了,根本不用heap的, prim只需判断当前边两个顶点是否全在当前set里出现 ...

你这按边集做的怎么好意思叫prim啊。。。。
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-2 00:00:34 | 显示全部楼层
NEO_FISH 发表于 2016-12-1 15:21
不会啊。我只用了一个hashset就存了,根本不用heap的, prim只需判断当前边两个顶点是否全在当前set里出现 ...

而且你的代码在下面这个case的情况应该是错的。

     1           2           1
A-----------B-----------C------------D
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 00:14:46 | 显示全部楼层
oily 发表于 2016-12-2 00:00.鏈枃鍘熷垱鑷1point3acres璁哄潧
而且你的代码在下面这个case的情况应该是错的。

     1           2           1

等等?你这个三个边四个点本身不就是MST了吗?
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 00:52:04 | 显示全部楼层
oily 发表于 2016-12-2 00:00
而且你的代码在下面这个case的情况应该是错的。

     1           2           1

我回去查了一下,多谢指正。终止条件想简单了。那个return null应该再往外一个循环放,然后加个判断cities.size循环前后不变得条件。。。如果愿意您可以再看看,至于你说我是按边做不是按点做的这个我倒是承认,但其实就是省事而已,本质还是通过遍历边来找下一个点的,没用的边直接remove了。。。
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-2 01:47:38 | 显示全部楼层
NEO_FISH 发表于 2016-12-2 00:52
. 1point3acres.com/bbs我回去查了一下,多谢指正。终止条件想简单了。那个return null应该再往外一个循环放,然后加个判断citie ...

从原理上来说kruskal就是按边集扩张做的MST,而prim是通过点集扩张做的,你这按边做的就别说是prim了吧。。。
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 04:17:34 | 显示全部楼层
oily 发表于 2016-12-2 01:47
从原理上来说kruskal就是按边集扩张做的MST,而prim是通过点集扩张做的,你这按边做的就别说是prim了吧。 ...

我这个肯定是Prim。我的点集是cities,是扩张这个集合来找MST。只不过找最近点的方法是通过遍历边来找,而没用Heap提前存好,没啥区别。Wiki上说The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex。只要这个算法每一步是加进一个不在现有树中的最近点就是Prim,所以没问题的。
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-2 11:25:43 | 显示全部楼层
NEO_FISH 发表于 2016-12-2 04:17
我这个肯定是Prim。我的点集是cities,是扩张这个集合来找MST。只不过找最近点的方法是通过遍历边来找,而 ...

不在现有树是关键,你这点集根本不能保证是树。
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 12:18:12 | 显示全部楼层
oily 发表于 2016-12-2 11:25
不在现有树是关键,你这点集根本不能保证是树。

能保证啊。话说你是觉得我的代码不对?还有啥testcase测测呗?
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-2 12:46:10 | 显示全部楼层
NEO_FISH 发表于 2016-12-2 12:18
能保证啊。话说你是觉得我的代码不对?还有啥testcase测测呗?

你觉得是就是吧,反正代码是不对的。。我也懒得给你找test case了。。你开心就好
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 12:47:09 | 显示全部楼层
oily 发表于 2016-12-2 12:46
你觉得是就是吧,反正代码是不对的。。我也懒得给你找test case了。。你开心就好
-google 1point3acres
呵呵。。。
回复 支持 反对

使用道具 举报

duziyuanyang 发表于 2016-12-2 13:14:22 | 显示全部楼层
现在oa2不求最优解的,做的太好也不见得是件好事。。反倒是ws好好准备,lz加油!
回复 支持 反对

使用道具 举报

koko7766 发表于 2016-12-6 14:28:04 | 显示全部楼层
我赞成楼主你的算法 没有具体测过你的code但是看思路这就是prim没错 点集最后对比size就可以判断是不是树  
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-1-22 20:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表