Berkeley CS 61B Data Structures(in Java) lab13

自己做完 再看看上面的讨论 感觉自己弱爆了。。。。快结课了。。还是好弱。。加油！！

楼上讨论的BFS之类的好高大上，我感觉自己好low… 只会用几个嵌套loop，而且连recursion也用得不利索。。T_T
回头又看了一下老师的BFS笔记，里面用到了queue，但是这里也没有implement queque，我们要怎么实现BFS呢？ 找github代码也没找到有用的。还望大神解答~

lab13已完成~

感觉自己还是有点菜啊，partI只会那种三重循环的。。。part2的话根据readme.pdf的提示用到了recursion，但是感觉效率也很低，有没有大佬指点一下如何优化，首页的思路没看懂。

附上截图：

part2的思想和part1类似，只是加上了recursion。因此每个迭代的level就是一个BFS的level。但是和lecture28中的BFS实现不一样，DFS才需要使用迭代，而BFS一般用while循环配合queue，然后loop每个刚标为visited的vertices。这里不需要while和queue，而且是无向图，只需要recurse length即可。
个人认为是recursion部分值得学习，利用的精华在于：public UDGraph paths(int length)的返回值是UDGraph itself
所以我们可以应用path方法的返回值（UDGraph类）的方法进行迭代，迭代至length=2，就可以使用part I中的 length2Paths()方法了。

1. paths(length-1).hasEdge(i, j)

复制代码

忽略了它的返回值，导致想了半天
它的return值 若某两点（i和j）之间有edge的话，edge的长度为length-1，我们再用part I的办法判断j和所有的vertices k 比较就能得出length为“length”的edge（i和k）了

另外想知道part I有什么更好的loop方法，目前只能想到三层的loop！

1.   public UDGraph length2Paths() {
   
2.     UDGraph newGraph = new UDGraph(vertices);
   
3.     // Put your answer to Part I here.
   
4.     for (int i = 0; i<vertices ; i++ ) {
   
5.       for (int j = 0; j<vertices; j++ ) {
   
6.         if (hasEdge(i,j)) {
   
7.           for (int k = 0; k<vertices ; k++ ) {
   
8.             if (hasEdge(j,k)) {
   
9.               newGraph.addEdge(i,k);
   
10.             }
    
11.           }
    
12.         }
    
13.       }
    
14.     }
    
15.     return newGraph;
    
16.   }

复制代码

这是我part1代码，应该是readme中说的，“It's possible
to do it with a relatively simple triply-nested loop.”

各位同学还有更快的算法吗，