图的dfs

1054415232 · 1054415232 · commit f19e877d0b44 · 2019-03-12T00:23:42.000+08:00
diff --git a/README.md b/README.md
@@ -23,4 +23,4 @@
 ### [单链表回文](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/leetCode/Palindrome.java)
 ### [堆的实现及求一组动态数据的中位数](https://github.com/chaoaiqi/study/tree/master/java/src/juejin/lc/heap)
 ### [求一组动态数据集合的最大 Top K](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/leetCode/GetTopKArrays.java)
-### [基于无向图的bfs和dfs]()
+### [基于无向图的bfs和dfs](https://github.com/chaoaiqi/study/blob/master/java/src/juejin/lc/graph/Graph.java)
diff --git a/java/src/juejin/lc/graph/Graph.java b/java/src/juejin/lc/graph/Graph.java
@@ -21,6 +21,7 @@ public class Graph {
      *
      * @param count 数量
      */
+    @SuppressWarnings("unchecked")
     private Graph(int count) {
         this.count = count;
         adj = new LinkedList[count];
@@ -35,7 +36,7 @@ private Graph(int count) {
      * @param oSide order
      * @param rSide reversed order
      */
-    public void add(int oSide, int rSide) {
+    private void add(int oSide, int rSide) {
         adj[oSide].add(rSide);
         adj[rSide].add(oSide);
     }
@@ -63,18 +64,90 @@ private void bfs(int oSide, int rSide) {
                 int value = adj[index].get(j);
                 if (!visited[value]) {
                     prev[value] = index;
-                    if (index == rSide) {
+                    if (value == rSide) {
                         print(prev, oSide, rSide);
                     }
+                    visited[value] = true;
+                    queue.offer(value);
                 }
             }
         }
     }
 
-    private void dfs(){
+    private boolean found = false;
+    /**
+     * 深度优先搜索
+     *
+     * @param oSide 顺序边
+     * @param rSide 逆序边
+     */
+    private void dfs(int oSide, int rSide) {
+        boolean[] visited = new boolean[count];
+        int[] prev = new int[count];
+        for (int i = 0; i < count; i++) {
+            prev[i] = -1;
+        }
+        recursiveDfs(visited, prev, oSide, rSide);
+        print(prev, oSide, rSide);
+    }
+
+    /**
+     * 递归
+     *
+     * @param visited visited
+     * @param prev    prev
+     * @param oSide   顺序边
+     * @param rSide   逆序边
+     */
+    private void recursiveDfs(boolean[] visited, int[] prev, int oSide, int rSide) {
+        if (found) return;
+        visited[oSide] = true;
+        if (oSide == rSide) {
+            found = true;
+            return;
+        }
+        for (int i = 0; i < adj[oSide].size(); i++) {
+            int value = adj[oSide].get(i);
+            if (!visited[value]) {
+                prev[value] = oSide;
+                recursiveDfs(visited, prev, value, rSide);
+            }
+        }
+    }
+
+    private void createGraph() {
+        //  0 -- 1 -- 2
+        //  |    |    |
+        //  3 -- 4 -- 5
+        //  |    |    |
+        //  6 -- 7 -- 8
+        add(0,1);//add(1,0);
+        add(0,3);//add(3,0);
+
+        add(1,2);//add(2,1);
+        add(1,4);// add(4,1);
+
+        add(2,5);//add(5,2);
+
+        add(3,4);//add(4,3);
+        add(3,6);//add(6,3);
 
+        add(4,5);//add(5,4);
+        add(4,7);// add(7,4);
+
+        add(5,8);//add(8,5);
+
+        add(6,7);//add(7,6);
+
+        add(7,8);//add(8,7);
     }
 
+    /**
+     * 递归正向输出图的路径
+     * @param prev prev
+     * @param oSide 顺序边
+     * @param rSide 逆序边
+     */
     private void print(int[] prev, int oSide, int rSide) {
         if (prev[rSide] != -1 && oSide != rSide) {
             print(prev, oSide, prev[rSide]);
@@ -83,6 +156,18 @@ private void print(int[] prev, int oSide, int rSide) {
     }
 
     public static void main(String[] args) {
-
+        int count = 9;
+        Graph graph = new Graph(count);
+        //  0 -- 1 -- 2
+        //  |    |    |
+        //  3 -- 4 -- 5
+        //  |    |    |
+        //  6 -- 7 -- 8
+        graph.createGraph();
+        System.out.println("BFS(广度优先搜索)");
+        graph.bfs(0,8);
+        System.out.println();
+        System.out.println("DFS(深度优先搜索)");
+        graph.dfs(0,8);
     }
 }
