Graphs

BFS, DFS, Topological Sort, Strongly Connected Components, Dijkstra's Algorithm

Graph Representations

Key Concepts:

  • Adjacency Matrix: 2D array, O(1) edge lookup, O(VĀ²) space
  • Adjacency List: Array of lists, O(V+E) space, better for sparse graphs
  • When to use which: Matrix for dense graphs, lists for sparse

Practice Tip:

Draw a simple graph and convert it between both representations. This is a common exam question!

Breadth-First Search (BFS)

Key Concepts:

  • Uses Queue (FIFO) - explores level by level
  • Time Complexity: O(V + E) with adjacency list
  • Space Complexity: O(V) for queue and visited array
  • Applications: Shortest path in unweighted graphs, level-order traversal
  • Output: BFS tree, distances from source

Video Recommendations:

šŸŽ„ Abdul Bari - BFS Graph Traversal (17 min) šŸŽ„ William Fiset - BFS Shortest Path (13 min)

Walkthrough:

  1. Initialize: Mark source as visited, enqueue source
  2. While queue not empty: dequeue vertex u
  3. For each neighbor v of u: if not visited, mark visited, enqueue v, set distance[v] = distance[u] + 1
  4. Result: All reachable vertices visited, shortest paths computed

šŸ“Š Visual Example: BFS Traversal

A Level 0 B Level 1 C Level 1 D E F G H Level 2: D, E, F, G Level 3: H
Starting node (Level 0)
Level 1
Level 2
Level 3

BFS Order from A: A ā†’ B ā†’ C ā†’ D ā†’ E ā†’ F ā†’ G ā†’ H

Queue progression: [A] ā†’ [B,C] ā†’ [C,D,E] ā†’ [D,E,F,G] ā†’ [E,F,G] ā†’ [F,G,H] ā†’ [G,H] ā†’ [H] ā†’ []

āœļø Trace Exercise: Practice BFS

Try this yourself: Given the graph above, what would be the BFS traversal starting from node C?

Answer: C ā†’ B ā†’ A ā†’ F ā†’ G ā†’ D ā†’ E ā†’ H

Explanation:

  • Level 0: C (start)
  • Level 1: B, F, G (neighbors of C)
  • Level 2: A (neighbor of B), D, E (neighbors of B and F)
  • Level 3: H (neighbor of E)

Queue: [C] ā†’ [B,F,G] ā†’ [F,G,A] ā†’ [G,A,D,E] ā†’ [A,D,E] ā†’ [D,E] ā†’ [E,H] ā†’ [H] ā†’ []

šŸ§  Quick Quiz: Test Your BFS Understanding

Q1: What data structure does BFS use?

A) Stack
B) Queue
C) Priority Queue
D) Hash Table
Correct! BFS uses a Queue (FIFO - First In First Out) to process vertices level by level. This is the key difference from DFS which uses a stack or recursion.

Q2: In an unweighted graph, BFS finds:

A) The longest path
B) The shortest path
C) All possible paths
D) The minimum spanning tree
Correct! BFS guarantees the shortest path in unweighted graphs because it explores nodes level by level, reaching closer nodes first.

Q3: What is the space complexity of BFS?

A) O(1)
B) O(E)
C) O(V)
D) O(VĀ²)
Correct! Space complexity is O(V) for the queue and visited array. In the worst case, all vertices might be in the queue at once.

šŸŽÆ Self-Check: Can You Explain?

Try explaining these in your own words (cover the answer first!):

  1. Why does BFS use a queue instead of a stack?
    A queue ensures FIFO (First-In-First-Out) ordering, which means we process vertices in the order we discover them. This guarantees we explore all vertices at distance d before exploring vertices at distance d+1, which is why BFS finds shortest paths.
  2. When would you choose BFS over DFS?
    Choose BFS when: (1) You need shortest paths in unweighted graphs, (2) You want to explore nearby nodes first, (3) The solution is likely near the start node. Choose DFS when: (1) You want to explore all paths, (2) Need topological sorting, (3) Detecting cycles, (4) Memory is limited (DFS uses less space in most cases).

Depth-First Search (DFS)

Key Concepts:

  • Uses Stack (LIFO) or recursion - explores as deep as possible first
  • Time Complexity: O(V + E)
  • Space Complexity: O(V) for recursion stack
  • Timestamps: Discovery time d[v] and finish time f[v]
  • Applications: Cycle detection, topological sort, SCC, path finding
  • Edge Classification: Tree, Back, Forward, Cross edges

Video Recommendations:

šŸŽ„ Abdul Bari - DFS Graph Traversal (17 min) šŸŽ„ MIT OpenCourseWare - DFS and Topological Sort (50 min - if time)

Common Pitfall:

Remember: DFS on an undirected graph only has tree and back edges. Forward and cross edges only appear in directed graphs!

Topological Sort

Key Concepts:

  • Only for DAGs (Directed Acyclic Graphs)
  • Linear ordering: If edge uā†’v exists, u appears before v
  • Algorithm: DFS-based - add vertices in reverse finish time order
  • Time Complexity: O(V + E)
  • Cycle Detection: If back edge found, graph has cycle (no topological sort possible)

Video Recommendations:

šŸŽ„ William Fiset - Topological Sort (15 min)

Quick Algorithm:

  1. Run DFS on entire graph
  2. When vertex finishes (all descendants explored), push to stack
  3. Pop stack to get topological order

Strongly Connected Components (SCC)

Key Concepts:

  • SCC: Maximal set of vertices where every vertex is reachable from every other
  • Kosaraju's Algorithm: Most common approach
  • Time Complexity: O(V + E) - two DFS passes
  • Steps: (1) DFS on G to compute finish times, (2) DFS on G^T (transpose) in decreasing finish time order

Video Recommendations:

šŸŽ„ Tushar Roy - Strongly Connected Components (16 min)

Walkthrough:

  1. Run DFS on original graph G, record finish times
  2. Compute transpose G^T (reverse all edges)
  3. Run DFS on G^T in decreasing finish time order
  4. Each DFS tree in step 3 is one SCC

Dijkstra's Algorithm (Single-Source Shortest Path)

Key Concepts:

  • Requirement: Non-negative edge weights only!
  • Greedy approach: Always pick minimum distance unvisited vertex
  • Time Complexity: O((V+E) log V) with min-heap, O(VĀ²) with array
  • Output: Shortest paths from source to all vertices
  • Relaxation: If d[v] > d[u] + w(u,v), update d[v]

Video Recommendations:

šŸŽ„ Abdul Bari - Dijkstra's Algorithm (15 min) šŸŽ„ William Fiset - Dijkstra's Shortest Path (12 min)

Critical to Remember:

Dijkstra's FAILS with negative weights! Use Bellman-Ford for negative weights (though this might not be on your exam based on syllabus).

Algorithm Steps:

  1. Initialize: d[source] = 0, d[all others] = āˆž, min-heap with all vertices
  2. While heap not empty: extract min vertex u
  3. For each neighbor v of u: relax edge (u,v)
  4. Update heap if distance improved

Graph Algorithms Quick Reference

Algorithm Time Complexity Space Key Use
BFS O(V + E) O(V) Shortest path (unweighted)
DFS O(V + E) O(V) Cycle detection, topological sort
Topological Sort O(V + E) O(V) Task scheduling (DAGs only)
SCC (Kosaraju) O(V + E) O(V) Find strongly connected components
Dijkstra O((V+E) log V) O(V) Shortest path (non-negative weights)

Interactive BFS/DFS Practice - Fill in the Order!

Based on ps1: Click vertices in the order they would be visited. Test your understanding!

Exercise 1: Breadth-First Search (Starting from A)

Instructions: Click vertices in the order BFS would visit them starting from node A. When multiple nodes can be enqueued, choose alphabetically.

A B C D E F G H
Your BFS order: Click on A to start...

Correct BFS Order from A:

A ā†’ B ā†’ F ā†’ H ā†’ D ā†’ E ā†’ C ā†’ G

Step-by-Step Explanation:
  1. Start at A: Enqueue A, mark as visited
  2. Process A: Neighbors are B, F, H (alphabetically: B, F, H). Enqueue all three.
  3. Queue: [B, F, H]
  4. Process B: Dequeue B. Neighbor is D. Enqueue D.
  5. Queue: [F, H, D]
  6. Process F: Dequeue F. Neighbor is E. Enqueue E.
  7. Queue: [H, D, E]
  8. Process H: Dequeue H. Neighbors are C, E (E already visited). Enqueue C.
  9. Queue: [D, E, C]
  10. Process D: Dequeue D. Neighbor is G. Enqueue G.
  11. Queue: [E, C, G]
  12. Process E, C, G: No new unvisited neighbors.

Remember: When multiple nodes are at the same level, enqueue alphabetically!

Exercise 2: Depth-First Search (Starting from A)

Instructions: Click vertices in the order DFS would visit them starting from node A. When multiple nodes can be explored, choose alphabetically.

A B C D E F G H
Your DFS order: Click on A to start...

Correct DFS Order from A:

A ā†’ B ā†’ D ā†’ G ā†’ F ā†’ E ā†’ H ā†’ C

Step-by-Step Explanation:
  1. Start at A: Mark A as visited. Neighbors: B, F, H (alphabetically)
  2. Visit B (first alphabetically): From A ā†’ B. Neighbor: D
  3. Visit D: From B ā†’ D. Neighbor: G
  4. Visit G: From D ā†’ G. No unvisited neighbors, backtrack to D, then B, then A
  5. Visit F (next alphabetically from A): From A ā†’ F. Neighbor: E
  6. Visit E: From F ā†’ E. No unvisited neighbors, backtrack to F, then A
  7. Visit H (last from A): From A ā†’ H. Neighbors: C, E (E already visited)
  8. Visit C: From H ā†’ C. Neighbors already visited (D, G)

Stack trace: A ā†’ [B,F,H] ā†’ B ā†’ [D] ā†’ D ā†’ [G] ā†’ G ā†’ backtrack ā†’ F ā†’ [E] ā†’ E ā†’ backtrack ā†’ H ā†’ [C] ā†’ C ā†’ done

DFS explores as deep as possible before backtracking!

Key Differences:

  • BFS Order: A ā†’ B ā†’ F ā†’ H ā†’ D ā†’ E ā†’ C ā†’ G (explores level-by-level)
  • DFS Order: A ā†’ B ā†’ D ā†’ G ā†’ F ā†’ E ā†’ H ā†’ C (explores depth-first)

BFS uses a Queue (FIFO - processes closest nodes first), while DFS uses a Stack/Recursion (LIFO - goes as deep as possible first).

Both visit all reachable nodes, but in very different orders!