Breadth First Search & Depth First Search

Graph Traversal algorithms are used to visit nodes in a graph. The two most common are BFS and DFS.

Breadth First Search (BFS)

BFS explores the graph layer by layer, sweeping outwards from the starting node. It uses a Queue data structure.

• Time Complexity: O(V + E)
• Space Complexity: O(V)

BFS Java Implementation

import java.util.*;

public class GraphBFS {
    private LinkedList<Integer> adj[];

    public GraphBFS(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w); // Directed graph
    }

    void BFS(int s, int totalVertices) {
        boolean visited[] = new boolean[totalVertices];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
}

Depth First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a Stack data structure (often implicitly via Recursion).

• Time Complexity: O(V + E)
• Space Complexity: O(V)

DFS Java Implementation

import java.util.*;

public class GraphDFS {
    private LinkedList<Integer> adj[];

    public GraphDFS(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                DFSUtil(n, visited);
            }
        }
    }

    void DFS(int v, int totalVertices) {
        boolean visited[] = new boolean[totalVertices];
        DFSUtil(v, visited);
    }
}