Introduction

A deep dive on algorithms pertinent to graph problems within the realm of data structures & algorithms.

• Introduction
• ♦️ BFS
• ♦️ DFS
• ♦️ Priority Queue
• 🔸 Dijkstra's Algorithm
• 🔷 A* Search Algorithm
• 🔸 Prim's Algorithm
• ♦️ Union-Find
• 🔸 Kruskal's Algorithm
• ♦️ Topological Sort
• ♦️ Bellman-Ford Algorithm
• ♦️ Floyd-Warshall Algorithm
• ♦️ Tarjan's Algorithm
• ♦️ Kosaraju's Algorithm
• ♦️ Edmonds-Karp Algorithm
• ♦️ Hopcroft-Karp Algorithm
• ♦️ Johnson's Algorithm
• Conclusion

♦️ BFS

Shortest path in unweighted graphs, level-order traversal, finding the minimum number of steps.

Here are the Key Features sections for the requested algorithms:

• Key Features:

  • Explores nodes level by level (breadth-first).
  • Guarantees the shortest path in unweighted graphs.
  • Uses a queue for traversal.
  • Commonly used for:
    • Finding the shortest path in unweighted graphs.
    • Level-order traversal of trees.
    • Solving problems involving minimum steps or distances.

• LeetCode Problems:

  • 127. Word Ladder — Find the shortest transformation sequence from beginWord to endWord.
  • 207. Course Schedule — Determine if you can finish all courses given prerequisites.
  • 994. Rotting Oranges — Find the minimum time required for all oranges to rot.
  • 1091. Shortest Path in Binary Matrix — Find the shortest path from the top-left corner to the bottom-right in a binary grid.

♦️ DFS

Detecting cycles, connected components, topological sorting.

• Key Features:

  • Explores as far as possible along each branch before backtracking (depth-first).
  • Uses a stack (explicit or recursion) for traversal.
  • Commonly used for:
    • Detecting cycles in graphs.
    • Finding connected components.
    • Topological sorting in Directed Acyclic Graphs (DAGs).
    • Solving maze and path finding problems.

• LeetCode Problems:

  • 200. Number of Islands — Count the number of islands (connected components) in a grid.
  • 210. Course Schedule II — Return the ordering of courses to finish all courses.
  • 417. Pacific Atlantic Water Flow — Find cells that can flow to both the Pacific and Atlantic oceans.
  • 785. Is Graph Bipartite? — Check if a graph is bipartite using DFS.

♦️ Priority Queue

Dijkstra’s algorithm for shortest path in weighted graphs, Prim’s algorithm for Minimum Spanning Tree (MST).

• Key Features:

  • A data structure that allows retrieval of the smallest (or largest) element efficiently.
  • Used in graph algorithms like:
    • Dijkstra's
    • Prim's
  • Typically implemented using a min-heap or max-heap.

• LeetCode Problems:

  • 743. Network Delay Time — Find the time it takes for all nodes to receive a signal from a starting node.
  • 787. Cheapest Flights Within K Stops — Find the cheapest flight path with at most K stops.
  • 1514. Path with Maximum Probability — Find the path with the highest probability.
  • 1631. Path With Minimum Effort — Find the minimum effort path in a grid.

🔸 Dijkstra's Algorithm

Dijkstra's algorithm is used to find the shortest path from a source node to all other nodes in a weighted, non-negative graph. It uses a priority queue (min-heap) to always extend the path with the lowest cost first. It is optimal for graphs with non-negative weights but does not handle negative cycles.

• Key Features:

  • Finds the shortest path from a source node to all other nodes in a weighted graph.
  • Works only with non-negative edge weights.
  • Uses a priority queue (min-heap) to extend the path with the lowest cost first.
  • Inefficient for graphs with negative weights (use Bellman-Ford instead).
  • Commonly used for:
    • Network routing.
    • Pathfinding in weighted graphs.

• LeetCode Problems:

  • 743. Network Delay Time - Find the time it takes for all nodes to receive a signal from a starting node.
  • 787. Cheapest Flights Within K Stops - Find the cheapest flight path with at most K stops.
  • 1514. Path with Maximum Probability - Find the path with the highest probability.
  • 1631. Path With Minimum Effort - Find the minimum effort path in a grid.
  • 1976. Number of Ways to Arrive at Destination - Count the number of ways to arrive at a destination with the minimum cost.

🔷 A* Search Algorithm

The A* Search Algorithm is a heuristic-based algorithm used for pathfinding and graph traversal. It is widely used in AI and game development.

• Key Features:

  • Combines the benefits of Dijkstra's algorithm and greedy best-first search.
  • Uses a heuristic function to guide the search.

• LeetCode Problems:

  • 127. Word Ladder
  • 505. The Maze II
  • 675. Cut Off Trees for Golf Event
  • 1091. Shortest Path in Binary Matrix
  • 1631. Path With Minimum Effort

🔸 Prim's Algorithm

Prim's algorithm is used to find the Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph. It builds the MST by greedily choosing the minimum edge that connects a vertex in the tree to a vertex outside the tree, using a priority queue for efficiency.

• Key Features:

  • Used to find the Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph.
  • Greedily chooses the minimum edge that connects a vertex in the tree to a vertex outside the tree.
  • Uses a priority queue (min-heap) for efficiency.
  • Commonly used for:
    • Network design (e.g., laying cables or pipelines).
    • Optimizing resource usage in connected systems.

• LeetCode Problems:

  • 261. Graph Valid Tree - Check if the graph is a valid tree.
  • 1135. Connecting Cities With Minimum Cost - Find the minimum cost to connect all cities.
  • 1168. Optimize Water Distribution in a Village - Minimize the cost of supplying water to all houses.
  • 1584. Min Cost to Connect All Points - Connect all points with the minimum cost.
  • 1631. Path With Minimum Effort (Can be solved with Prim’s as well as Dijkstra's).

♦️ Union-Find

Finding connected components, cycle detection in undirected graphs, Kruskal’s MST.

• Key Features:

  • A data structure used to efficiently manage and merge disjoint sets.
  • Supports two main operations:
  • Find: Determines which set a particular element belongs to.
  • Union: Merges two sets into one.
  • Commonly used for:
    • Detecting cycles in undirected graphs.
    • Finding connected components.
    • Supporting Kruskal’s algorithm for Minimum Spanning Tree (MST).

• LeetCode Problems:

  • 261. Graph Valid Tree — Determine if the graph is a valid tree.
  • 323. Number of Connected Components in an Undirected Graph — Count the number of connected components.
  • 684. Redundant Connection — Find the edge that, when removed, will make the graph a tree.
  • 947. Most Stones Removed with Same Row or Column — Maximize the number of stones removed by grouping in rows or columns.

🔸 Kruskal's Algorithm

Kruskal's algorithm is also used to find the Minimum Spanning Tree (MST) of a graph. It works by sorting all edges by weight and adding them one by one to the MST, ensuring that no cycles are formed (using Union-Find for cycle detection).

• Key Features:

  • Used to find the Minimum Spanning Tree (MST) of a graph.
  • Works by:
  • Sorting all edges by weight.
  • Adding edges one by one to the MST, ensuring no cycles are formed (using Union-Find for cycle detection).
  • Commonly used for:
    • Network design (e.g., laying cables or pipelines).
    • Optimizing resource usage in connected systems.

• LeetCode Problems:

  • 684. Redundant Connection - Find the edge that, when removed, will make the graph a tree.
  • 1135. Connecting Cities With Minimum Cost - Find the minimum cost to connect all cities. (Also solvable with Prim's)
  • 1168. Optimize Water Distribution in a Village - Find the minimum cost for water distribution.
  • 1202. Smallest String With Swaps - Use Union-Find to group and sort substrings.
  • 1584. Min Cost to Connect All Points - Connect all points with minimum cost. (Can be solved with either Kruskal's or Prim's)

♦️ Topological Sort

Topological Sort is used to order nodes in a Directed Acyclic Graph (DAG) such that for every directed edge U -> V, node U appears before node V in the ordering. It's particularly useful for task scheduling and dependency resolution.

• Key Features:

  • Orders nodes in a Directed Acyclic Graph (DAG) such that for every directed edge U -> V, node U appears before node V in the ordering.
  • Commonly used for:
    • Task scheduling.
    • Dependency resolution.
    • Analyzing precedence relationships in workflows.

• LeetCode Problems:

  • 207. Course Schedule - Determine if you can finish all courses given prerequisites.
  • 210. Course Schedule II - Find an order in which you can take the courses.
  • 310. Minimum Height Trees - Find the roots of minimum height trees.
  • 329. Longest Increasing Path in a Matrix - Longest path in a matrix can be viewed as a DAG.
  • 802. Find Eventual Safe States - Find nodes that do not lead to cycles.

♦️ Bellman-Ford Algorithm

The Bellman-Ford Algorithm is used to find the shortest path from a single source to all other vertices in a graph. It works with graphs that have negative weight edges but cannot handle negative weight cycles.

• Key Features:

  • Handles negative weights.
  • Slower than Dijkstra's algorithm for graphs without negative weights.

• LeetCode Problems:

  • 399. Evaluate Division
  • 743. Network Delay Time
  • 787. Cheapest Flights Within K Stops
  • 1631. Path With Minimum Effort
  • 1928. Minimum Cost to Reach Destination in Time

♦️ Floyd-Warshall Algorithm

The Floyd-Warshall Algorithm is used to find the shortest paths between all pairs of vertices in a graph. It works for both directed and undirected graphs and handles negative weights but not negative weight cycles.

• Key Features:

  • Solves the all-pairs shortest path problem.
  • Uses dynamic programming.

• LeetCode Problems:

  • 847. Shortest Path Visiting All Nodes
  • 1129. Shortest Path with Alternating Colors
  • 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
  • 1631. Path With Minimum Effort
  • 1976. Number of Ways to Arrive at Destination

♦️ Tarjan's Algorithm

The Tarjan's Algorithm is used to find strongly connected components (SCCs) in a directed graph. It uses depth-first search (DFS) and is highly efficient.

• Key Features:

  • Finds SCCs in O(V + E) time.
  • Useful for analyzing graph connectivity.

• LeetCode Problems:

  • 207. Course Schedule
  • 310. Minimum Height Trees
  • 323. Number of Connected Components in an Undirected Graph
  • 802. Find Eventual Safe States
  • 1192. Critical Connections in a Network

♦️ Kosaraju's Algorithm

The Kosaraju's Algorithm is another method to find SCCs in a directed graph. It involves two passes of DFS: one on the original graph and one on the transposed graph.

• Key Features:

  • Finds SCCs in O(V + E) time.
  • Simpler to implement conceptually compared to Tarjan's.

• LeetCode Problems:

  • 207. Course Schedule
  • 210. Course Schedule II
  • 310. Minimum Height Trees
  • 802. Find Eventual Safe States
  • 1192. Critical Connections in a Network

♦️ Edmonds-Karp Algorithm

The Edmonds-Karp Algorithm is an implementation of the Ford-Fulkerson method for finding the maximum flow in a flow network. It uses BFS to find augmenting paths.

• Key Features:

  • Solves the maximum flow problem.
  • Runs in O(VE²) time.

• LeetCode Problems:

  • 207. Course Schedule
  • 210. Course Schedule II
  • 310. Minimum Height Trees
  • 802. Find Eventual Safe States
  • 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

♦️ Hopcroft-Karp Algorithm

The Hopcroft-Karp Algorithm is used to find the maximum matching in a bipartite graph. It alternates between BFS and DFS to find augmenting paths.

• Key Features:

  • Solves the maximum bipartite matching problem.
  • Runs in O(E√V) time.

• LeetCode Problems:

  • 785. Is Graph Bipartite?
  • 886. Possible Bipartition
  • 947. Most Stones Removed with Same Row or Column
  • 1020. Number of Enclaves
  • 1202. Smallest String With Swaps

♦️ Johnson's Algorithm

The Johnson's Algorithm is used to find shortest paths between all pairs of vertices in a sparse graph with negative weights. It combines Bellman-Ford and Dijkstra's algorithms.

• Key Features:

  • Handles negative weights.
  • Efficient for sparse graphs.

• LeetCode Problems:

  • 743. Network Delay Time
  • 787. Cheapest Flights Within K Stops
  • 1514. Path with Maximum Probability
  • 1631. Path With Minimum Effort
  • 1976. Number of Ways to Arrive at Destination

Conclusion

Mastery of these algorithms will develop your graph problem solving intuition substantially.