Breadth First Traversal and Depth First Traversal in Data Structure

Graph traversal is the process of visiting every vertex and edge in a graph exactly once. The two most fundamental traversal algorithms are Breadth‑First Search (BFS) and Depth‑First Search (DFS). Both are used to explore graphs, but they differ in the order they visit vertices and the data structures they rely on internally.

Breadth‑First Search (BFS)

BFS explores all neighbors of a node before moving to the next level. It uses a queue to track vertices to visit and guarantees the shortest path in unweighted graphs.

BFS Algorithm Steps

1. Start from a source vertex and mark it as visited.
2. Enqueue the source vertex.
3. While the queue is not empty:
   • Dequeue a vertex.
   • Visit all unvisited neighbors, mark them as visited, and enqueue them.

BFS Implementation in Python

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)

        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

# Example graph (adjacency list)
graph = {
    0: [1, 2],
    1: [0, 2, 3],
    2: [0, 1, 3],
    3: [1, 2]
}
print(bfs(graph, 0))  # Output: [0, 1, 2, 3]

BFS Implementation in Java

import java.util.*;

public class BFS {
    public static List bfs(Map> graph, int start) {
        Set visited = new HashSet<>();
        Queue queue = new LinkedList<>();
        List order = new ArrayList<>();

        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            order.add(vertex);

            for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Map> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2, 3));
        graph.put(2, Arrays.asList(0, 1, 3));
        graph.put(3, Arrays.asList(1, 2));

        System.out.println(bfs(graph, 0));  // [0, 1, 2, 3]
    }
}

BFS Implementation in C++

#include 
#include 
#include 
#include 
#include 
using namespace std;

vector bfs(unordered_map>& graph, int start) {
    unordered_set visited;
    queue q;
    vector order;

    visited.insert(start);
    q.push(start);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();
        order.push_back(vertex);

        for (int neighbor : graph[vertex]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
    return order;
}

int main() {
    unordered_map> graph;
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 3};
    graph[3] = {1, 2};

    vector result = bfs(graph, 0);
    for (int v : result) cout << v << " ";
    cout << endl;
    return 0;
}

Depth‑First Search (DFS)

DFS explores as far as possible along a branch before backtracking. It uses a stack (explicit or via recursion). DFS is useful for topological sorting, cycle detection, and solving puzzles.

DFS Algorithm Steps (Recursive)

1. Start from a source vertex and mark it as visited.
2. Recursively visit all unvisited neighbors of the current vertex.
3. Backtrack when no unvisited neighbors remain.

DFS Implementation in Python (Recursive)

def dfs_recursive(graph, start, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(start)
    order.append(start)

    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)

    return order

print(dfs_recursive(graph, 0))  # Output: [0, 1, 2, 3] (order may vary)

DFS Implementation in Python (Iterative)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)
            for neighbor in graph.get(vertex, []):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

print(dfs_iterative(graph, 0))  # Output: [0, 2, 3, 1] (order may vary)

DFS Implementation in Java

import java.util.*;

public class DFS {
    // Recursive DFS
    public static void dfsRecursive(Map> graph, int start,
                                     Set visited, List order) {
        visited.add(start);
        order.add(start);

        for (int neighbor : graph.getOrDefault(start, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(graph, neighbor, visited, order);
            }
        }
    }

    // Iterative DFS
    public static List dfsIterative(Map> graph, int start) {
        Set visited = new HashSet<>();
        Stack stack = new Stack<>();
        List order = new ArrayList<>();

        stack.push(start);

        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            if (!visited.contains(vertex)) {
                visited.add(vertex);
                order.add(vertex);
                for (int neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        return order;
    }

    public static void main(String[] args) {
        Map> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(0, 2, 3));
        graph.put(2, Arrays.asList(0, 1, 3));
        graph.put(3, Arrays.asList(1, 2));

        List order = new ArrayList<>();
        dfsRecursive(graph, 0, new HashSet<>(), order);
        System.out.println(order);

        System.out.println(dfsIterative(graph, 0));
    }
}

DFS Implementation in C++

#include 
#include 
#include 
#include 
#include 
using namespace std;

// Recursive DFS
void dfsRecursive(unordered_map>& graph, int start,
                   unordered_set& visited, vector& order) {
    visited.insert(start);
    order.push_back(start);

    for (int neighbor : graph[start]) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited, order);
        }
    }
}

// Iterative DFS
vector dfsIterative(unordered_map>& graph, int start) {
    unordered_set visited;
    stack st;
    vector order;

    st.push(start);

    while (!st.empty()) {
        int vertex = st.top();
        st.pop();

        if (visited.find(vertex) == visited.end()) {
            visited.insert(vertex);
            order.push_back(vertex);

            for (int neighbor : graph[vertex]) {
                if (visited.find(neighbor) == visited.end()) {
                    st.push(neighbor);
                }
            }
        }
    }
    return order;
}

int main() {
    unordered_map> graph;
    graph[0] = {1, 2};
    graph[1] = {0, 2, 3};
    graph[2] = {0, 1, 3};
    graph[3] = {1, 2};

    unordered_set visited;
    vector order;
    dfsRecursive(graph, 0, visited, order);
    for (int v : order) cout << v << " ";
    cout << endl;

    vector result = dfsIterative(graph, 0);
    for (int v : result) cout << v << " ";
    cout << endl;
    return 0;
}

BFS vs DFS — Comparison

Applications of BFS

• Shortest Path: Finding the shortest path in unweighted graphs (e.g., GPS navigation).
• Web Crawling: Google's web crawler uses BFS to index pages.
• Social Networks: Finding friends/followers at a certain distance (e.g., "6 degrees of separation").
• Peer‑to‑Peer Networks: Finding the shortest route in P2P networks.
• Maze Solving: Finding the shortest path in a maze.
• Garbage Collection: Mark‑and‑sweep algorithms use BFS/DFS.

Applications of DFS

• Topological Sorting: Ordering vertices in a DAG (dependency resolution).
• Cycle Detection: Detecting cycles in directed and undirected graphs.
• Connected Components: Finding all connected components in a graph.
• Path Finding: Finding any path between two vertices.
• Solving Puzzles: Sudoku, N‑Queens, mazes.
• Articulation Points & Bridges: Finding critical vertices/edges.
• Strongly Connected Components: Kosaraju's and Tarjan's algorithms use DFS.

BFS and DFS for Trees

For trees, BFS is often called level‑order traversal, and DFS can be applied as preorder (root, left, right), inorder (left, root, right), or postorder (left, right, root) traversals.

Tree Traversal Example

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def bfs_tree(root):
    if not root:
        return []
    queue = deque([root])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return order

def dfs_tree_preorder(root, order=None):
    if order is None:
        order = []
    if root:
        order.append(root.val)
        dfs_tree_preorder(root.left, order)
        dfs_tree_preorder(root.right, order)
    return order

Complexity Analysis

Choosing Between BFS and DFS

• Use BFS if:
  • You need the shortest path in an unweighted graph.
  • The graph is wide (many neighbors per node).
  • You need to find the closest node to the source.
• Use DFS if:
  • You need to explore all possible paths (e.g., puzzle solving).
  • The graph is deep (long paths).
  • You need topological sorting or cycle detection.
  • Memory is a concern (DFS uses less memory in deep graphs).

Key Takeaways

• BFS uses a queue and explores level by level.
• DFS uses a stack (or recursion) and explores as deep as possible.
• Both have O(V + E) time complexity for adjacency list representation.
• BFS finds the shortest path in unweighted graphs; DFS does not.
• DFS is useful for topological sorting, cycle detection, and backtracking.
• BFS is useful for shortest path, level‑order traversal, and finding connected components.