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

断断续续花了2天写完proj3，是个很好的Project，第一问内容涵盖了LinkedList, graph, hashTable。一开始没有看到有个建议的data structure图例，自己写的乱七八糟，之后根据图例中的框架搭，思路清楚地多。Vertex和Edge各有一个hashTable,方便根据hashCode直接查找AdjacencyList中对应的vertex/edge,以便add/remove等操作。我在vertexPair原有的class中直接加入了weight和partner，不容易搞乱。
第二问自己建了个edge的class，里面implement了comparable interface,就可以偷懒直接用java自带的sorting了。之后把vertex用hashCode() map到disjoint set中按edge已经理好的顺序addEdge()就好。总的来说第一问比第二问麻烦的多，但按照给的图例写结构的话思路不会太乱。
至此终于结束61B了，真的是好课，推荐给所有初学java的同学。

Part I里面我用的是方法(iii)，跟大部分的人不太一样。主要要弄清一共有多少个数据结构(2 x hashtable, 2 x linkedlist)，数据结构里面分别存的是什么。我的hashtable可以extend和shrink。

61B终于学完啦！还是很开心的！所有的hw，lab（除了14年的lab15）都写完了，proj做了1和3。2的话任务量感觉太大了，确实很难，只好放弃了。

十分不愉快的coding过程，其实只完成了part1，part2的时候，我特么新建一个WUGraph对象，竟然对当做参数传进来的WUGraph g有影响，已经无语了，是在不想花这么多时间去找这个小失误在哪，已经尽力了，我的kurskal算法和github上的人几乎一模一样，就是结构上面出了错，不管了，结课。

CS61B完结~

俘虏你的心 发表于 2017-3-26 14:00
Part I里面我用的是方法(iii)，跟大部分的人不太一样。主要要弄清一共有多少个数据结构(2 x hashtable, 2 x ...

您好，请问您有github上传代码吗，我想要参考一下您的，我的思路也是这样，但是代码一直有个bug没解决

终于艰难地做完了pj3，cs61b差不多要告一段落了！！
看着别人的code写还是debug了两天，各种错误的bug，第一天有一个小bug一直找不到！！第二天才发现是自己重写hashtable的时候出了问题！！
太多的坑要填了，写到了后面，前面的有些东西都有点生疏忘了。。。

重点：耐心debug！把整个类所有存储数据的方式搞明白！自己写的hashtable注意要测试好，在hw6有某个同学的测试代码，可以参考一下！

elyn 发表于 2016-5-24 23:48
快哭了，花了三天时间。。。。。。。。。。。。。。。。。
终于把CS61B刷完了

三天就刷完了？真厉害啊！

附上截图：

【part 1】：生成一个Weighted Undirected Graph
重点在于理解搞这么复杂数据结构的意义，是为了保证时间复杂度在一定范围内，只要理解了数据结构。其实现就不难。
对于实现你需要进行Augmenting Data Structure，满足readme中的reference指向。例如EdgeNode中新加的Vertex1和Vertex2 这两个field指向这个edge的两端的Vertex的Node；或是VertexList中node的指向VertexInApp的reference，还需加上它们的getter和setter。如图是我加的一些笔记：（V是Vertex的缩写）

因为利用了homework05中的链表（DList和DListNode），上面的Augment是写在了它的父类（ListNode）中。

【part 2】：利用Kruskal算法求最小生成树（Minimum Spanning Tree）
因为VertexPair类是protected的，不能被package外引用。所以我自己写了个myPair类，里面维护着vertex1 vertex2和weight三个field。
其次利用了homework08中的QuickSort算法，将myPair enqueue到LinkedQueue中，进行quicksort，因为quicksort是compare-based的算法，所以myPair类的签名需要implement Comparable，并override compareto算法（只compare里面的weight即可）。
最后一部分是利用并查集（DisjointSet）来实现，和homework09一样，find两个vertex，如果他们的parent不是同一个，说明不在同一个set里，两个vertex增加edge，因为是edge weight从小到大进行判断，所以保证了生成的树为最小。还有一个问题在于Vertex 类是object，并查集是通过Array实现的，所以需要将每个Vertex映射（map）一个独一无二的int，最好的办法是通过Dictionary（key+value），字典通过HashTable实现最方便。