Graph traversals: BFS, DFS, connected components

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• With head insertion, in what order does an adjacency list hold its neighbours? from Lesson 6.2
• Where can the second largest key of a max-heap be? from Lesson 5.4
• Which structure gives level order in a tree? from Lesson 4.3.2

1 · The Hook

🎣

News spreads in two ways. A rumour told to everyone in a room, who each tell everyone in their rooms, spreads in rings — first friends, then friends of friends. An explorer in a cave follows one tunnel as far as it goes, then backs up to the last junction and tries the next tunnel. The first is breadth-first search, the second depth-first search.

2 · Predict First

🤔

In the running example, starting at 0 and always taking smaller-numbered neighbours first, in which order does a ring-by-ring visit reach the vertices? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

0 1 2 3 4 5: 0, then its neighbours 1, 2, then their new neighbours 3, 4, then 5. Vertices 6 and 7 are never reached: they are in another component.

BFS (breadth-first search)

Breadth-first search (BFS) uses a queue: enqueue the start; repeatedly dequeue a vertex, visit it, and enqueue its unseen neighbours, marking them seen when enqueued. Vertices are visited in order of distance (number of edges) from the start, so BFS gives shortest paths in an unweighted graph. Cost Θ(n + e) with lists, Θ(n²) with a matrix.

#define N 8
int g[N][N];

void build(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
}

int dist[N], q[N];

void bfs(int s)
{
    int front = 0, rear = 0, v, w, i;
    for (i = 0; i < N; i++) dist[i] = -1;          /* -1 means not yet seen */
    dist[s] = 0;
    q[rear++] = s;
    while (front < rear) {
        v = q[front++];
        printf("%d ", v);
        for (w = 0; w < N; w++)
            if (g[v][w] && dist[w] == -1) {
                dist[w] = dist[v] + 1;             /* mark when enqueued */
                q[rear++] = w;
            }
    }
    printf("\n");
}

int main(void)
{
    int i;
    build();
    bfs(0);
    for (i = 0; i < N; i++) printf("%d ", dist[i]);
    printf("\n");
    return 0;
}

Output

0 1 2 3 4 5 
0 1 1 2 2 3 -1 -1

DFS (depth-first search)

Depth-first search (DFS) goes to an unseen neighbour immediately and backtracks when stuck — recursion (or an explicit stack). Same cost as BFS. The edges used form a DFS tree; in an undirected graph, an edge to an already seen vertex that is not the parent reveals a cycle.

#define N 8
int g[N][N];

void build(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
}

int seen[N];

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

int main(void)
{
    int v, c = 0;
    build();
    for (v = 0; v < N; v++)
        if (!seen[v]) {                   /* a new component starts here */
            printf("{ ");
            dfs(v);
            printf("} ");
            c++;
        }
    printf("\n%d\n", c);
    return 0;
}

Output

{ 0 1 3 5 4 2 } { 6 7 } 
2

Connected components

Run a traversal from every vertex not yet seen; each new start begins a new component. The number of starts is the number of components; total cost still Θ(n + e). The program above finds {0, 1, 3, 5, 4, 2} and {6, 7}.

Many valid orders

Traversal order depends on the order of neighbours. From 0 in the 6-vertex component, the valid BFS orders are 0 1 2 3 4 5, 0 1 2 4 3 5, 0 2 1 4 3 5 and the valid DFS orders are 0 1 3 5 4 2, 0 1 4 2 5 3, 0 1 4 5 3 2, 0 2 4 1 3 5, 0 2 4 5 3 1 (computed by trying every neighbour order). With head-inserted lists (Lesson 6.2) the same DFS code visits 0 2 4 5 3 1.

4 · Visual

BFS from 0: levels (distances) under each vertex; highlighted edges form the BFS tree.

DFS from 0 (smaller neighbour first): the DFS tree is the path 0-1-3-5-4-2.

BFS from 0 (queue shown after visiting each vertex)

visit  queue after        visit  queue after
  0    1 2                  3    4 5
  1    2 3 4                4    5
  2    3 4                  5    (empty)

DFS from 0 (call stack)
dfs(0) -> dfs(1) -> dfs(3) -> dfs(5) -> dfs(4) -> dfs(2)
                                         stuck: back up to 4, 5, 3, 1, 0 -> done

BFS spreads by rings using a queue; DFS dives using the call stack.

5 · Worked Examples

Example 1 Easy

In the running example, what is the shortest distance (in edges) from 0 to 5, and how many vertices are at distance 2?

Solution

BFS levels: 5 is at level 3; vertices 3 and 4 are at level 2: 2 vertices.

Example 2 Medium

What does this print?

#define N 8
struct node {
    int v;
    struct node *next;
};
struct node *adj[N];                      /* adjacency lists, all NULL at start */

void addEdge(int a, int b)                /* insert b at the head of a's list */
{
    struct node *p = malloc(sizeof(struct node));
    p->v = b;
    p->next = adj[a];
    adj[a] = p;
}

int seen[N];

void dfs(int v)
{
    struct node *p;
    seen[v] = 1;
    printf("%d ", v);
    for (p = adj[v]; p != NULL; p = p->next)
        if (!seen[p->v]) dfs(p->v);
}

int main(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) {
        addEdge(e[i][0], e[i][1]);
        addEdge(e[i][1], e[i][0]);
    }
    dfs(0);
    printf("\n");
    return 0;
}

Solution

The lists are head-inserted (0: 2 1; 1: 4 3 0; 2: 4 0; 3: 5 1; 4: 5 2 1; 5: 4 3), so DFS takes 2 before 1.

Output

0 2 4 5 3 1

Example 3 GATE

Which of these are valid DFS orders of the running example starting at 0: 0 1 4 2 5 3 / 0 2 4 1 5 3 / 0 1 3 5 4 2 / 0 2 1 4 3 5?

Solution

Valid: 0 1 4 2 5 3 and 0 1 3 5 4 2 (true,false,true,false). In 0 2 4 1 5 3, after 1 the search must go to 1’s unseen neighbour 3, not to 5. 0 2 1 … jumps from 2 to 1, which is not adjacent to 2 while 2 still has the unseen neighbour 4.

6 · GATE Traps

⚠️

• BFS marks a vertex seen when it is enqueued, not when dequeued; otherwise it can be enqueued twice.
• BFS shortest paths hold only for unweighted graphs (edge counts).
• Traversal order depends on neighbour order; head-inserted lists reverse it.
• A traversal from one vertex reaches only its component; loop over all vertices to count components.
• Cost: Θ(n + e) with lists, Θ(n²) with a matrix.

8 · Memory Hook

🧠

“Queue spreads in rings; stack dives down tunnels.”

9 · Connect the Dots

Phase 6 is complete, and with it every topic in the syllabus. Phase 7 answers: can you retrieve and combine all of it under exam conditions — rule sheet, mixed sets, a GATE-pattern drill and a full test?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markStructure

BFS uses a ______ and DFS uses a ______.

• (A) queue; stack (or recursion)
• (B) queue; heap
• (C) heap; queue
• (D) stack; queue

Q2MCQ2 marksOutput

What does this print?

#define N 8
int g[N][N];

void build(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
}

int dist[N], q[N];

void bfs(int s)
{
    int front = 0, rear = 0, v, w, i;
    for (i = 0; i < N; i++) dist[i] = -1;          /* -1 means not yet seen */
    dist[s] = 0;
    q[rear++] = s;
    while (front < rear) {
        v = q[front++];
        printf("%d ", v);
        for (w = 0; w < N; w++)
            if (g[v][w] && dist[w] == -1) {
                dist[w] = dist[v] + 1;             /* mark when enqueued */
                q[rear++] = w;
            }
    }
    printf("\n");
}

int main(void)
{
    int i;
    build();
    bfs(0);
    for (i = 0; i < N; i++) printf("%d ", dist[i]);
    printf("\n");
    return 0;
}

• (A) 0 1 2 3 4 5 6 7 then 0 1 1 2 2 3 4 5
• (B) 0 1 2 3 4 5 then 0 1 1 2 2 3 0 0
• (C) 0 1 3 5 4 2 then 0 1 1 2 2 3 -1 -1
• (D) 0 1 2 3 4 5 then 0 1 1 2 2 3 -1 -1

Q3MSQ2 marksValid BFS

Which are valid BFS orders of the running example from 0?

• (A) 0 2 1 4 3 5
• (B) 0 1 2 4 3 5
• (C) 0 2 1 3 4 5
• (D) 0 1 2 3 4 5

Q4NAT2 marksOutput

How many components does this program report (the last number printed)?

#define N 8
int g[N][N];

void build(void)
{
    int e[][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {6, 7}};
    int i;
    for (i = 0; i < 8; i++) g[e[i][0]][e[i][1]] = g[e[i][1]][e[i][0]] = 1;
}

int seen[N];

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

int main(void)
{
    int v, c = 0;
    build();
    for (v = 0; v < N; v++)
        if (!seen[v]) {                   /* a new component starts here */
            printf("{ ");
            dfs(v);
            printf("} ");
            c++;
        }
    printf("\n%d\n", c);
    return 0;
}

Numerical answer: ________

Q5MCQ1 markCost

BFS on a graph stored as an adjacency matrix costs:

• (A) Θ(n²)
• (B) Θ(e log n)
• (C) Θ(n)
• (D) Θ(n + e)

11 · Rule Card

• BFS: queue; mark when enqueued; visits by distance; shortest paths in unweighted graphs.
• DFS: recursion/stack; dives then backtracks; non-parent seen neighbour ⇒ cycle (undirected).
• Components: restart a traversal at each unseen vertex; count the starts.
• Θ(n + e) with lists, Θ(n²) with a matrix.
• Orders depend on neighbour order; check validity by simulation.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

BFS (queue)DFS (stack / recursion)BFS distance levelscounting connected componentsvalid traversal orders

13 · Answer Vault