Berkeley CS 61B Data Structures(in Java) lab13

Sophia_Z 发表于 2016-6-17 15:28
被发现了。。。我用了一个boolean记录是否全部遍历过。。。好蛋疼的。。把BFS改了一下。。话说 ...

好囧，原来我的算法也用一重循环就可以了。
把每个点当做开始点BFS，把第N层的点作为结束点，更新到新的G里面就可以了，，，哈哈哈，也不知道当初为什么用了两重循环

做完了~开心~来这里打卡

马上就要完成61B了，开心!

这道题目粗看不难，但是readme.pdf中有几句提示值得玩味：
Try to think of the fastest, simplest code for length2Paths(). It's possible to do it with a relatively simple triply-nested loop.  ... If your TA thinks your algorithm is too slow, you'll be asked to do it again.
那么问题来了，how to define fastest, simplest code?
我用两种不同的思路来解决这个问题：
（１）use a triply-nested loop with modification.
   INSTEAD OF:

1. for( int u = 0; u < vertices; u++){
   
2.             for(int v = 0; v < vertices; v++) {
   
3.                          for(int w = 0; w < vertices; w++){
   
4.               // set newGraph.adjMatrix[][].

复制代码

The running time is O(n^3). Thus, we need to improve the performance.
IMPROVEMENT:

1. //STEP 1: loop through the adjMatrix to determine the degree of each vertex, O(n^2).
   
2. //STEP 2:  loop through the adjMatrix to form the incidentEdges for each vertex, O(n^2). (NOTE: incidentEdges[i].length == degree(i)  => save memory.)
   
3. //STEP 3:
   
4.                    for(int u = 0; u < vertices; u++) {
   
5.                          for(int v : incidentEdges[u]) {
   
6.                                for(int w : incidentEdges[v]){
   
7.                                // set newGraph.adjMatrix[][].
   

复制代码

The running time is O(n^2 + n * max(degree(i))^2). Faster since degree(i) < n.
This implementation is much intuitive and clear.
(2) use BFS as someone suggested.
STEP1  loop through every vertex.
              STEP1.1   start BFS from this vertex.
              STEP1.2   get all vertices in the LEVEL length and set newGraph.adjMatrix.
The crux of this implementation: how to represent one vertex's LEVEL.
Originally, I used an int array to store the level info and update it according to the preceding vertex's.
However, it is WRONG. Because the same vertex can have the DIFFERENT level number and can COEXIST in the queue under certain circumstances.

For example, in the given test code, when length = 5.
Level       0     1    2    3     4     5
vertex      8->4->2->0->8->4
                   8->4->5->7
                   8->4->5->9->1->0
                   8->4->5->9->1->3
                   8->6->4->2->0->8
                   8->6->4->5->7
                   8->6->4->5->9
                   8->6->7
                   8->10->6->4->2
                   8->10->6->4->5
                   8->10->6->7     
The running time is somewhat complicated, which I am unable to give the analysis.

今天终于get到了递归的一种正确打开方式，不能去用回溯的方法理解递归（因为回溯本质上还是在一层层迭代了），而是用数学归纳法理解递归。只要base case成立（n=0，程序对n=1时成立），n=k时，对k+1也成立，那么久永远成立了。
看了楼上的，只有一句膜可以说。。。。

想要得到正确答案并不难，但是看了楼上各种分析之后感觉自己有点儿嫩了，今天晚了，明天起来看看有没有能改进的地方~

lab13 done

elyn 发表于 2016-6-17 16:22
好囧，原来我的算法也用一重循环就可以了。
把每个点当做开始点BFS，把第N层的点作为结束点，更新到新的 ...

你好 。。那个BFS怎么套进去阿。。就是怎么把老师上课的  BFS代码改一下。。。改了好久。。