Self-checkedTier 1 12 min readalgo.graph-traversals-bfs-dfs

BFS and DFS

The two basic graph searches. Breadth-first search with a queue (distances in edges, shortest paths in unweighted graphs, levels) and depth-first search with colours and discovery and finish times (parenthesis and white-path theorems), both in O(V + E) with adjacency lists and O(V^2) with a matrix; applications: reachability, connected components, bipartiteness, cycle detection; the traps in marking and in the order of neighbours.

Why it exists

Almost every graph question starts with "visit every vertex reachable from here, exactly once". Two systematic ways to do it, breadth-first search (BFS) and depth-first search (DFS), are the engines behind connectivity, shortest paths in unweighted graphs, cycle detection, topological sorting, strongly connected components, spanning trees, and many puzzle solvers. Both take $O(V + E)$ time; they differ in the order of the visit, and that order is what each application uses. GATE asks for visit orders, distances, discovery and finish times, and what can be concluded from them.

Prerequisites

Graph representations Queue (abstract data type)

You need graph representations, adjacency lists in particular (graph representations), and the queue (queue).

Precise definitions

Graph. $G = (V, E)$ with $|V| = n$ vertices and $|E| = m$ edges (the pages write $V$ and $E$ for the counts). A path is a sequence of vertices with an edge between consecutive ones; the graph is connected (undirected) if there is a path between any two vertices; a connected component is a largest set of vertices that are pairwise connected. A cycle is a path that returns to its start without repeating an edge. A tree is a connected graph without cycles; it has exactly $V - 1$ edges.

Breadth-first search from a source $s$ . Visit $s$ , then all vertices at distance $1$ , then all at distance $2$ , and so on: a queue holds the vertices that are discovered but not yet expanded. Taking a vertex $u$ from the front, each undiscovered neighbour $v$ gets $\text{dist}[v] = \text{dist}[u] + 1$ , $\text{parent}[v] = u$ , and goes to the back of the queue.

Depth-first search. From a vertex, follow an edge to an undiscovered neighbour and continue from there as deep as possible; when a vertex has no undiscovered neighbour left, go back. It is a recursion (or an explicit stack). Each vertex has a colour: white (undiscovered), gray (discovered, still being explored: it is on the recursion stack), black (finished). A counter gives each vertex a discovery time $d[v]$ when it turns gray and a finish time $f[v]$ when it turns black; times run through $1, 2, \ldots, 2V$ with no repetition.

Distance. The number of edges on a shortest path (BFS does not use weights).

How it works

Breadth-first search

The animation runs the real code on the graph with the edges $0$ - $1$ , $0$ - $2$ , $1$ - $3$ , $1$ - $4$ , $2$ - $4$ , $3$ - $5$ , $4$ - $5$ , $4$ - $6$ , $5$ - $7$ . The lists are in increasing order, which fixes the order of the search.

Breadth-first search: visit the vertices level by level with a queue

Real run

C source

1#include <stdio.h>

3#define N 8

5static int deg[N];

6static int nbr[N][N]; /* nbr[u][0 .. deg[u]-1]: the neighbours of u, an adjacency list */

8/* distances (in edges) and parents of all vertices reachable from source; -1 means not reached */

9void bfs(int source, int dist[], int parent[]) {

10 int queue[N];

11 int head = 0, tail = 0;

12 for (int v = 0; v < N; v++) {

13 dist[v] = -1;

14 parent[v] = -1;

15 }

16 dist[source] = 0;

17 queue[tail++] = source;

18 while (head < tail) {

19 int u = queue[head++];

20 for (int k = 0; k < deg[u]; k++) {

21 int v = nbr[u][k];

22 if (dist[v] == -1) {

23 dist[v] = dist[u] + 1;

24 parent[v] = u;

25 queue[tail++] = v;

26 }

27 }

28 }

29}

dist[v] (blank = not reached yet)

parent[v]

queue (positions already taken out are faded)

Adjacency lists

0→1→2→ NULL

1→0→3→4→ NULL

2→0→4→ NULL

3→1→5→ NULL

4→1→2→5→6→ NULL

5→3→4→7→ NULL

6→4→ NULL

7→5→ NULL

State

edges examined so far = 0 (every edge is examined twice in the end: once from each end)

Blue = the position this step is working on, amber = a position being compared, red = positions just swapped, green = finished or in its final place, a filled blue cell = a value just placed, faded = not part of the structure at this step.

Step 1

A graph with 8 vertices and 9 edges. Breadth-first search from vertex 0.

1 / 36

The undirected graph with 8 vertices and the edges 0-1, 0-2, 1-3, 1-4, 2-4, 3-5, 4-5, 4-6, 5-7 is set up by hidden driver code; neighbours are listed in increasing order. bfs() is the exact code that runs. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. Apple clang version 21.0.0 (clang-2100.1.1.101). gcc -O0 -o prog prog.c && ./prog

Why distances are right: the queue always holds vertices of at most two consecutive distances, $d, \ldots, d, d+1, \ldots, d+1$ in non-decreasing order, so vertices are taken out in order of distance; a vertex gets its distance when it is first reached, from a vertex of the previous level. The parent links form the BFS tree; the path in it from $s$ to $v$ is a shortest path. For an undirected graph every edge joins two vertices whose levels differ by at most $1$ .

Depth-first search

Same graph, same order. Gray vertices are the stack; a tree edge leads to a white vertex; the other edges lead to gray or black vertices.

Depth-first search: go as deep as possible, with discovery and finish times

Real run

C source

1#include <stdio.h>

3#define N 8

4enum { WHITE, GRAY, BLACK };

6static int deg[N];

7static int nbr[N][N];

8static int color[N], parent[N], disc[N], fin[N], timer;

10void dfs_visit(int u) {

11 color[u] = GRAY;

12 disc[u] = ++timer;

13 for (int k = 0; k < deg[u]; k++) {

14 int v = nbr[u][k];

15 if (color[v] == WHITE) {

16 parent[v] = u;

17 dfs_visit(v);

18 }

19 }

20 color[u] = BLACK;

21 fin[u] = ++timer;

22}

24void dfs(void) {

25 for (int v = 0; v < N; v++) {

26 color[v] = WHITE;

27 parent[v] = -1;

28 }

29 timer = 0;

30 for (int v = 0; v < N; v++) {

31 if (color[v] == WHITE) {

32 dfs_visit(v);

33 }

34 }

35}

color (W = white: unvisited, G = gray: on the stack, B = black: finished)

discovery time disc[v]

finish time fin[v]

parent[v]

recursion stack (top on the right)

bottomempty

Adjacency lists

0→1→2→ NULL

1→0→3→4→ NULL

2→0→4→ NULL

3→1→5→ NULL

4→1→2→5→6→ NULL

5→3→4→7→ NULL

6→4→ NULL

7→5→ NULL

Step 1

Depth-first search from vertex 0. Times count 1, 2, 3, ... for every discovery and every finish.

1 / 43

The same graph as the breadth-first animation. dfs() and dfs_visit() are the exact code that runs; the vertices are tried in increasing order. Produced by: real execution: every array, stack, matrix and list in the picture is read from the running program's memory at each step. Apple clang version 21.0.0 (clang-2100.1.1.101). gcc -O0 -o prog prog.c && ./prog

Two theorems that are used all the time (and were tested on 1000 random graphs):

Parenthesis theorem. For any two vertices $u, v$ the intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ are either disjoint or one is inside the other; $v$ is a descendant of $u$ in the depth-first forest exactly when $[d[v], f[v]] \subset [d[u], f[u]]$ .
White-path theorem. $v$ becomes a descendant of $u$ exactly when, at the time $d[u]$ , there is a path from $u$ to $v$ consisting of white vertices.

Both on one table

The program runs both searches on the page graph, counts edge examinations, and prints the results for each vertex.

#include <stdio.h>
 
#define N 8
 
static int deg[N], nbr[N][N];                /* adjacency lists in increasing order */
static int examined;
 
static void add_edge(int u, int v) { nbr[u][deg[u]++] = v; nbr[v][deg[v]++] = u; }
 
static void sort_lists(void) {
    for (int u = 0; u < N; u++)
        for (int i = 1; i < deg[u]; i++) {
            int x = nbr[u][i], j = i - 1;
            while (j >= 0 && nbr[u][j] > x) { nbr[u][j + 1] = nbr[u][j]; j--; }
            nbr[u][j + 1] = x;
        }
}
 
static void bfs(int source, int dist[], int parent[], int order[]) {
    int queue[N], head = 0, tail = 0;
    for (int v = 0; v < N; v++) { dist[v] = -1; parent[v] = -1; }
    dist[source] = 0;
    queue[tail++] = source;
    while (head < tail) {
        int u = queue[head++];
        order[head - 1] = u;
        for (int k = 0; k < deg[u]; k++) {
            int v = nbr[u][k];
            examined++;
            if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; queue[tail++] = v; }
        }
    }
}
 
enum { WHITE, GRAY, BLACK };
static int color[N], par[N], disc[N], fin[N], timer;
 
static void dfs_visit(int u) {
    color[u] = GRAY;
    disc[u] = ++timer;
    for (int k = 0; k < deg[u]; k++) {
        int v = nbr[u][k];
        examined++;
        if (color[v] == WHITE) { par[v] = u; dfs_visit(v); }
    }
    color[u] = BLACK;
    fin[u] = ++timer;
}
 
int main(void) {
    int E[9][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 4}, {3, 5}, {4, 5}, {4, 6}, {5, 7}};
    for (int i = 0; i < 9; i++) add_edge(E[i][0], E[i][1]);
    sort_lists();
    int dist[N], parent[N], order[N];
    examined = 0;
    bfs(0, dist, parent, order);
    printf("BFS from 0: order");
    for (int i = 0; i < N; i++) printf(" %d", order[i]);
    printf("; %d edge examinations\n", examined);
    for (int v = 0; v < N; v++) { color[v] = WHITE; par[v] = -1; }
    examined = 0;
    for (int v = 0; v < N; v++) if (color[v] == WHITE) dfs_visit(v);
    printf("DFS from 0: %d edge examinations\n", examined);
    printf("%2s %5s %6s %5s %4s %7s\n", "v", "dist", "bfs-p", "disc", "fin", "dfs-p");
    for (int v = 0; v < N; v++) printf("%2d %5d %6d %5d %4d %7d\n", v, dist[v], parent[v], disc[v], fin[v], par[v]);
    return 0;
}

BFS from 0: order 0 1 2 3 4 5 6 7; 18 edge examinations
DFS from 0: 18 edge examinations
 v  dist  bfs-p  disc  fin   dfs-p
 0     0     -1     1   16      -1
 1     1      0     2   15       0
 2     1      0     6    7       4
 3     2      1     3   14       1
 4     2      1     5   10       5
 5     3      3     4   13       3
 6     3      4     8    9       4
 7     4      5    11   12       5

Breadth-first and depth-first search of the same graph: start

Computed by a script, not typed

vertex	BFS distance	BFS parent	DFS discovery	DFS finish	DFS parent
vertex 0
vertex 1
vertex 2
vertex 3
vertex 4
vertex 5
vertex 6
vertex 7

Step 0

Both searches start at vertex 0 and look at the neighbours of a vertex in increasing order. The numbers come from the C program on this page.

0 / 8

computed by script: the quantities are measured by running C, or evaluated, one row at a time. python3 scripts/gen-algo-graph-traces.py

Breadth-first distances $0, 1, 1, 2, 2, 3, 3, 4$ ; depth-first intervals nested like brackets ( $[1, 16]$ for the root contains all others). Both searches examined $18 = 2 \cdot 9$ edge entries: each undirected edge appears in the lists of both of its ends.

Cost

Time. Each vertex is expanded once and each adjacency list is scanned once: $\Theta(V + E)$ with adjacency lists. With an adjacency matrix scanning the neighbours of a vertex costs $\Theta(V)$ , so $\Theta(V^2)$ .
Space. BFS: the queue, $O(V)$ . DFS: the recursion stack, up to $O(V)$ (a path graph); plus the colour, time and parent arrays, $\Theta(V)$ .

What they are used for

Question	Method
Is $v$ reachable from $s$ ?	one search from $s$
Shortest path in edges (unweighted)	BFS
Connected components	repeat the search from every unvisited vertex; count the starts
Is the graph bipartite (2-colourable)?	BFS (or DFS) colouring: each vertex gets the colour opposite its parent; an edge joining equal colours means an odd cycle, so the graph is not bipartite
Does an undirected graph have a cycle?	an edge to an already visited vertex other than the parent (equivalently $E > V - c$ for a graph with $c$ components; a forest has exactly $V - c$ edges)
Does a directed graph have a cycle, topological order, strongly connected components	DFS (next page)
Spanning tree	the search tree is a spanning tree of the component

Worked examples

EX 1BFS order and distances

Easy

Page graph, source $0$ . Queue: $[0]$ . Take $0$ : neighbours $1, 2$ are new, distance $1$ : $[1, 2]$ . Take $1$ : neighbours $0$ (seen), $3, 4$ are new, distance $2$ : $[2, 3, 4]$ . Take $2$ : $0, 4$ both seen. Take $3$ : $5$ new, distance $3$ : $[4, 5]$ . Take $4$ : $1, 2, 5$ seen, $6$ new, distance $3$ : $[5, 6]$ . Take $5$ : $3, 4$ seen, $7$ new, distance $4$ . Visit order $0, 1, 2, 3, 4, 5, 6, 7$ ; distances $0, 1, 1, 2, 2, 3, 3, 4$ as in the table.

EX 2DFS times by hand

Easy

Same graph. $0$ (time $1$ ) $\to 1$ ( $2$ ) $\to 3$ ( $3$ ) $\to 5$ ( $4$ ) $\to 4$ ( $5$ ) $\to 2$ ( $6$ ): the neighbours of $2$ are $0$ and $4$ , both gray, so $2$ finishes at $7$ . Back at $4$ : $5$ is gray, $6$ is new ( $8$ , finishes $9$ ); $4$ finishes at $10$ . Back at $5$ : $7$ is new ( $11$ , finishes $12$ ); $5$ finishes at $13$ ; $3$ at $14$ ; $1$ at $15$ (its neighbour $4$ is already black); $0$ at $16$ . The edges $0$ - $1$ , $1$ - $3$ , $3$ - $5$ , $5$ - $4$ , $4$ - $2$ , $4$ - $6$ , $5$ - $7$ are the tree edges.

EX 3Bipartite or not

Medium

For the page graph, colour $0$ with $A$ ; $1, 2$ get $B$ ; $3, 4$ (neighbours of $1$ ) get $A$ , and $4$ is also a neighbour of $2$ ( $B$ ): consistent; $5, 6$ get $B$ , $7$ gets $A$ ; every edge joins different colours: bipartite. Add the edge $3$ - $4$ : both are $A$ , they close the odd cycle $1$ - $3$ - $4$ : not bipartite. (A graph is bipartite exactly when it has no cycle of odd length; checked by trying all $2^n$ colourings on random graphs.)

EX 4Counting components and edges

Medium

A graph with $V = 10$ vertices and $E = 6$ edges has at least $V - E = 4$ connected components (each edge can reduce the number of components by at most one), and exactly $V - E$ if it has no cycle. A connected graph needs $E \ge V - 1$ . A graph with $V$ vertices and $E \ge V$ edges, if connected, has a cycle.

EX 5Typical statements

GATE level

(a) BFS finds shortest paths in an unweighted graph: true; in a weighted graph: false (use Dijkstra). (b) DFS finds shortest paths: false (the path in the DFS tree can be much longer). (c) Time of BFS on an adjacency matrix: $\Theta(V^2)$ ; on adjacency lists $\Theta(V + E)$ . (d) The order of visit is unique: false; it depends on the source and the order of the adjacency lists. (e) The maximum size of the BFS queue of a star graph with $n$ leaves: $n$ (all leaves are queued at once). (f) Number of times the loop body runs over adjacency lists in BFS of an undirected graph: $2E$ .

Cheat box

BFS: queue; $\text{dist}[v] = \text{dist}[u] + 1$ on first discovery; shortest paths in edges; levels differ by $\le 1$ across any edge of an undirected graph.
DFS: stack/recursion; colours white, gray, black; times $d[v] < f[v]$ using $1 \ldots 2V$ ; parenthesis theorem; white-path theorem.
Time $\Theta(V + E)$ with lists, $\Theta(V^2)$ with a matrix. Space $O(V)$ .
Mark a vertex when it is put into the queue (not when taken out), or it can be queued many times.
Bipartite iff no odd cycle (BFS two-colouring). Components: one search per start. Undirected cycle: an edge to a visited vertex other than the parent.
$V$ vertices, $E$ edges: components $\ge V - E$ ; connected needs $E \ge V - 1$ ; a tree has $V - 1$ edges.

Traps and GATE patterns

Connections

Builds on

Graph representations Queue (abstract data type)

Unlocks

DFS edge types, topological sort and SCCPrerequisite of DFS edge types, topological sort and SCCuses Spanning trees and the cut propertyPrerequisite of Spanning trees and the cut propertyuses Dijkstra's algorithmPrerequisite of Dijkstra's algorithmuses Queue (abstract data type)uses Binary tree traversalsanalogous to Graph representationsuses

Across subjects

Graph representationsuses Queue (abstract data type)uses Stack (abstract data type)uses

Within this subject

DFS edge types, topological sort and SCCimplemented-by Spanning trees and the cut propertyimplemented-by Dijkstra's algorithmanalogous-to

The queue of BFS and the stack of DFS are the data structures of the queue and the stack; the graphs are stored as in graph representations. DFS is developed further in edge types, topological sort and strongly connected components, and both searches underlie spanning trees. Dijkstra's algorithm (shortest paths) is BFS with a priority queue instead of a queue.

PYQs

16 previous year questions from your book. I re-solved each one myself (15 by running or simulating, 1 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2025 · Set 1 · MCQQ7 · page 114 of the book

Let G(V, E) be an undirected and unweighted
graph with 100 vertices. Let d(u, v) denote the
number of edges in a shortest path between
vertices u and v in V. Let the maximum value of
d(u, v), u, v ∈⁡V such that u ≠ v, be 30. Let T be
any breadth-first-search tree of G. Which ONE of
the given options is CORRECT for every such
graph G?

(a)The height of T is exactly 15.
(b)The height of T is exactly 30.
(c)The height of T is at least 15.
(d)The height of T is at least 30.

GATE 2022 · NAT · 1 markQ11 · page 114 of the book

"Let G(V, E) be a directed graph, where V = {1, 2,
3, 4, 5} is the set of vertices and E is the set of
directed edges, as defined by the following
adjacency matrix A.

"A[i][j] = 1 indicates a directed edge from node i
to node j."A directed spanning tree of G, rooted at
r ∈⁡V, is defined as "a subgraph T of G such that
the undirected version of T is a tree, and T
contains a directed path from r to every other
vertex in V." The number of such directed
spanning trees rooted at vertex 5 is
.

GATE 2005 · NAT · 1 markQ47 · page 121 of the book

Let G be a directed graph whose vertex set is the
set of numbers from 1 to 100. There is an edge
from a vertex i to a vertex j iff either j = i + 1 or j
= 3i. The minimum number of edges in a path in G
from vertex 1 to vertex 100 is:

(a)4
(b)7
(c)23
(d)99

GATE 2026 · Set 1 · MSQ · 2 marksQ2 · page 136 of the book

An undirected, unweighted, simple graph G(V, E) is
said to be 2 -colorable if there exists a function c: V →
{0,1} such that for every (u, v) ∈ E, c(u) ≠ c(v).
Which of the following statements about 2-
colorable graphs is/are true?

(a)If G is 2-colorable, then G may contain cycles of odd length
(b)If G is 2-colorable, then G may contain cycles of even length
(c)An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V|+|E|), if G is represented as an adjacency list
(d)An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|E|log|V|), if G is represented as an adjacency list.

GATE 2025 · Set 2 · NAT · 2 marksQ3 · page 136 of the book

Consider the following algorithm someAlgo that
takes an undirected graph G as input.
someAlgo(G) :
1. Let v be any vertex in G. Run BFS on G starting
at v. Let u be a vertex in G at maximum distance
from v as given by the BFS.

2. Run BFS on G again with u as the starting vertex.
Let z be the vertex at maximum distance from u as
given by the BFS.
3. Output the distance between u and z in G.
The output of someAlgo(T) for the tree shown in the
given figure is
. (Answer in integer)

5 5
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2025 · Set 2 · MSQ · 1 markQ4 · page 137 of the book

Which of the following statements regarding
Breadth First Search (BFS) and Depth First Search
(DFS) on an undirected simple graph G is/are
TRUE?

(a)A DFS tree of G is a Shortest Path tree of G.
(b)Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
(c)If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex s to u and v in the BFS tree are within ±1 of each other.
(d)Both BFS and DFS can be used to find the connected components of G.

GATE 2024 · Set 1 · NATQ6 · page 137 of the book

The number of edges present in the forest
generated by the DFS traversal of an undirected
graph G with 100 vertices is 40. The number of
connected components in G is
Which one of the following statements is true?

(a)⌈⁡diam (G) / 2⌉ < diam (G 2 ) < diam(G)
(b)diam(G 2 ) = diam(G)
(c)diam(G) = diam(G 2 ) <= 2 diam(G)
(d)diam(G 2 ) <= ⌈⁡diam (G) / 2 ⌉

GATE 2023 · NAT · 2 marksQ7 · page 137 of the book

Let U = {1, 2, 3}. Let 2U denote the powerset of U.
Consider an undirected graph G whose vertex set is
2U. For any A, B in 2U, (A, B) is an edge in G if and
only if (i) A != B, and (ii) either A ⊆⁡B or B ⊆⁡A.
For any vertex A in G, the set of all possible orderings
in which the vertices of G can be visited in a Breadth
First Search (BFS) starting from A is denoted by
B(A).
If Φ denotes the empty set, then the cardinality of
B(Φ) is   .

GATE 2021 · Set 1 · MCQQ8 · page 137 of the book

Let G = (V, E) be an undirected unweighted
connected graph. The diameter of G is defined as:
diam(G)=max{" the length of shortest path
between " u" and " v}
Let M be the adjacency matrix of G. Define graph
G2 on the same set of vertices with adjacency
matrix N, where
v. Suppose T is also a breadth first search (BFS)
N
1
if Mij > 0 or Pij > 0
tree in G, rooted at v. Which of the following
statements is/are TRUE for every such graph G and
ij = {0
where P = M2.
otherwise
tree T?

(a)The only edges in G are the edges in T
(b)There are no cross-edges in G with respect to the tree T
(c)There are no back-edges in G with respect to the tree T
(d)There are no forward-edges in G with respect to the tree T

GATE 2018 · MCQ · 2 marksQ9 · page 137 of the book

Match Let G be a simple undirected graph. Let TD be
a depth first search tree of G. Let TB be a breadth
first search tree of G. Consider the following
statements.
(I) No edge of G is a cross edge with respect to TD.
(A cross edge in G is between two nodes neither of
which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v
is at depth j in TB, then |i - j| = 1.
Which of the statements above must necessarily be
true?

(a)I only
(b)II only
(c)Both I and II
(d)Neither I nor II ALGORITHMS Check Out Our Gate Courses & Secure Your Dream Rank !

GATE 2016 · Set 2 · NATQ10 · page 138 of the book

Breadth First Search (BFS) is started on a binary
tree beginning from the root vertex. There is a
vertex t at a distance four from the root. If t is the
n-th vertex in this BFS traversal, then the
maximum possible value of n is  .

GATE 2015 · Set 1 · MCQ · 1 markQ12 · page 138 of the book

Let G= (V,E) be a simple undirected graph, and s
be a particular vertex in it called the source. For x
∈ V, let d (x) denote the shortest distance in G
from s to x. A breadth first search (BFS) is
performed starting at s. Let T be the resultant BFS
tree. If (u, v) is an edge of G that is not in T, then
which one of the following CANNOT be the
value of d (u) - d (v)?

(a)-1
(b)0
(c)1
(d)2

GATE 2014 · Set 3 · NAT · 1 markQ13 · page 138 of the book

Suppose depth first search is executed on the graph
below starting at some unknown vertex. Assume
that a recursive call to visit a vertex is made only
after first checking that the vertex has not been
visited earlier. Then the maximum possible
recursion depth (including the initial call) is
.

GATE 2008 · MCQQ14 · page 138 of the book

Consider the following sequence of nodes for the
undirected graph given below:
1.a b e f d g c
2.a b e f c g d
3.a d g e b c f
4.a d b c g e f
A Depth First Search (DFS) is started at node a. The
nodes are listed in the order they are first visited.
Which of the above is/are possible output(s)?

(a)1 and 3 only
(b)2 and 3 only
(c)2,3 and 4 only
(d)1,2 and 3 only

GATE 2015 · Set 2 · MCQ · 1 markQ6 · page 147 of the book

Given below are some algorithms, and some
algorithm design paradigms.
List - I
P. Dijkstra's Shortest Path
Q. Floyd-Warshall algorithm to compute all
pairs shortest path
R. Binary search on a sorted array
S. Backtracking search on a graph
List – II
i. Divide and Conquer
ii. Dynamic Programming
iii. Greedy design
iv. Depth-first search
v. Breadth-first search
Match the above algorithms on the left to the
corresponding design paradigm they follow.

(a)P-i, Q-iii, R-i, S-v.
(b)P-iii, Q-iii, R-i, S-v.
(c)P-iii, Q-ii, R-i, S-iv.
(d)P-iii, Q-ii, R-i, S-v.

GATE 2021 · Set 2Q9 · page 67 of the book

Consider a complete binary tree with 7 nodes. Let A
denote the set of first 3 elements obtained by
performing Breadth-First Search (BFS) starting from
the root. Let B denote the set of first 3 elements
obtained by performing Depth-First Search (DFS)
starting from the root.The value of |A – B| is

Self-check

Question 1

How many edge examinations does BFS make on an undirected connected graph with $V$ vertices and $E$ edges, using adjacency lists?

Show answer

$2E$ (each edge is in the lists of both ends), plus $V$ dequeues: $\Theta(V + E)$ .

Question 2

What does it mean for the intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ to be disjoint?

Show answer

Neither vertex is an ancestor of the other in the depth-first forest.

Question 3

How can you tell from a BFS two-colouring that a graph is not bipartite?

Show answer

An edge joins two vertices with the same colour: it closes an odd cycle.

Question 4

What is the time of DFS on a graph given as an adjacency matrix?

Show answer

$\Theta(V^2)$ : finding the neighbours of each vertex scans a whole row.

Revision card

One-screen revision

BFS: queue, distance in edges, levels, shortest paths unweighted, $\Theta(V + E)$ .
DFS: colours, times in $1 \ldots 2V$ , intervals nested or disjoint, white-path theorem, $\Theta(V + E)$ .
Matrix: $\Theta(V^2)$ . Mark when queuing. Order depends on the lists.
Uses: reachability, components, bipartiteness (odd cycle), cycles, spanning trees.

References

·Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd edition), Chapter 22 Elementary Graph Algorithms (22.2 breadth-first search, 22.3 depth-first search)
·Sedgewick and Wayne, Algorithms (4th edition), Section 4.1 Undirected Graphs
·Dasgupta, Papadimitriou, Vazirani, Algorithms, Chapter 3 Decompositions of graphs

Verification

BFS was compared with Floyd-Warshall distances on 500 random undirected graphs of up to 8 vertices (distances, the fact that an edge joins vertices at most one level apart, and exactly 2E edge examinations with adjacency lists); components were compared with union-find; bipartiteness by BFS colouring was compared with ALL 2^n colourings. DFS was checked on 1000 random graphs, directed and undirected: every time stamp 1 to 2V is used once, any two intervals are nested or disjoint (parenthesis theorem), v is a descendant of u exactly when it is reachable from u through vertices discovered after u (white-path theorem), and undirected graphs have no cross edges. The two animations and the table are real runs of the page's C code and were recomputed by independent searches. Textbook chapter references are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand or by a small script (loop counts, recurrences, merge and quicksort counts and averages, hash probes and load-factor formulas, DP tables, MST and shortest-path runs, Floyd matrices); long C programs were not re-read line by line (they are compiled and compared by npm run verify:c, and their printed outputs were checked against the prose); tables and animations are machine output and were read, not re-run; No other defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

DP on sequences: LIS and coin change

DFS edge types, topological sort and SCC