Quartz 4

7.0 Graphs

1 min read

Graphs

Graphs represent relationships and connectivity — foundational for traversal, search, cycles, and dependency resolution problems.

1.0 Graph Traversals

  1. BFS (level order, shortest path in unweighted)
  2. DFS (recursion + stack)
  3. Connected components

2.0 Directed Graphs and Topological Sort

  1. Kahn’s Algorithm (BFS)
  2. DFS-based topo sort
  3. Cycle detection in directed graphs

3.0 Undirected Graphs and Cycle Detection

  1. Union-Find / DSU
  2. DFS with parent tracking
  3. Bipartite check (BFS coloring)

4.0 Shortest Path Algorithms

  1. Dijkstra (min-heap based)
  2. Bellman-Ford (negative weights)
  3. A* Search (heuristics)

5.0 MST and Spanning Trees

  1. Prim’s Algorithm
  2. Kruskal’s Algorithm
  3. Disjoint Set Union applications

6.0 Grid-Based Graphs

  1. Word search, island count
  2. Flood fill and BFS
  3. Multi-source BFS (rotting oranges)

7.0 Backtracking and Constraint Solving on Graphs

  1. N-Queens
  2. Sudoku
  3. Hamiltonian Path (TSP, exhaustive)

8.0 Advanced Graph Topics

  1. Articulation points and bridges
  2. Tarjan’s algorithm (SCC)
  3. Top K shortest paths (Yen’s algorithm)

Graph View

Backlinks