By Piyush Wairale · GATE DA Educator & Course Instructor, IIT Madras BS Programme · Updated August 2026

Graph Representations: Matrix vs List

An adjacency matrix is a V×V grid where entry (i, j) = 1 if edge i–j exists: O(1) edge lookup, but O(V²) space and O(V) to enumerate one vertex’s neighbours — wasteful for sparse graphs. An adjacency list stores each vertex’s neighbour list (a dict of lists in Python): O(V + E) space and neighbour enumeration proportional to degree. Since traversals spend all their time enumerating neighbours, the list representation is what gives BFS and DFS their O(V + E) bound — with a matrix both degrade to O(V²). That representation–complexity link is itself a GATE MCQ. Graph algorithms sit in the Programming & DSA section of the official GATE DA syllabus, alongside the sorting algorithms traced in the previous deep dive.

BFS Traced: Every Queue State

Our graph (undirected): edges A–B, A–C, B–D, B–E, C–F, E–F, F–G. Start at A, neighbours visited in alphabetical order. Mark visited when enqueued:

BFS visit order: A, B, C, D, E, F, G — pure levels: {A} then {B, C} then {D, E, F} then {G}.

BFS = Shortest Paths in Unweighted Graphs

Because BFS exhausts distance-k vertices before touching distance k+1, the level at which a vertex is discovered is its shortest hop-distance from the source. From our trace: dist = {A: 0, B: 1, C: 1, D: 2, E: 2, F: 2, G: 3}. Note F is reachable as A→C→F (2 hops) and A→B→E→F (3 hops) — BFS automatically records 2, because C dequeued first. DFS gives no such guarantee: it can reach F along the long path first. “Shortest path in an unweighted graph → which traversal?” is a standing one-marker: BFS.

DFS Traced: Dive Deep, Backtrack

Same graph, same rule (alphabetical neighbours), recursive DFS from A:

visit A → first neighbour B: visit B → first unvisited neighbour D: visit D (neighbours: only B, visited — backtrack) → next of B is E: visit E → unvisited neighbour F: visit F → F’s neighbours alphabetically C, E, G: visit C (its neighbours A, F both visited — backtrack) → visit G → backtrack all the way.

DFS discovery order: A, B, D, E, F, C, G — compare with BFS’s A, B, C, D, E, F, G: DFS reached distant F before nearby C. The tree edges are A–B, B–D, B–E, E–F, F–C, F–G, and the unused edge A–C becomes a back edge from C up to its ancestor A — the witness that the graph contains a cycle (A–B–E–F–C–A).

What DFS Is Actually For

Cycle detection: a back edge to a vertex still on the recursion stack (directed) or to a visited non-parent (undirected) proves a cycle. Topological sort: on a DAG, output vertices in reverse finishing order — the classic “course prerequisite” question. Connected components: restart DFS (or BFS) from every unvisited vertex; the number of restarts is the number of components. These three applications, plus BFS’s shortest paths, cover essentially every “which algorithm would you use?” MCQ. They are also the uninformed-search foundation for the AI section — BFS and DFS reappear as search strategies in the AI search algorithms pillar.

BFS vs DFS: the Comparison Table

The Python Implementations to Know

from collections import deque

def bfs(graph, start):
    visited, order = {start}, []
    q = deque([start])
    while q:
        u = q.popleft()              # FIFO
        order.append(u)
        for v in sorted(graph[u]):   # alphabetical tie-break
            if v not in visited:
                visited.add(v)       # mark when ENQUEUED
                q.append(v)
    return order

def dfs(graph, u, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(u)
    order.append(u)
    for v in sorted(graph[u]):
        if v not in visited:
            dfs(graph, v, visited, order)
    return order

# graph = {'A': ['B','C'], 'B': ['A','D','E'], ...}

Tree Traversals in 60 Seconds

DFS on a binary tree comes in three orders. Take the BST with root 5, left subtree 3 (children 1, 4), right subtree 8 (children 7, 9):

Inorder (left, root, right): 1, 3, 4, 5, 7, 8, 9 — on a BST this is always the sorted sequence, the single most-tested traversal fact. Preorder (root, left, right): 5, 3, 1, 4, 8, 7, 9 — used to copy/serialise a tree. Postorder (left, right, root): 1, 4, 3, 7, 9, 8, 5 — used to delete a tree bottom-up. BFS on a tree is just level-order: 5, 3, 8, 1, 4, 7, 9.

Three GATE-Style Problems, Solved

Problem 1 (MCQ/NAT). On our graph (A–B, A–C, B–D, B–E, C–F, E–F, F–G), run BFS from B with alphabetical tie-breaks. What is the fourth vertex visited?

Solution. Visit B → enqueue A, D, E. Dequeue A → enqueue C. Dequeue D → nothing. Dequeue E → enqueue F. Dequeue C → F already seen. Dequeue F → enqueue G. Order: B, A, D, E, C, F, G — the fourth visited is E.

Problem 2 (MCQ). Which is a valid DFS order from A (alphabetical tie-breaks) — (a) A,B,C,D,E,F,G (b) A,B,D,E,F,C,G (c) A,C,B,D,E,F,G (d) A,B,D,C,E,F,G?

Solution. (b) — exactly the trace above. (a) is the BFS order; (c) violates the alphabetical rule (B before C from A); (d) visits C from D, but they aren’t adjacent.

Problem 3 (NAT/MCQ). A BST is built by inserting 5, 3, 8, 1, 4, 7, 9. Write its inorder and postorder traversals.

Solution. Inorder = sorted keys: 1, 3, 4, 5, 7, 8, 9. Postorder: 1, 4, 3, 7, 9, 8, 5. If an exam option shows an unsorted “inorder” of a BST, it’s wrong by definition — no tracing needed.

Common Mistakes to Avoid

Marking visited at dequeue instead of enqueue. Late marking can enqueue a vertex twice and corrupt the order — mark the moment you enqueue.

Ignoring the stated tie-break rule. Visit orders are only unique given a rule (alphabetical, numerical). Half the wrong MCQ options come from breaking it.

Claiming DFS finds shortest paths. Only BFS guarantees minimum hops in unweighted graphs.

Quoting O(V+E) for adjacency-matrix traversals. With a matrix, enumerating neighbours costs O(V) per vertex → O(V²) total.

Forgetting the non-parent condition in undirected cycle detection. Seeing your parent again is not a cycle; seeing any other visited vertex is.

How GATE DA Asks Graph Traversals

Four repeat patterns: (1) MCQ/NAT — the k-th vertex visited, or the full valid order, under a stated tie-break; (2) MCQ — which sequences are valid BFS/DFS orders of a given graph; (3) NAT — shortest hop-distance via BFS levels, or number of connected components; (4) MCQ — tree traversal outputs, especially the BST-inorder-is-sorted fact and reconstructing a tree from two traversals. Trace with the queue/stack column method from this post and budget under three minutes each — the Python & DSA pillar covers the list/dict machinery the code snippets rely on.

FAQs: BFS & DFS for GATE DA

Keep the momentum: revise Python fundamentals in the Python & DSA pillar, pair this with the sorting algorithms deep dive, see the same traversals power informed search in the AI search guide, and track coverage against the GATE DA 2027 syllabus. New problem-solving sessions drop regularly on my YouTube channel — subscribe so you don’t miss them.