一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 566|回复: 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) {               
                //Output arraylist
                ArrayList<Connection> result=new ArrayList<>();-google 1point3acres
                //Edge case
                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>(){.1point3acres缃
                        @Override. 1point 3acres 璁哄潧
                        public int compare(Connection A, Connection B) {
                                return Integer.compare(A.cost,B.cost);
                        }. 1point 3acres 璁哄潧
                });               
                //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()){. 鍥磋鎴戜滑@1point 3 acres
                                        cities.add(cityA);
                                        cities.add(cityB);
                                        result.add(connection);. visit 1point3acres.com for more.
                                        connectionsList.remove(connection);
                                        break;
                                }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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                                        //If only one city of a connection is in the MST, take it
                                        if(cities.contains(cityA)){
                                                result.add(connection);
                                                cities.add(cityB);
                                                connectionsList.remove(connection);
                                                break;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                        }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);
                        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                });
               
                return result;
        }




补充内容 (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
.鏈枃鍘熷垱鑷1point3acres璁哄潧
                Collections.sort(result,new Comparator<Connection>(){. . visit 1point3acres.com for more.
                        @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.鏈枃鍘熷垱鑷1point3acres璁哄潧
Collections.sort(result,new Comparator(){.
                        @Override
   ...

有道理!
回复 支持 反对

使用道具 举报

oily 发表于 2016-12-1 14:57:54 | 显示全部楼层

简单版的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.

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.
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-1 15:21:18 | 显示全部楼层
oily 发表于 2016-12-1 14:57
简单版的prim我记得复杂度是比kruskal高的,O(v^2)应该是。
Stack Overflow上是这么说的:. 鍥磋鎴戜滑@1point 3 acres
If you impl ...

不会啊。我只用了一个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. 1point 3acres 璁哄潧
不会啊。我只用了一个hashset就存了,根本不用heap的, prim只需判断当前边两个顶点是否全在当前set里出现 ...

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

使用道具 举报

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

而且你的代码在下面这个case的情况应该是错的。
. 鍥磋鎴戜滑@1point 3 acres
     1           2           1
A-----------B-----------C------------D
回复 支持 反对

使用道具 举报

 楼主| NEO_FISH 发表于 2016-12-2 00:14:46 | 显示全部楼层
oily 发表于 2016-12-2 00:00
而且你的代码在下面这个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
我回去查了一下,多谢指正。终止条件想简单了。那个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. 1point3acres.com/bbs
不在现有树是关键,你这点集根本不能保证是树。

能保证啊。话说你是觉得我的代码不对?还有啥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了。。你开心就好

呵呵。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 15:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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