Graph Algorithms: Study Guide & Checklist
Based on DSA Lecture Notes
1 Graph Fundamentals & Representations
Topics Covered
- Graph Definition: Structure G = (V, E) where E ⊆ V × V .
- Graph Types:
- Simple Graph: No self-loops, multigraphs not allowed (at most one edge between
any pair).
- Directed vs. Undirected: Differentiate based on ordered pairs vs. sets.
- Representations:
- Adjacency Matrix: Aij = 1 if edge exists, 0 otherwise.
- Adjacency List: Array of linked lists. Preferred for sparse graphs.
- Space Complexity: Adjacency List takes Θ(V + E).
Study Checklist
Define a Graph and understand notation G = (V, E).
Differentiate between Directed and Undirected graphs.
Implement an Adjacency Matrix (Aij = 1 logic).
Implement an Adjacency List (Linked lists for vertices).
Analyze space complexity: Understand why lists are Θ(V + E) and when m ≈ n log n.
2 Graph Traversals
2.1 Breadth-First Search (BFS)
- Mechanism: Layer-based traversal using a Queue (FIFO).
- Vertex Attributes:
- Colors: White (Undiscovered), Gray (Discovered/In Queue), Black (Finished).
- Distance (d): Shortest path distance (number of edges) from source s.
- Parent (π): Predecessor in the BFS tree.
- Output: Computes shortest paths in unweighted graphs.
1
2.2 Depth-First Search (DFS)
- Mechanism: Recursive exploration (DFS-VISIT).
- Timestamps:
- Discovery time (u.d).
- Finish time (u.f ).
- Edge Classification:
- Tree Edges: Edges in the DFS forest.
- Back Edges: Connects to an ancestor (indicates a cycle).
- Forward Edges: Connects to a descendant.
- Cross Edges: All other edges (no ancestor/descendant relation).
- Key Theorems:
- Parenthesis Theorem: Time intervals [u.d, u.f ] are either disjoint or nested.
- White Path Theorem: Vertex v is a descendant of u iff there is a white path to v at
time u.d.
Study Checklist
BFS: Implement using a Queue.
BFS: Track vertex colors (White/Gray/Black).
DFS: Implement using recursion.
DFS: distinct between discovery (d) and finish (f ) times.
Edge Classification: Identify Tree, Back, Forward, and Cross edges.
Theorems: Verify the Parenthesis Theorem on a sample graph.
3 Graph Properties & Types
Topics Covered
- Connected Components:
- Undirected: Path exists between every pair in the set.
- Directed: Strongly Connected Components (SCC).
- Bipartite Graphs:
- Vertices can be partitioned into two sets X and Y such that all edges go between X
and Y .
- Condition: A graph is bipartite iff it contains no odd cycles.
2
Study Checklist
Define Connected Components and Strongly Connected Components.
Check if a graph is Bipartite (2-colorable).
Prove/Verify that a Bipartite graph cannot contain an odd cycle.
4 Applications: Topological Sort
Topics Covered
- Prerequisite: Directed Acyclic Graph (DAG).
- Algorithm: Run DFS, then order vertices by decreasing finish time (v.f ).
- Note: A DAG must have at least one vertex with in-degree 0.
Study Checklist
Verify the input graph is a DAG.
Perform Topological Sort by calculating DFS finish times.
5 Minimum Spanning Tree (MST)
Topics Covered
- Greedy Strategy: Connect all terminals with minimum total cost.
- Fundamental Properties:
- Cut Property: For any cut (S, V − S), the lightest edge crossing the cut is in the MST.
- Cycle Property: The heaviest edge in any cycle is not in the MST.
- Algorithms:
- Kruskal’s Algorithm: Sort edges by weight; add safe edges using Union-Find data
structure. Complexity: O(E log V ).
- Prim’s Algorithm: Grow the tree from a root vertex.
- Reverse Delete: Delete edges in decreasing order of weight unless disconnecting
the graph.
Study Checklist
State the Cut Property and Cycle Property.
Trace Kruskal’s Algorithm on a sample graph.
Trace Prim’s Algorithm on a sample graph.
Understand the role of Union-Find in Kruskal’s.
3
6 Shortest Path Algorithms
Topics Covered
- Concepts:
- Optimal Substructure: Subpaths of shortest paths are shortest paths.
- Relaxation: Relax(u, v, w): if v.d > u.d + w(u, v), update v.d and set v.π = u.
- Algorithms:
- Dijkstra’s Algorithm: Greedy approach. Uses a Priority Queue (Q). Requires non-
negative edge weights.
- Bellman-Ford Algorithm: Can handle negative edge weights. Based on dynamic
programming principles.
Study Checklist
Explain the concept of Relaxation.
Trace Dijkstra’s Algorithm using a Priority Queue.
Identify why Dijkstra fails with negative edge weights.
Understand the distinction between Dijkstra and Bellman-Ford.