Depth First Search (DFS) in Java

Depth First Search (DFS) is a type of algorithm used to traverse the nodes of a graph or a tree. It is a popular algorithm used to search trees and graphs, and is commonly used in computer science and mathematics. Depth First Search is an algorithm that starts at the root node and explores as far as possible along each branch before backtracking. It is used to find paths from a start node to a goal node in a graph or a tree.

In this article, we will discuss the Depth First Search algorithm in detail and its time and space complexity. We will also discuss the DFS algorithm in the context of the Java programming language and provide code examples throughout the article.

How Does the Algorithm Work?

Depth First Search is a recursive algorithm that follows a specific set of steps to traverse the nodes of a graph or a tree. It starts at the root node and explores as far as possible along each branch before backtracking.

The basic idea behind the Depth First Search algorithm is that it traverses the graph or tree in a depth-first manner. It starts at the root node and explores as far as possible down each branch before backtracking. It then moves to the next branch, and continues this process until it finds the goal node.

The following is an example of the Depth First Search algorithm in action:

Let’s say we have a graph with the following structure

A-B-C
|
D-E

We start at the node A and explore as far as possible along each branch. We start by exploring node B, then C, and then backtrack to node A. We then explore node D and then node E. We can then stop the algorithm since we have found our goal node.

Time Complexity

The time complexity of the Depth First Search algorithm depends on the number of nodes and edges in the graph or tree. The best case time complexity of Depth First Search is O(V+E), where V is the number of nodes and E is the number of edges. The average case time complexity of Depth First Search is also O(V+E). The worst case time complexity of Depth First Search is O(V^2), where V is the number of nodes.

Space Complexity

The space complexity of the Depth First Search algorithm is O(V), where V is the number of nodes.

Depth First Search in Java

Now that we have discussed the basics of the Depth First Search algorithm, let’s look at how it can be implemented in the Java programming language.

We will start by creating a Graph class that will represent our graph. We will create a private Node class that will represent a node in the graph. The Node class will have two instance variables: a String value and a List of Node objects that will represent the edges of the graph. We will also create a constructor that takes in a String value and a List of Node objects.

public class Graph {
  
    private class Node {
        String value;
        List<Node> edges;
 
        public Node(String value, List<Node> edges) {
            this.value = value;
            this.edges = edges;
        }
    }
}

Next, we will create a DepthFirstSearch method that will take in a Node object as a parameter. This method will be recursive and will traverse the graph in a depth-first manner. We will also create a List of Node objects to keep track of the nodes that have been visited.

public void DepthFirstSearch(Node node) {
 
  // Create a List of Node objects to keep track of the nodes that have been visited.
  List<Node> visited = new ArrayList<>();
 
  // Call the recursive DFS helper method.
  DFSHelper(node, visited);
}

Next, we will create a DFSHelper method that will take in a Node object and a List of Node objects as parameters. This method will be recursive and will traverse the graph in a depth-first manner.

public void DFSHelper(Node node, List<Node> visited) {
 
  // Add the current node to the visited list.
  visited.add(node);
 
  // Print out the value of the current node.
  System.out.println(node.value);
 
  // Loop through the edges of the current node.
  for (Node edge : node.edges) {
    // Check if the edge has been visited.
    if (!visited.contains(edge)) {
      // If it has not been visited, call the DFS helper method on the edge.
      DFSHelper(edge, visited);
    }
  }
}

Conclusion

In this article, we discussed the Depth First Search (DFS) algorithm in detail. We discussed how the algorithm works, its time complexity, and its space complexity. We also discussed the DFS algorithm in the context of the Java programming language and provided code examples throughout the article.

Exercises

public void DepthFirstSearch(Node node) {
 
  List<Node> visited = new ArrayList<>();
 
  DFSHelper(node, visited);
}

public void DFSHelper(Node node, List<Node> visited) {
 
  visited.add(node);
 
  System.out.println(node.value);
 
  for (Node edge : node.edges) {
    if (!visited.contains(edge)) {
      DFSHelper(edge, visited);
    }
  }
}

public void DepthFirstSearch(Node node) {
 
  List<Node> visited = new ArrayList<>();
 
  DFSHelper(node, visited);
}

public void DFSHelper(Node node, List<Node> visited) {
 
  visited.add(node);
 
  System.out.println(node.value);
 
  for (Node edge : node.edges) {
    if (!visited.contains(edge)) {
      DFSHelper(edge, visited);
    }
  }
}

public void DepthFirstSearch(Node node) {
 
  List<Node> visited = new ArrayList<>();
 
  DFSHelper(node, visited);
}

public void DFSHelper(Node node, List<Node> visited) {
 
  visited.add(node);
 
  System.out.println(node.value);
 
  for (Node edge : node.edges) {
    if (!visited.contains(edge)) {
      DFSHelper(edge, visited);
    }
  }
}

public void DepthFirstSearch(Node node) {
 
  List<Node> visited = new ArrayList<>();
 
  DFSHelper(node, visited);
}

public void DFSHelper(Node node, List<Node> visited) {
 
  visited.add(node);
 
  System.out.println(node.value);
 
  for (Node edge : node.edges) {
    if (!visited.contains(edge)) {
      DFSHelper(edge, visited);
    }
  }
}

public void DepthFirstSearch(Node node) {
 
  List<Node> visited = new ArrayList<>();
 
  DFSHelper(node, visited);
}

public void DFSHelper(Node node, List<Node> visited) {
 
  visited.add(node);
 
  System.out.println(node.value);
 
  for (Node edge : node.edges) {
    if (!visited.contains(edge)) {
      DFSHelper(edge, visited);
    }
  }
}