chapter
    Graph Traversal: BFS and DFS Short Notes for GATE DA

    Graph Traversal: BFS and DFS short notes for GATE DA: 3 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    graph traversal bfs and dfs short notes

    Quick Recap: Reachability

    Core Principles

    Asymmetry: In directed graphs, does not imply .

    Reverse Graph (): Flipping edges turns "reachable from" into "can reach".

    SCC Intersection: .

    Algorithm Equivalence: BFS and DFS discover the exact same reachable set from a source.

    Path vs Existence: Reachability only guarantees a path exists. Only BFS guarantees the shortest path in unweighted graphs.

    Scope: One traversal = single-source reachability. traversals = transitive closure.

    Quick Recap: DFS Edge Classification

    Core Principles

    Parenthesis Theorem: Time intervals are either strictly nested or completely disjoint.

    Tree Edge: (and discovered via ).

    Back Edge: (indicates a cycle).

    Forward Edge: (but not discovered via ).

    Cross Edge: (disjoint intervals).

    Undirected Rule: DFS on undirected graphs yields only Tree and Back edges.

    Quick Recap: Visual Tracing Checklist

    Visual Tracing Checklist

    Workspace: Always use a trace table and explicitly draw the Queue (BFS) or Stack (DFS).
    Degree Check: Count the degrees of all vertices before starting to ensure no edges are missed.
    Ordering: Pre-sort adjacency lists if the question specifies an ordering constraint.
    BFS Signature: Expands level-by-level. All distance vertices are visited before distance .
    DFS Signature: Dives deep. Explores a single path as far as possible before backtracking.
    Strictness: Follow the exact neighbor order specified; any deviation ruins the trace.

    Try a question

    Answer it here to see how it works. Nothing is recorded until you sign in.

    Question 1
    Level 1: Warm-up

    Which of the following statements correctly defines the Strongly Connected Component (SCC) of a vertex in a directed graph?

    Question 2
    Level 1: Warm-up

    Which of the following statements about the edges produced by a Depth First Search on a simple undirected graph is ALWAYS true?

    Question 3
    Level 1: Warm-up

    Which of the following edge types is mathematically impossible to produce during a Depth First Search on any simple undirected graph?

    Question 4
    Level 1: Warm-up

    During a Depth First Search on a directed graph, the presence of which edge type is both necessary and sufficient to conclude that the graph contains at least one directed cycle?

    Question 5
    Level 1: Warm-up

    A student performs a Depth First Search on a simple undirected graph and reports the following edge classification:

    • Tree edges: 3
    • Back edges: 2
    • Forward edges: 1
    • Cross edges: 0

    What is the MINIMUM number of edges that the student MUST have misclassified?

    Question 6
    Level 1: Warm-up

    Which of the following sets of discovery and finish timestamps is mathematically IMPOSSIBLE for a valid Depth First Search on a directed graph?

    Question 7
    Level 1: Warm-up

    Which of the following statements about the intersection of the forward and backward reachable sets from a vertex in a directed graph is ALWAYS true?

    Question 8
    Level 1: Warm-up

    During a Depth First Search on a simple undirected graph, the edge is explored from and vertex is found to be already visited. Which of the following must be true about ?

    Question 9
    Level 1: Warm-up

    During a Depth First Search on a directed graph with 6 vertices and 10 edges, the edge classification yields:

    • Tree edges: 4
    • Back edges: 3
    • Forward edges: 1
    • Cross edges: ?

    How many Cross edges are there?

    Question 10
    Level 1: Warm-up

    During a Depth First Search on a simple undirected graph with 8 vertices, the algorithm discovers exactly 7 Tree edges. What is the maximum possible number of Back edges that can be generated in this graph?

    Free preview ends here

    Login to view the complete short notes

    Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

    Login to continueSee plans
    Why MastersUp

    Personalised first. High quality throughout.

    Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

    Built around you, not around a syllabus PDF

    Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

    Revision that hits your weak spots

    We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

    Questions calibrated to the real exam

    Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

    Notes written for recall, not for volume

    Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

    One place for everything

    Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

    Honest progress

    No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

    Unlock the whole course

    Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

    View all plansStart free

    Graph Traversal: BFS and DFS Short Notes for GATE DA

    Graph Traversal: BFS and DFS short notes for GATE DA: 3 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

    Quick Recap: Reachability

    Core Principles

    Asymmetry: In directed graphs, does not imply .

    Reverse Graph (): Flipping edges turns "reachable from" into "can reach".

    SCC Intersection: .

    Algorithm Equivalence: BFS and DFS discover the exact same reachable set from a source.

    Path vs Existence: Reachability only guarantees a path exists. Only BFS guarantees the shortest path in unweighted graphs.

    Scope: One traversal = single-source reachability. traversals = transitive closure.

    Quick Recap: DFS Edge Classification

    Core Principles

    Parenthesis Theorem: Time intervals are either strictly nested or completely disjoint.

    Tree Edge: (and discovered via ).

    Back Edge: (indicates a cycle).

    Forward Edge: (but not discovered via ).

    Cross Edge: (disjoint intervals).

    Undirected Rule: DFS on undirected graphs yields only Tree and Back edges.

    Quick Recap: Visual Tracing Checklist

    Visual Tracing Checklist

    Workspace: Always use a trace table and explicitly draw the Queue (BFS) or Stack (DFS).
    Degree Check: Count the degrees of all vertices before starting to ensure no edges are missed.
    Ordering: Pre-sort adjacency lists if the question specifies an ordering constraint.
    BFS Signature: Expands level-by-level. All distance vertices are visited before distance .
    DFS Signature: Dives deep. Explores a single path as far as possible before backtracking.
    Strictness: Follow the exact neighbor order specified; any deviation ruins the trace.

    Graph Traversal: BFS and DFS: Solved Questions with Step-by-Step Explanations (10 Problems)

    Question 1 · Programming, Data Structures and Algorithms MCQ

    Which of the following statements correctly defines the Strongly Connected Component (SCC) of a vertex in a directed graph?

    1. A.

      The union of forward and backward reachable sets from

    2. B.

      The intersection of forward and backward reachable sets from

    3. C.

      The set of all vertices that can reach

    4. D.

      The set of all vertices reachable from

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: This is a direct definition recall question about SCCs.

    Step 1: Recall the definition of Strongly Connected Component.

    Step 2: An SCC is a maximal set of vertices where every vertex is reachable from every other vertex.

    Step 3: For vertex , this means:

    • can reach them (forward reachable)
    • They can reach (backward reachable)

    Step 4: Therefore, SCC() = forward reachable set backward reachable set.

    Answer: The intersection of forward and backward reachable sets from

    Question 2 · Programming, Data Structures and Algorithms MCQ

    Which of the following statements about the edges produced by a Depth First Search on a simple undirected graph is ALWAYS true?

    1. A.

      It can produce Cross edges if the graph is disconnected.

    2. B.

      It can produce Forward edges if the graph contains cycles.

    3. C.

      It will only produce Tree and Back edges.

    4. D.

      It will only produce Tree and Cross edges.

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: This is a bounding question testing the fundamental rule of DFS on undirected graphs.

    Step 1: Recall the theorem for undirected graphs. When DFS is performed on an undirected graph, every edge is explored in both directions.

    Step 2: If an edge is explored and is already visited, must be an ancestor of . If were in a different branch, the edge would have been traversed from to earlier, making a descendant of .

    Step 3: Therefore, any non-tree edge in an undirected graph must be a Back edge. Forward and Cross edges are mathematically impossible.

    Step 4: Evaluate the options. Option C correctly states that only Tree and Back edges are produced, regardless of cycles or connectivity.

    Answer: It will only produce Tree and Back edges.

    Question 3 · Programming, Data Structures and Algorithms MCQ

    Which of the following edge types is mathematically impossible to produce during a Depth First Search on any simple undirected graph?

    1. A.

      Tree edge

    2. B.

      Back edge

    3. C.

      Forward edge

    4. D.

      Both A and B

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: This is a bounding question testing the fundamental rule of DFS on undirected graphs.

    Step 1: Recall the theorem for undirected graphs. When DFS explores an edge in an undirected graph, the reverse edge also exists.

    Step 2: If is already visited when is explored, must be an ancestor of . If were in a different branch, the edge would have been traversed from to earlier.

    Step 3: Therefore, any non-tree edge in an undirected graph must be a Back edge. Forward and Cross edges are mathematically impossible.

    Step 4: Evaluate the options. Forward edge is the only correct choice among the single types.

    Answer: Forward edge

    Question 4 · Programming, Data Structures and Algorithms MCQ

    During a Depth First Search on a directed graph, the presence of which edge type is both necessary and sufficient to conclude that the graph contains at least one directed cycle?

    1. A.

      Back edge

    2. B.

      Tree edge

    3. C.

      Forward edge

    4. D.

      Cross edge

    Correct Answer:

    A

    Step-by-Step Solution

    Key idea: This is an observation question testing the fundamental relationship between Back edges and cycles.

    Step 1: Recall the definition of a Back edge. It is an edge where is an ancestor of in the DFS tree.

    Step 2: If is an ancestor of , there is a tree path from down to . The Back edge completes this into a cycle: .

    Step 3: Conversely, if the graph has a cycle, DFS must produce at least one Back edge. No other edge type guarantees a cycle.

    Step 4: Therefore, Back edges are both necessary and sufficient for cycles.

    Answer: Back edge

    Question 5 · Programming, Data Structures and Algorithms NAT

    A student performs a Depth First Search on a simple undirected graph and reports the following edge classification:

    • Tree edges: 3
    • Back edges: 2
    • Forward edges: 1
    • Cross edges: 0

    What is the MINIMUM number of edges that the student MUST have misclassified?

    Correct Answer:

    1.00

    Step-by-Step Solution

    Key idea: In an undirected graph, DFS produces ONLY Tree edges and Back edges. Forward and Cross edges are mathematically impossible.

    Step 1: Recall the rule for undirected graphs: DFS yields only Tree and Back edges. No Forward or Cross edges can exist.

    Step 2: Check the student's report:

    • Tree edges: 3 (possible ✓)
    • Back edges: 2 (possible ✓)
    • Forward edges: 1 (IMPOSSIBLE ✗)
    • Cross edges: 0 (possible ✓)

    Step 3: The Forward edge is impossible in an undirected graph. It must be misclassified (likely as a Tree or Back edge).

    Step 4: Count misclassified edges: At least 1 edge (the Forward edge) must be wrong.

    Answer: 1

    Question 6 · Programming, Data Structures and Algorithms MCQ

    Which of the following sets of discovery and finish timestamps is mathematically IMPOSSIBLE for a valid Depth First Search on a directed graph?

    1. A.

    2. B.

    3. C.

    4. D.

    Correct Answer:

    C

    Step-by-Step Solution

    Key idea: The Parenthesis Theorem states that DFS time intervals must be either completely disjoint or strictly nested. Partial overlap is impossible.

    Step 1: Check Option A: , , . and are nested inside , and disjoint from each other. Valid.

    Step 2: Check Option B: , , . All are strictly nested. Valid.

    Step 3: Check Option C: , . starts before , but finishes before finishes (). This is a partial overlap. Invalid.

    Step 4: Check Option D: , , . All are completely disjoint. Valid.

    Answer: Option C

    Question 7 · Programming, Data Structures and Algorithms MCQ

    Which of the following statements about the intersection of the forward and backward reachable sets from a vertex in a directed graph is ALWAYS true?

    1. A.

      The intersection is empty if has no incoming edges.

    2. B.

      The intersection contains at least the vertex itself.

    3. C.

      The intersection size is equal to the number of tree edges in the DFS.

    4. D.

      The intersection includes all vertices in the weakly connected component of .

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: This is a statement truth question about SCC intersection properties.

    Step 1: The SCC of is defined as .

    Step 2: By definition, can reach itself (path of length 0), so .

    Step 3: Similarly, can reach itself, so .

    Step 4: Therefore, is always in the intersection, meaning the intersection is never empty and contains at least .

    Step 5: Evaluate options: A is false (intersection always has ). B is true. C is false (no relation to tree edges). D is false (weak component can be larger).

    Answer: The intersection contains at least the vertex itself.

    Question 8 · Programming, Data Structures and Algorithms MCQ

    During a Depth First Search on a simple undirected graph, the edge is explored from and vertex is found to be already visited. Which of the following must be true about ?

    1. A.

      is a descendant of in the DFS tree

    2. B.

      is an ancestor of in the DFS tree

    3. C.

      belongs to a different DFS tree from

    4. D.

      has a larger discovery time than

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: This is a bounding question testing the structural reason why undirected DFS only produces Tree and Back edges.

    Step 1: The graph is undirected, so edge implies edge also exists.

    Step 2: Since is already visited when is explored from , DFS must have reached earlier.

    Step 3: Because the graph is undirected, when DFS first visited , it would have explored the edge . If was unvisited at that time, DFS would have discovered as a child of , making a descendant of .

    Step 4: This means is an ancestor of in the DFS tree. The edge is therefore a Back edge.

    Step 5: The other options are impossible: cannot be a descendant (it was visited before explored this edge), cannot be in a different tree (the undirected edge connects them), and must have a smaller discovery time (visited earlier).

    Answer: is an ancestor of in the DFS tree

    Question 9 · Programming, Data Structures and Algorithms NAT

    During a Depth First Search on a directed graph with 6 vertices and 10 edges, the edge classification yields:

    • Tree edges: 4
    • Back edges: 3
    • Forward edges: 1
    • Cross edges: ?

    How many Cross edges are there?

    Correct Answer:

    2.00

    Step-by-Step Solution

    Key idea: The total number of edges equals the sum of all edge types.

    Step 1: Recall that every edge in a directed graph DFS is classified as exactly one type: Tree, Back, Forward, or Cross.

    Step 2: Set up the equation: Total edges = Tree + Back + Forward + Cross

    Step 3: Substitute known values:

    Step 4: Solve for Cross:

    Answer: 2

    Question 10 · Programming, Data Structures and Algorithms MCQ

    During a Depth First Search on a simple undirected graph with 8 vertices, the algorithm discovers exactly 7 Tree edges. What is the maximum possible number of Back edges that can be generated in this graph?

    1. A.

      20

    2. B.

      21

    3. C.

      27

    4. D.

      28

    Correct Answer:

    B

    Step-by-Step Solution

    Key idea: In an undirected graph, every edge is either a Tree edge or a Back edge. The maximum number of edges in a simple graph limits the Back edges.

    Step 1: Recall that for a simple undirected graph with vertices, the maximum number of edges is .

    Step 2: Calculate max edges for : .

    Step 3: Recall that every edge is classified as either Tree or Back. So, .

    Step 4: We are given . To maximize Back edges, we must maximize Total edges.

    Step 5: Max Back edges = Max Total edges - Tree edges = .

    Answer: Option B

    More short notes in this unit