Berkeley CS 61B Data Structures(in Java) lab13

没有找到lab13的帖子，于是自己发一个。比较简单。

这道题目粗看不难，但是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.

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.”

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

想问一下~~~楼主用的是什么样的算法哇~

交作业。最难的部分竟是理解题意，一直以为if and only if 表示仅仅的意思，但是在这道题里面意思竟然是只要的意思 = =？？囧

veralavander 发表于 2016-5-14 00:20
想问一下~~~楼主用的是什么样的算法哇~

我用的两重循环内嵌广度优先搜索

elyn 发表于 2016-5-20 16:13
我用的两重循环内嵌广度优先搜索

所以你是用BFS遍历两遍吗？
我也是用了BFS，但是遍历一遍，起始点我随机生成。然后想问一下你是怎么解决点不完全connected的情况。
比如假如我从第8个点开始进行BFS（题目给的第8行是空，第8个点没有任何chidren结点），那么BFS第一个步骤，enqueue(8)之后进入的那个循环dequeue(8)就会出现队列为空而跳出循环的情况，这样除了第8个点之外的点都没有visited

Sophia_Z 发表于 2016-6-16 18:48
所以你是用BFS遍历两遍吗？
我也是用了BFS，但是遍历一遍，起始点我随机生成。然后想问一下你是怎么解决 ...

我没有看太明白你这个算法。。
我用的是两重循环需要遍历所有点，目前也没有想到更好的办法
第一重是check所有开始点，第二重是check所有结束点。
中间套的是BFS。

Sophia_Z 发表于 2016-6-16 18:48
所以你是用BFS遍历两遍吗？
我也是用了BFS，但是遍历一遍，起始点我随机生成。然后想问一下你是怎么解决 ...

我想了下你的算法，如果只用BFS遍历，可以处理的话，解决完全不连接的点，估计还是需要套一重循环去check所有的点是不是有被处理过？

elyn 发表于 2016-6-17 13:27
我想了下你的算法，如果只用BFS遍历，可以处理的话，解决完全不连接的点，估计还是需要套一重循环去check ...

被发现了。。。我用了一个boolean记录是否全部遍历过。。。好蛋疼的。。把BFS改了一下。。话说你说的check所有开始点和结束点的意思是 每个点都作为开始点 操作一次吗？我有点没明白

是的，第一重循环把每个点作为开始点进行BFS处理，然后第二重循环做为结束点check每个点是不是满足条件。

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

是的，第一重循环把每个点作为开始点进行BFS处理，然后第二重循环做为结束点check每个点是不是满足条件