Chapter 07 section 07 new test case added. Java BFS bug fixed.

liuyubobobo · liuyubobobo · commit c126be773bc9 · 2018-05-01T14:57:28.000+08:00
diff --git a/07-Graph-Basics/Course Code (C++)/07-BFS-and-Shortest-Path/main.cpp b/07-Graph-Basics/Course Code (C++)/07-BFS-and-Shortest-Path/main.cpp
@@ -14,17 +14,33 @@ int main() {
     SparseGraph g = SparseGraph(7, false);
     ReadGraph<SparseGraph> readGraph(g, filename);
     g.show();
-    cout<<endl;
 
     // 比较使用深度优先遍历和广度优先遍历获得路径的不同
     // 广度优先遍历获得的是无权图的最短路径
     Path<SparseGraph> dfs(g,0);
-    cout<<"DFS : ";
+    cout << "DFS : ";
     dfs.showPath(6);
 
     ShortestPath<SparseGraph> bfs(g,0);
-    cout<<"BFS : ";
+    cout << "BFS : ";
     bfs.showPath(6);
 
+    cout << endl;
+
+    filename = "testG1.txt";
+    SparseGraph g2 = SparseGraph(13, false);
+    ReadGraph<SparseGraph> readGraph2(g2, filename);
+    g2.show();
+
+    // 比较使用深度优先遍历和广度优先遍历获得路径的不同
+    // 广度优先遍历获得的是无权图的最短路径
+    Path<SparseGraph> dfs2(g2,0);
+    cout << "DFS : ";
+    dfs2.showPath(3);
+
+    ShortestPath<SparseGraph> bfs2(g,0);
+    cout << "BFS : ";
+    bfs2.showPath(3);
+
     return 0;
 }
diff --git a/07-Graph-Basics/Course Code (C++)/07-BFS-and-Shortest-Path/testG1.txt b/07-Graph-Basics/Course Code (C++)/07-BFS-and-Shortest-Path/testG1.txt
@@ -0,0 +1,14 @@
+13 13
+0 5
+4 3
+0 1
+9 12
+6 4
+5 4
+0 2
+11 12
+9 10
+0 6
+7 8
+9 11
+5 3
diff --git a/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/src/bobo/algo/Main.java b/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/src/bobo/algo/Main.java
@@ -9,7 +9,6 @@ public static void main(String[] args) {
         SparseGraph g = new SparseGraph(7, false);
         ReadGraph readGraph = new ReadGraph(g, filename);
         g.show();
-        System.out.println();
 
         // 比较使用深度优先遍历和广度优先遍历获得路径的不同
         // 广度优先遍历获得的是无权图的最短路径
@@ -20,5 +19,22 @@ public static void main(String[] args) {
         ShortestPath bfs = new ShortestPath(g,0);
         System.out.print("BFS : ");
         bfs.showPath(6);
+
+        System.out.println();
+
+        filename = "testG1.txt";
+        SparseGraph g2 = new SparseGraph(13, false);
+        ReadGraph readGraph2 = new ReadGraph(g2, filename);
+        g2.show();
+
+        // 比较使用深度优先遍历和广度优先遍历获得路径的不同
+        // 广度优先遍历获得的是无权图的最短路径
+        Path dfs2 = new Path(g2,0);
+        System.out.print("DFS : ");
+        dfs2.showPath(3);
+
+        ShortestPath bfs2 = new ShortestPath(g,0);
+        System.out.print("BFS : ");
+        bfs.showPath(3);
     }
 }
diff --git a/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/src/bobo/algo/ShortestPath.java b/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/src/bobo/algo/ShortestPath.java
@@ -3,6 +3,7 @@
 import java.util.Vector;
 import java.util.Stack;
 import java.util.LinkedList;
+import java.util.Queue;
 
 public class ShortestPath {
 
@@ -31,16 +32,16 @@ public ShortestPath(Graph graph, int s){
         this.s = s;
 
         // 无向图最短路径算法, 从s开始广度优先遍历整张图
-        LinkedList<Integer> q = new LinkedList<Integer>();
+        Queue<Integer> q = new LinkedList<Integer>();
 
-        q.push( s );
+        q.add(s);
         visited[s] = true;
         ord[s] = 0;
         while( !q.isEmpty() ){
-            int v = q.pop();
+            int v = q.remove();
             for( int i : G.adj(v) )
                 if( !visited[i] ){
-                    q.push(i);
+                    q.add(i);
                     visited[i] = true;
                     from[i] = v;
                     ord[i] = ord[v] + 1;
diff --git a/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/testG1.txt b/07-Graph-Basics/Course Code (Java)/07-BFS-and-Shortest-Path/testG1.txt
@@ -0,0 +1,14 @@
+13 13
+0 5
+4 3
+0 1
+9 12
+6 4
+5 4
+0 2
+11 12
+9 10
+0 6
+7 8
+9 11
+5 3

-Original file line number
+Diff line change
@@ @@ -0,0 +1,14 @@ @@
 +13 13
 +0 5
 +4 3
 +0 1
 +9 12
 +6 4
 +5 4
 +0 2
 +11 12
 +9 10
 +0 6
 +7 8
 +9 11
 +5 3