Add BFS/DFS ordering to matrix graphs (TheAlgorithms#2807)

iccowan · web-flow · commit 5f424ce931a7 · 2021-11-04T12:35:52.000+02:00
diff --git a/DataStructures/Graphs/MatrixGraphs.java b/DataStructures/Graphs/MatrixGraphs.java
@@ -1,5 +1,10 @@
 package DataStructures.Graphs;
 
+import java.util.List;
+import java.util.Queue;
+import java.util.ArrayList;
+import java.util.LinkedList;
+
 public class MatrixGraphs {
 
   public static void main(String args[]) {
@@ -12,7 +17,17 @@ public static void main(String args[]) {
     graph.addEdge(3, 4);
     graph.addEdge(4, 1);
     graph.addEdge(2, 3);
+    graph.addEdge(3, 9);
+    graph.addEdge(9, 1);
+    graph.addEdge(9, 8);
+    graph.addEdge(1, 8);
+    graph.addEdge(5, 6);
+    System.out.println("The graph matrix:");
     System.out.println(graph);
+    System.out.println("Depth first order beginning at node '1':");
+    System.out.println(graph.depthFirstOrder(1));
+    System.out.println("Breadth first order beginning at node '1':");
+    System.out.println(graph.breadthFirstOrder(1));
   }
 }
 
@@ -118,6 +133,107 @@ public boolean removeEdge(int from, int to) {
     return false;
   }
 
+  /**
+   * This method returns a list of the vertices in a depth first order
+   * beginning with the specified vertex
+   *
+   * @param startVertex the vertex to begin the traversal
+   * @return the list of the ordered vertices
+   */
+  public List<Integer> depthFirstOrder(int startVertex) {
+    // If the startVertex is invalid, return an empty list
+    if (startVertex >= _numberOfVertices || startVertex < 0)
+      return new ArrayList<Integer>();
+
+    // Create an array to track the visited vertices
+    boolean[] visited = new boolean[_numberOfVertices];
+
+    // Create a list to keep track of the order of our traversal
+    ArrayList<Integer> orderList = new ArrayList<Integer>();
+
+    // Perform our DFS algorithm
+    depthFirstOrder(startVertex, visited, orderList);
+
+    return orderList;
+  }
+
+  /**
+   * Helper method for public depthFirstOrder(int) that will perform
+   * a depth first traversal recursively on the graph
+   *
+   * @param currentVertex the currently exploring vertex
+   * @param visited the array of values denoting whether or not that vertex has been visited
+   * @param orderList the list to add vertices to as they are visited
+   */
+  private void depthFirstOrder(int currentVertex, boolean[] visited, List<Integer> orderList) {
+    // If this vertex has already been visited, do nothing and return
+    if (visited[currentVertex])
+      return;
+
+    // Visit the currentVertex by marking it as visited and adding it
+    // to the orderList
+    visited[currentVertex] = true;
+    orderList.add(currentVertex);
+
+    // Get the adjacency array for this vertex
+    int[] adjacent = _adjacency[currentVertex];
+    for (int i = 0; i < adjacent.length; i++)
+      // If an edge exists between the currentVertex and the vertex
+      // we are considering exploring, recurse on it
+      if (adjacent[i] == AdjacencyMatrixGraph.EDGE_EXIST)
+        depthFirstOrder(i, visited, orderList);
+  }
+
+  /**
+   * This method returns a list of the vertices in a breadth first order
+   * beginning with the specified vertex
+   *
+   * @param startVertex the vertext to begin the traversal
+   * @return the list of the ordered vertices
+   */
+  public List<Integer> breadthFirstOrder(int startVertex) {
+    // If the specified startVertex is invalid, return an empty list
+    if (startVertex >= _numberOfVertices || startVertex < 0)
+        return new ArrayList<Integer>();
+
+    // Create an array to keep track of the visited vertices
+    boolean[] visited = new boolean[_numberOfVertices];
+
+    // Create a list to keep track of the ordered vertices
+    ArrayList<Integer> orderList = new ArrayList<Integer>();
+
+    // Create a queue for our BFS algorithm and add the startVertex
+    // to the queue
+    Queue<Integer> queue = new LinkedList<Integer>();
+    queue.add(startVertex);
+
+    // Continue until the queue is empty
+    while (! queue.isEmpty()) {
+      // Remove the first vertex in the queue
+      int currentVertex = queue.poll();
+
+      // If we've visited this vertex, skip it
+      if (visited[currentVertex])
+        continue;
+
+      // We now visit this vertex by adding it to the orderList and
+      // marking it as visited
+      orderList.add(currentVertex);
+      visited[currentVertex] = true;
+
+      // Get the adjacency array for the currentVertex and 
+      // check each node
+      int[] adjacent = _adjacency[currentVertex];
+      for (int vertex = 0; vertex < adjacent.length; vertex++)
+        // If an edge exists between the current vertex and the
+        // vertex we are considering exploring, we add it to the queue
+        if (adjacent[vertex] == AdjacencyMatrixGraph.EDGE_EXIST)
+          queue.add(vertex);
+    }
+
+    return orderList;
+  }
+
   /**
    * this gives a list of vertices in the graph and their adjacencies
    *
