find all paths of graph (examplehub#132)

realDuYuanChao · github-actions · web-flow · commit f7ec0defa5cb · 2021-07-07T20:01:54.000+08:00
* find all path of graph

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/images/adjacency_matrix_graph.jpeg b/images/adjacency_matrix_graph.jpeg
diff --git a/src/main/java/com/examplehub/datastructures/graph/AdjacencyMatrix.java b/src/main/java/com/examplehub/datastructures/graph/AdjacencyMatrix.java
@@ -1,5 +1,8 @@
 package com.examplehub.datastructures.graph;
 
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Stack;
 import java.util.StringJoiner;
 
 public class AdjacencyMatrix<E> {
@@ -57,4 +60,49 @@ public String dfsPath() {
     }
     return dfsPath.toString();
   }
+
+  List<String> findAllPath(E startVertex, E endVertex) {
+    int start = -1;
+    int end = -1;
+    for (int i = 0; i < numOfVertex; ++i) {
+      if (startVertex == vertex[i]) {
+        start = i;
+      }
+      if (endVertex == vertex[i]) {
+        end = i;
+      }
+    }
+    return (start == -1 || end == -1) ? null : findAllPath(start, end);
+  }
+
+  private List<String> findAllPath(int start, int end) {
+    List<String> allPath = new ArrayList<>();
+    Stack<E> stack = new Stack<>();
+    boolean[] visited = new boolean[vertex.length];
+    doFindAllPath(allPath, stack, visited, start, end);
+    return allPath;
+  }
+
+  void doFindAllPath(List<String> allPath, Stack<E> stack, boolean[] visited, int start, int end) {
+    stack.push(vertex[start]);
+    visited[start] = true;
+    if (start == end) {
+      StringJoiner joiner = new StringJoiner("->");
+      for (E item : stack) {
+        joiner.add(item.toString());
+      }
+      allPath.add(joiner.toString());
+      stack.pop();
+      visited[start] = false;
+      return;
+    }
+
+    for (int i = 0; i < numOfVertex; ++i) {
+      if (adj[start][i] == 1 && !visited[i]) {
+        doFindAllPath(allPath, stack, visited, i, end);
+      }
+    }
+    stack.pop();
+    visited[start] = false;
+  }
 }
diff --git a/src/test/java/com/examplehub/datastructures/graph/AdjacencyMatrixTest.java b/src/test/java/com/examplehub/datastructures/graph/AdjacencyMatrixTest.java
@@ -48,4 +48,22 @@ void testGetVertexDegree() {
     assertEquals(4, adjacencyMatrix.getVertexDegree("D"));
     assertEquals(2, adjacencyMatrix.getVertexDegree("E"));
   }
+
+  @Test
+  void testFindAllPath() {
+    String[] vertex = {"A", "B", "C", "D", "E"};
+    AdjacencyMatrix<String> adjacencyMatrix = new AdjacencyMatrix<>(vertex);
+    adjacencyMatrix.addEdge(0, 1); /* A - B */
+    adjacencyMatrix.addEdge(0, 2); /* A - C */
+    adjacencyMatrix.addEdge(0, 3); /* A - D */
+    adjacencyMatrix.addEdge(1, 3); /* B - D */
+    adjacencyMatrix.addEdge(2, 3); /* C - D */
+    adjacencyMatrix.addEdge(1, 4); /* B - E */
+    adjacencyMatrix.addEdge(3, 4); /* D - E */
+    assertEquals(
+        "A->B->D->E, A->B->E, A->C->D->B->E, A->C->D->E, A->D->B->E, A->D->E",
+        String.join(", ", adjacencyMatrix.findAllPath("A", "E")));
+
+    assertNull(adjacencyMatrix.findAllPath("A", "F"));
+  }
 }
