Graph algorithms are a set of techniques used to solve problems that can be modeled using graphs, which are collections of nodes (vertices) connected by edges. They are fundamental in computer science and are used to represent networks, relationships, and various other structured data.

Core Idea:

Graphs consist of vertices (nodes) and edges that connect pairs of vertices. Edges can be directed (one-way) or undirected (two-way) and can have weights (costs). Graph algorithms explore the structure and properties of these graphs to find paths, connectivity, cycles, shortest paths, and more.

Common Scenarios & How it Works:

  1. Traversal (Exploring the Graph):
    • Breadth-First Search (BFS): Explores the graph layer by layer. Ideal for finding the shortest path in unweighted graphs. Uses a queue.
    • Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Useful for pathfinding, cycle detection, and topological sorting. Uses a stack (often implicitly via recursion).
  2. Shortest Path Algorithms:
    • Dijkstra’s Algorithm: Finds the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights. Uses a priority queue.
    • Bellman-Ford Algorithm: Finds the shortest path from a single source node to all other nodes in a weighted graph, even with negative edge weights. Can detect negative cycles.
    • Floyd-Warshall Algorithm: Finds the shortest paths between all pairs of nodes in a weighted graph.
  3. Minimum Spanning Tree (MST): Finds a subset of edges that connects all vertices in an undirected, weighted graph with the minimum possible total edge weight, without forming any cycles.
    • Prim’s Algorithm: Grows the MST from an arbitrary starting vertex by iteratively adding the cheapest edge connecting a vertex in the MST to a vertex outside it.
    • Kruskal’s Algorithm: Sorts all edges by weight and adds them to the MST if they don’t form a cycle. Often uses a Union-Find data structure.
  4. Connectivity:
    • Connected Components (Undirected Graphs): Finding sets of vertices where each vertex is reachable from every other vertex in the same set. DFS or BFS can be used.
    • Strongly Connected Components (Directed Graphs): Finding maximal subgraphs where every vertex is reachable from every other vertex within that subgraph. Tarjan’s algorithm or Kosaraju’s algorithm are common.

  5. Topological Sort (Directed Acyclic Graphs - DAGs): Linear ordering of vertices such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. Often used for scheduling tasks with dependencies. Can be implemented using Kahn’s algorithm (BFS-based) or DFS.

  6. Cycle Detection:
    • Undirected Graphs: Can be detected using DFS by keeping track of visited nodes and their parents in the DFS tree. If an adjacent node is visited and not the parent, a cycle exists.
    • Directed Graphs: Can be detected using DFS by tracking nodes currently in the recursion stack (visiting) and visited nodes. If a node in the recursion stack is encountered again, a cycle exists.
  7. Network Flow:
    • Max Flow Min Cut Theorem (e.g., Ford-Fulkerson, Edmonds-Karp): Determines the maximum flow from a source to a sink in a flow network.

Advantages:

  • Modeling Power: Graphs can model a vast range of real-world problems and relationships.
  • Versatility: A wide array of well-studied algorithms can solve various complex problems.
  • Optimization: Many graph algorithms are designed for efficiency and can handle large datasets.

When to Use:

  • Problems involving networks (e.g., social networks, computer networks, road networks).
  • When relationships between entities are central to the problem (e.g., dependencies, connections, hierarchies).
  • Pathfinding, route optimization, and navigation problems.
  • Scheduling and dependency management.
  • Analyzing connectivity and structure of data.
  • Problems involving state transitions where states are nodes and transitions are edges.

Example LeetCode Problems:

  1. (#200) Number of Islands (Grid traversal - BFS/DFS)
  2. (#133) Clone Graph (BFS/DFS)
  3. (#207) Course Schedule (Topological Sort, Cycle Detection in Directed Graph)
  4. (#210) Course Schedule II (Topological Sort)
  5. (#743) Network Delay Time (Dijkstra’s Algorithm)
  6. (#994) Rotting Oranges (Grid BFS)
  7. (#323) Number of Connected Components in an Undirected Graph (Premium - BFS/DFS or Union-Find)
  8. (#261) Graph Valid Tree (Premium - Check for cycles and connectivity)
  9. (#1192) Critical Connections in a Network (Bridges in a graph - Tarjan’s algorithm)
  10. (#787) Cheapest Flights Within K Stops (Modified Bellman-Ford or Dijkstra)
  11. (#1584) Min Cost to Connect All Points (Minimum Spanning Tree - Prim’s/Kruskal’s)