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

好像还没有帖子.

附上截图：

【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实现最方便。

花了好久终于做完了，很多东西其实都没能好好掌握，做这个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!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可以告一段落了。。

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

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

我有很大一个疑问就是，怎么构建这个哈希表？ key就是外面的节点，value就是里面的节点？然后如何输出外面的节点（从里面的这个链表出发）？？

lqwandyy 发表于 2015-12-18 21:23
我有很大一个疑问就是，怎么构建这个哈希表？ key就是外面的节点，value就是里面的节点？然后如何输出外面 ...

我是这样想的，vertex的DList里有DListNode，它的item field指向一个自己定义的VertexNode（内部点），这个Node也有一个item field指向外部点。哈希表的value我指向了DListNode。也不知道算不算符合要求。

由于之前的一个BUG没有发现，导致第一部分就花了很长时间。。。终于弄好了。

请教一下Project3的代码量大概有多少？ 不知道3天能不能搞定... （Project1 大概花了1天的时间）

project 3差不多花了一天半的时间。。。

快哭了，花了三天时间。。。。。。。。。。。。。。。。。
终于把CS61B刷完了