Day 24: Graph Traversal Algorithms – Mastering DFS and BFS with Real-World Examples

Graph traversal is the process of visiting all nodes in a graph. The two main algorithms for traversal are Depth-First Search (DFS) and Breadth-First Search (BFS).

1. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It can be implemented recursively or iteratively using a stack.

DFS Example in Java:

javaCopy codeimport java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    // Add edge
    public void addEdge(int node, int neighbor) {
        graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);
    }

    // DFS traversal
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

    private void dfsHelper(int node, Set<Integer> visited) {
        visited.add(node);
        System.out.print(node + " ");
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(4, 0);
        System.out.print("DFS Traversal: ");
        g.dfs(0); // Starting node
    }
}

2. Breadth-First Search (BFS)

BFS explores all neighbors of a node before visiting their neighbors, using a queue.

BFS Example in Java:

javaCopy codeimport java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> graph = new HashMap<>();

    // Add edge
    public void addEdge(int node, int neighbor) {
        graph.computeIfAbsent(node, k -> new ArrayList<>()).add(neighbor);
    }

    // BFS traversal
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");
            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(2, 3);
        g.addEdge(3, 2);
        g.addEdge(4, 0);
        System.out.print("BFS Traversal: ");
        g.bfs(0); // Starting node
    }
}