BFS and DFS with example

Depth first traversal (DFS)

Goes as deep as possible along each path, then backtracks. Uses a stack (or recursion). From a vertex, move to an unvisited neighbour; when none remains, pop back.

int adj[N][N], visited[N], n;
void dfs(int v) {
    visited[v] = 1;
    printf("%d ", v);
    for (int w = 0; w < n; w++)
        if (adj[v][w] && !visited[w])
            dfs(w);
}

Breadth first traversal (BFS)

Visits the start vertex, then all its neighbours, then their neighbours, level by level. Uses a queue.

int adj[N][N], visited[N], n;
void bfs(int s) {
    int queue[N], front = 0, rear = 0;
    visited[s] = 1; queue[rear++] = s;
    while (front < rear) {
        int v = queue[front++];            /* dequeue */
        printf("%d ", v);
        for (int w = 0; w < n; w++)
            if (adj[v][w] && !visited[w]) {
                visited[w] = 1;
                queue[rear++] = w;         /* enqueue */
            }
    }
}

Example graph

        A
       / \
      B   C
     / \   \
    D   E---F

Edges: A-B, A-C, B-D, B-E, C-F, E-F. Adjacency lists (alphabetical): A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

BFS from A (queue):

BFS order: A B C D E F

DFS from A (stack, alphabetical order): A → B → D (dead end, back to B) → E → F → C.

DFS order: A B D E F C

Both take O(V + E) time with adjacency lists.