一亩三分地论坛

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

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

Berkeley CS 61B Data Structures(in Java) Project3 Kruskal

[复制链接] |试试Instant~ |关注本帖
zj45499 发表于 2015-1-29 15:41:59 | 显示全部楼层 |阅读模式

[Coursera]CS 61B Data Structures(in Java) #25 - 2014@Berkeley

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

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

x
好像还没有帖子.


Screen Shot 2015-01-29 at 3.23.39 PM.jpg

Screen Shot 2015-01-29 at 3.22.52 PM.jpg

评分

1

查看全部评分

lyc1994 发表于 2015-8-15 18:59:19 | 显示全部楼层
终于写完project3!project3的主要内容是设计出储存undirected, weighted graph的数据结构(Part1),并在此基础上使用Kruskal算法产生minimum spanning tree(Part 2)。
因为对存,取,删除graph中的vertex以及edge有时间要求,所以Part1中的数据结构十分复杂,用到了哈希表,DList。Part2部分则涉及到了sorting,Disjoint Sets,可以说覆盖了课程后半部分的大部分知识点。不过在做完homework 9之后,做本project就没有问题了。
由于graph的数据结构中有大量引用,例如partner references,vertex哈希表中的对象与vertex list中的对象相互引用,edge对象引用vertex对象,vertex对象引用edge list对象等等,我的处理方法是定义DListNode的子类GraphListNode来描述vertex以及edge。在GraphListNode中定义两个指向GraphListNode引用以及一个指向GraphList的引用,以适应graph的复杂结构。这里地里的筒子都是用什么方法处理的呢
project3做完,再看掉剩下的课,CS61B可以告一段落了。。
p1.JPG
p2.JPG
回复 支持 反对

使用道具 举报

Believers 发表于 2015-12-17 19:18:25 | 显示全部楼层
本帖最后由 Believers 于 2015-12-17 19:22 编辑

图的构建真的花了好久好久好久……对哈希的操作还是不够熟练。

这个project还是非常好,因为后半部分的hw和lab很少涉及到graph方面的知识,通过这个project可以说是对所有的知识都进行了复习。
只剩一个hw10了!!!!!!

part1

part1

part2

part2
回复 支持 反对

使用道具 举报

lqwandyy 发表于 2015-12-18 21:23:43 | 显示全部楼层
我有很大一个疑问就是,怎么构建这个哈希表? key就是外面的节点,value就是里面的节点?然后如何输出外面的节点(从里面的这个链表出发)??
回复 支持 反对

使用道具 举报

Believers 发表于 2015-12-18 21:50:54 | 显示全部楼层
lqwandyy 发表于 2015-12-18 21:23
我有很大一个疑问就是,怎么构建这个哈希表? key就是外面的节点,value就是里面的节点?然后如何输出外面 ...

我是这样想的,vertex的DList里有DListNode,它的item field指向一个自己定义的VertexNode(内部点),这个Node也有一个item field指向外部点。哈希表的value我指向了DListNode。也不知道算不算符合要求。
回复 支持 反对

使用道具 举报

lqwandyy 发表于 2015-12-19 15:45:35 | 显示全部楼层
由于之前的一个BUG没有发现,导致第一部分就花了很长时间。。。终于弄好了。
proj3-1.jpg
回复 支持 反对

使用道具 举报

hypsm 发表于 2016-2-6 18:09:19 | 显示全部楼层
请教一下Project3的代码量大概有多少? 不知道3天能不能搞定... (Project1 大概花了1天的时间)
回复 支持 反对

使用道具 举报

sunnysun18 发表于 2016-5-15 11:23:45 | 显示全部楼层
project 3差不多花了一天半的时间。。。
1.png
2.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

elyn 发表于 2016-5-24 23:48:25 | 显示全部楼层
快哭了,花了三天时间。。。。。。。。。。。。。。。。。
终于把CS61B刷完了
更多图片 小图 大图
组图打开中,请稍候......

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

farewell 发表于 2016-8-27 18:47:33 | 显示全部楼层
花了好久终于做完了,很多东西其实都没能好好掌握,做这个project感觉把所有知识都梳理起来了,赶紧结束CS61B课程,还有一个月就开学了,得要抓紧了,不然真找不到实习了呜呜呜第一部分构建这个图,把顶点存入hashtable的同时还要建立一个链表,每个顶点同时还是这个顶点邻接edge链表的sentinel,edge链表中的每个元素还通过hashtable与vertexpair对应。对于任意一条边,都有对应的partner,这样在删除过程中可以方便找到另一条边。同时,为了快速找到vertex在链表中的位置,vertex数据结构中还加入了一个node
第二部分用kruskal产生最小生成树,首先产生一颗没有edge的树,以及含有每个顶点的disjoint set,将edge的weight用homework8中的quicksort排序,对于每个顶点,通过hashtable找到这个点在disjoint set中的标号,如果不在一个set里就union,这里吸取homework9的教训,find以后得到的是root值,在union时候必须用这个root值。
project3_1.png
project3_2.png

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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