Graph traversals

ACompressed recap

🧾

BFS uses a queue and visits vertices by distance (shortest edge counts in unweighted graphs); DFS dives using recursion or a stack. Both cost Θ(n + e) with lists, Θ(n²) with a matrix. Restarting a traversal at every unseen vertex counts the connected components. Visiting orders depend on neighbour order; to check a given order, simulate the queue or stack.

BMerged rule card

6.3 Graph traversals: BFS, DFS, connected components

• 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.

CInterleaved GATE-style questions

Q1MCQ2 marksValid DFS

Which is a valid DFS order of the running example from 0?

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

Q2MCQ2 marksOutput

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;
}

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

Q3NAT1 markComponents

A graph has 10 vertices and its DFS-based component counter starts 4 new traversals. How many components?

Numerical answer: ________

Q4MCQ1 markShortest path

Which traversal finds the fewest-edges path from s to every vertex in an unweighted graph?

• (A) neither
• (B) either
• (C) DFS
• (D) BFS

Q5NAT2 marksDistance

In the running example, what is dist[5] after BFS from 0?

Numerical answer: ________

Q6MSQ2 marksFacts

Which are true?

• (A) DFS can detect a cycle in an undirected graph.
• (B) In BFS, a vertex should be marked when it is enqueued.
• (C) A single BFS from any vertex reaches every vertex of any graph.
• (D) BFS with adjacency lists is Θ(n + e).

Q7MCQ1 markDirected

In the directed graph 1→2, 1→3, 2→4, 3→4, 4→5, 5→2, DFS from 1 (smaller neighbour first) visits:

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

Q8MCQ2 marksCost

Counting components of a graph with n vertices and e edges stored as adjacency lists costs:

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

DAnswer Vault