Depth-First Search (DFS) – Graph Search Algorithms

DFS (Depth First Search) is an algorithm used to traverse a graph (or tree) by starting at a given vertex and moving as far as possible along one path before backtracking to explore other paths. It is widely used for tasks such as full graph traversal, path existence checks, and connected component detection.

---

2. Basic Concept

1. Start at a Vertex
   • Mark the starting vertex as visited (e.g., using a visited array or set).
2. Go Deeper
   • Move to an unvisited adjacent vertex and continue going deeper into the graph.
3. Backtrack
   • When no further unvisited vertices are reachable, return to the previous vertex and explore a different route if available.

---

3. Time Complexity

• With an adjacency list representation of a graph with V vertices and E edges:
  • Time Complexity: O(V + E).
• With an adjacency matrix, it can be O(V^2) because you might check all possible vertices from each vertex.

---

4. DFS Code Example (Java)

Below is a simple example using an adjacency list and a recursive DFS approach in Java.

4.1 Source Code

import java.util.ArrayList;
import java.util.List;

public class DFSExample {
    private List<List<Integer>> graph; // Adjacency list
    private boolean[] visited;

    public DFSExample(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        visited = new boolean[n];
    }

    // Add an undirected edge
    public void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }

    public void dfs(int current) {
        visited[current] = true;
        System.out.print(current + " ");

        for (int next : graph.get(current)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

    // Reset the visited array for another DFS run
    public void resetVisited() {
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }
    }
}

4.2 Test Code

public class DFSTest {
    public static void main(String[] args) {
        // Create a graph with 6 vertices (0 ~ 5)
        DFSExample dfsGraph = new DFSExample(6);

        // Add undirected edges
        dfsGraph.addEdge(0, 1);
        dfsGraph.addEdge(0, 2);
        dfsGraph.addEdge(1, 3);
        dfsGraph.addEdge(2, 4);
        dfsGraph.addEdge(2, 5);

        System.out.println("DFS start (from vertex 0):");
        dfsGraph.dfs(0);
        // Possible output (depending on adjacency order): 0 1 3 2 4 5

        // Reset visited array to reuse
        dfsGraph.resetVisited();
        System.out.println("\nDFS start (from vertex 3):");
        dfsGraph.dfs(3);
    }
}

Running the above code will perform DFS starting from vertex 0 (and then from 3 after resetting), printing the visited vertices in DFS order.

---

5. DFS Code Example (Python)

Below is a similar example in Python, using a dictionary for the adjacency list and a recursive DFS function.

5.1 Source Code

class DFSExample:
    def __init__(self, n):
        # Assume vertices 0..n-1
        self.graph = {i: [] for i in range(n)}
        self.visited = [False] * n

    def add_edge(self, u, v):
        # Undirected edge: add both ways
        self.graph[u].append(v)
        self.graph[v].append(u)

    def dfs(self, current):
        self.visited[current] = True
        print(current, end=' ')

        for nxt in self.graph[current]:
            if not self.visited[nxt]:
                self.dfs(nxt)

    def reset_visited(self):
        self.visited = [False] * len(self.visited)

5.2 Test Code

def test_dfs():
    dfs_graph = DFSExample(6)
    # Add edges
    dfs_graph.add_edge(0, 1)
    dfs_graph.add_edge(0, 2)
    dfs_graph.add_edge(1, 3)
    dfs_graph.add_edge(2, 4)
    dfs_graph.add_edge(2, 5)

    print("DFS start (from vertex 0):")
    dfs_graph.dfs(0)
    # Example output: 0 1 3 2 4 5

    dfs_graph.reset_visited()
    print("\nDFS start (from vertex 3):")
    dfs_graph.dfs(3)

if __name__ == "__main__":
    test_dfs()

---

6. Use Cases

1. Connected Components
   • To find connected components in an undirected graph: for each unvisited vertex, run DFS and mark all reachable vertices as part of the same component.
2. Cycle Detection
   • During DFS, if you find an adjacent vertex that is already visited and is part of the current path, a cycle exists.
3. General Graph Traversal
   • Use DFS repeatedly for each unvisited vertex to explore the whole graph if it has multiple components.

---

7. Comparison with BFS

Aspect	DFS (Depth First Search)	BFS (Breadth First Search)
Data Structure	Stack or Recursion	Queue
Visit Order	Go deep along a path, then backtrack	Layer-by-layer from the start vertex
Typical Uses	Path exploration, backtracking, topological sort, connected components	Shortest path in unweighted graphs, level-order traversal

---

8. Conclusion

• DFS explores as far down a path as possible before backtracking, leveraging a stack or recursion to manage the process.
• Time complexity is O(V + E) with adjacency lists, and O(V^2) with adjacency matrices.
• It is widely used in graph traversal, cycle detection, connected component finding, and backtracking scenarios.