Many problems in coding tests are based on graph or tree structures. One of the algorithms that is useful in solving these problems is Depth-First Search (DFS). In this tutorial, we will learn about the concept of DFS and how to implement it in Java.
1. What is Depth-First Search (DFS)?
Depth-First Search is a type of graph traversal algorithm that explores nodes as deeply as possible along each branch before backtracking. In other words, it keeps moving down one branch until no further progress can be made, at which point it backtracks to the previous node and explores other branches.
2. Characteristics of DFS
- Uses a stack to keep track of visited nodes.
- Can be implemented through recursion.
- Unlike Breadth-First Search (BFS), it primarily considers the depth of nodes or the path.
3. Problem Definition
Let us assume there is a graph as follows:
A
/ \
B C
/ \ \
D E F
We aim to find the path from A to D using DFS. The goal is to find the path and print the nodes visited from A to D.
4. Problem-Solving Process
To solve the problem using DFS, we first need to represent the graph and then implement the DFS algorithm.
4.1 Graph Representation
Graphs can usually be represented by an adjacency list or an adjacency matrix. Here, we will represent the graph using an adjacency list.
Implementing the Graph in Java
import java.util.*;
class Graph {
private Map> adjacencyList;
public Graph() {
adjacencyList = new HashMap<>();
}
public void addEdge(String source, String destination) {
adjacencyList.putIfAbsent(source, new ArrayList<>());
adjacencyList.get(source).add(destination);
}
public Map> getAdjacencyList() {
return adjacencyList;
}
}
4.2 Implementing the DFS Algorithm
The DFS algorithm can be implemented as follows. A Set is used to keep track of visited nodes, and depth exploration is performed through recursive calls.
Java DFS Method
class DFS {
private Set visited;
private List path;
public DFS() {
visited = new HashSet<>();
path = new ArrayList<>();
}
public void depthFirstSearch(Graph graph, String node) {
if (!visited.contains(node)) {
visited.add(node);
path.add(node);
for (String neighbor : graph.getAdjacencyList().get(node)) {
depthFirstSearch(graph, neighbor);
}
}
}
public List getPath() {
return path;
}
}
5. Complete Code
Now, let’s combine the complete code for use. Below is the complete code that creates the graph and executes DFS.
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
DFS dfs = new DFS();
dfs.depthFirstSearch(graph, "A");
System.out.println("DFS Path: " + dfs.getPath());
}
}
6. Code Execution Result
When you run the above code, you can obtain the following result:
DFS Path: [A, B, D, E, C, F]
As can be seen from the result, DFS starts from A, visits B, and then goes deep to D. The order of exploration in DFS is maintained.
7. Advanced Learning
This tutorial introduced the concept of DFS and basic implementation methods. It is advisable to solve various problems using DFS to build your skills. Typical problems include:
- Maze solving
- Finding connected components
- Cycle detection
8. Conclusion
Through this tutorial, we learned the basic concept of Depth-First Search and how to implement it in Java. Graph problems frequently appear in coding tests, so it is essential to memorize and practice them. In the next tutorial, we will discuss another search algorithm, Breadth-First Search (BFS).