How to Do a Depth First Search for a Graph

Introduction

Depth First Search is a algorithm used in graph theory for traversing or searching tree or graph data structures. The idea behind DFS is to start from a source node and explore as far as possible along each branch before backtracking. You can implement DFS using recursion or an explicit stack, and it is particularly useful in scenarios like cycle detection, topological sorting, pathfinding, and more.

How DFS Works

DFS begins at a chosen starting node and marks it as visited. It then recursively explores each unvisited neighbor. This recursive nature leads the traversal to go deep into the graph before returning to explore other branches. For undirected graphs, care must be taken to avoid revisiting nodes, and for directed graphs, the direction of edges influences the path.

DFS can be implemented for both connected and disconnected graphs. In the case of a disconnected graph, DFS must be run on all unvisited nodes to ensure every component is covered.

Java Implementation

Below is a Java implementation of DFS on an undirected graph using an adjacency list representation.

public class DFSGraph {
    private int verts;
    private List<List<Integer>> adjList;

    public DFSGraph(int vertices) {
        this.verts = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination) {
        adjList.get(source).add(destination);
        adjList.get(destination).add(source); // For undirected graph
    }

    public void dfs() {
        boolean[] visited = new boolean[verts];
        for (int i = 0; i < verts; i++) {
            if (!visited[i]) {
                dfsUtil(i, visited);
            }
        }
    }

    private void dfsUtil(int currentVertex, boolean[] visited) {
        visited[currentVertex] = true;
        System.out.print(currentVertex + " ");

        for (int neighbor : adjList.get(currentVertex)) {
            if (!visited[neighbor]) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        DFSGraph graph = new DFSGraph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);

        System.out.println("DFS traversal of the graph:");
        graph.dfs();
    }
}

Example Explanation

In the above example, a graph with 5 vertices is created. The edges are added to connect vertex 0 to 1 and 2, and vertex 1 to 3 and 4. When DFS is executed starting from vertex 0, it visits as deeply as possible before backtracking, leading to an output similar to 0 1 3 4 2, depending on the order of adjacency list elements.

Applications of DFS

DFS has wide-ranging applications such as detecting cycles in a graph, finding connected components, solving puzzles and mazes, topological sorting in directed acyclic graphs (DAGs), and network analysis. Its recursive nature also makes it an intuitive approach for problems involving exhaustive search.

Conclusion

Depth First Search is a powerful technique for exploring graphs and trees. Its simplicity and versatility make it a fundamental algorithm in computer science. Whether implemented recursively or iteratively, understanding DFS provides the foundation for solving many complex graph-related problems.

You can find the example code on Github.