CSE310 Exam Review

Advanced DFS Topics (Parts 5-8)

Advanced DFS Topics

This interactive review covers three advanced depth-first search topics critical for your exam:

🔍 Module 1

DFS on Directed Graphs

Master DFS algorithm on directed graphs with discovery and finish times, DFS forest construction, and key theorems.

  • White-Path Theorem
  • Parenthesis Theorem
  • Nesting of Intervals
  • Step-by-step execution

🎨 Module 2

Edge Classification

Learn to classify edges as tree, back, forward, or cross edges during and after DFS execution.

  • Four edge types
  • Classification rules
  • Timestamp analysis
  • Cycle detection

📊 Module 3

Topological Sort

Understand DAGs and compute topological orderings using DFS with finish-time ordering.

  • DAG properties
  • Finish-time ordering
  • Correctness proof
  • Applications

📚 How to Use This Review

  1. Select a module from the cards or tabs
  2. Study the theory and key concepts
  3. Step through interactive visualizations
  4. Test yourself with practice questions
  5. Review solutions with detailed explanations

Module 1: DFS on Directed Graphs

Theory Overview

Depth-First Search on directed graphs extends the basic DFS algorithm with additional properties and theorems that help analyze graph structure.

DFS Algorithm

DFS(G): for each vertex u ∈ G.V: color[u] = WHITE π[u] = NIL time = 0 for each vertex u ∈ G.V: if color[u] = WHITE: DFS-Visit(G, u) DFS-Visit(G, u): time = time + 1 // discovery time d[u] = time color[u] = GRAY for each v ∈ Adj[u]: // explore edges if color[v] = WHITE: π[v] = u DFS-Visit(G, v) color[u] = BLACK time = time + 1 // finish time f[u] = time
Key Concepts:
  • Discovery time d[u]: When vertex u is first discovered (turns GRAY)
  • Finish time f[u]: When exploration from u is complete (turns BLACK)
  • Invariant: For all vertices u, we have d[u] < f[u]
  • Time range: 1 ≤ d[u] < f[u] ≤ 2|V|

Key Theorems

White-Path Theorem

Vertex v is a descendant of u in the DFS forest if and only if at time d[u], there exists a white path from u to v (a path consisting entirely of white vertices).

Parenthesis Theorem

For any two vertices u and v, exactly one of the following holds:

  • Intervals [d[u], f[u]] and [d[v], f[v]] are disjoint (neither is descendant of other)
  • Interval [d[u], f[u]] is contained in [d[v], f[v]] (u is descendant of v)
  • Interval [d[v], f[v]] is contained in [d[u], f[u]] (v is descendant of u)

Nesting of Intervals

Vertex v is a proper descendant of u if and only if d[u] < d[v] < f[v] < f[u].

Interactive DFS Walkthrough

Problem: Run DFS on the directed graph with vertices {a,b,c,x,y,z} starting from vertex 'a'.
Step 1 of 15
Starting DFS from vertex a
Initialize: All vertices WHITE, time = 0
WHITE (undiscovered)
GRAY (discovered)
BLACK (finished)

Practice Questions

Q1: Trace DFS Execution

Question: Given a directed graph with vertices {s,t,u,v} and edges s→t, s→u, t→v, u→v, v→t, trace DFS starting from s. Show all discovery and finish times.

Q2: White-Path Theorem Application

Question: Using the DFS from the interactive walkthrough, explain why y is a descendant of a using the White-Path Theorem.

Q3: Parenthesis Theorem Analysis

Question: Given timestamps a:[1/8], b:[2/5], x:[6/7], determine the relationship between these vertices using the Parenthesis Theorem.

Module 2: Edge Classification

Theory Overview

DFS can classify every edge in a directed graph into one of four types based on the color of the destination vertex when the edge is explored.

Four Edge Types

Tree Edge

Edge (u,v) where v is WHITE when explored. These edges form the DFS forest.

Rule: color[v] = WHITE when examining (u,v)

Back Edge

Edge (u,v) where v is GRAY when explored. Points to an ancestor in DFS tree. Indicates a cycle!

Rule: color[v] = GRAY when examining (u,v)

Forward Edge

Edge (u,v) where v is BLACK and v is a descendant of u. Points from ancestor to descendant (non-tree edge).

Rule: color[v] = BLACK and d[u] < d[v] < f[v] < f[u]

Cross Edge

Edge (u,v) where v is BLACK but v is not a descendant of u. All other edges.

Rule: color[v] = BLACK and intervals disjoint

Important Facts:
  • In an undirected graph, only tree and back edges exist
  • In a directed graph, all four edge types can exist
  • Back edges indicate cycles in the graph
  • A DAG (Directed Acyclic Graph) has no back edges

Classification Using Timestamps

For edge (u,v) after DFS completion: if d[u] < d[v] < f[v] < f[u]: // v's interval nested in u's if (u,v) was used in DFS: TREE EDGE else: FORWARD EDGE else if d[v] < d[u] < f[u] < f[v]: // u's interval nested in v's BACK EDGE else: // intervals disjoint CROSS EDGE

Interactive Edge Classification

Problem: Using the completed DFS from Module 1, classify each of the 8 edges in the graph.
Edge 1 of 8
Classifying edge (a,b)
Edge (a,b): b is WHITE when explored from a → Tree Edge
Tree Edge
Back Edge
Forward Edge
Cross Edge

Practice Questions

Q1: Classify All Edges

Question: Given a directed graph with DFS timestamps: a:[1/10], b:[2/5], c:[6/9], d:[3/4], e:[7/8]. Edges: (a,b), (a,c), (b,d), (c,e), (d,b). Classify each edge.

Q2: Cycle Detection

Question: Explain how to detect a cycle in a directed graph using DFS. Why do back edges indicate cycles?

Q3: Undirected Graphs

Question: In an undirected graph, why are there only tree and back edges? Why can't forward or cross edges exist?

Module 3: Topological Sort

Theory Overview

Directed Acyclic Graph (DAG)

A DAG is a directed graph with no cycles. Many real-world problems naturally form DAGs:

  • Task scheduling: Tasks with dependencies (must do A before B)
  • Course prerequisites: Take Data Structures before Algorithms
  • Build systems: Compile dependencies in correct order
  • Inheritance hierarchies: Class inheritance in programming

Topological Sort Definition

Topological Sort:

A linear ordering of vertices such that for every directed edge (u,v), vertex u appears before vertex v in the ordering.

Example: If tasks have dependencies A→B, A→C, B→D, C→D, one valid ordering is: A, B, C, D (or A, C, B, D)

Algorithm

Topological-Sort(G): 1. Call DFS(G) to compute finish times f[v] for all v 2. As each vertex is finished (turns BLACK), insert it at the FRONT of a linked list 3. Return the linked list of vertices Alternatively: 1. Call DFS(G) to compute finish times 2. Sort vertices by decreasing finish time 3. Return the sorted list

Key insight: If edge (u,v) exists, then f[u] > f[v] (u finishes after v). By ordering vertices by decreasing finish time, we ensure u appears before v.

Correctness

Why it works:

For any edge (u,v) in a DAG:

  1. When we explore (u,v), vertex v can be:
    • WHITE: We visit v, complete its subtree, then finish v before finishing u. So f[v] < f[u]. ✓
    • GRAY: Would be a back edge → cycle! But we have a DAG, so this can't happen.
    • BLACK: We already finished v, so f[v] < f[u]. ✓
  2. In all cases: f[v] < f[u], so u appears before v in decreasing finish time order
Important Properties:
  • Topological sort is only defined for DAGs
  • If graph has a cycle, topological sort is impossible
  • A DAG may have multiple valid topological orderings
  • Time complexity: O(V + E) (same as DFS)

Interactive Topological Sort

Problem: Compute topological sort for course prerequisite DAG. Courses must be taken in an order that respects all prerequisites.
Step 1 of 15
Starting DFS from CS100
Initialize: All courses undiscovered, topological order = []
WHITE
GRAY
BLACK

Practice Questions

Q1: Compute Topological Sort for New Course Set

Question: Given a new course DAG with courses {CS150, CS220, CS240, CS350} and prerequisites: CS150→CS220, CS150→CS240, CS220→CS350, CS240→CS350. Compute a topological sort showing the DFS process and final valid course sequence.

Q2: Adding a Cycle to Prerequisites

Question: If we add an edge CS400→CS100 to the course prerequisite graph, what happens? Why can't we perform topological sort? Explain in the context of course prerequisites.

Q3: Prerequisite Property Proof

Question: Prove that if edge (u,v) exists in a DAG (representing "u is prerequisite for v"), then u appears before v in any topological ordering. Use the course prerequisite context.