Graph Problem Solving Techniques

Welcome back! In our last lesson, we developed a method for tackling linked list and tree problems by focusing on the "state" required at each step of a traversal. This systematic approach of identifying the crucial information needed to make decisions is a powerful tool for moving from a problem statement to a concrete algorithm.

Today, we'll apply that same structured thinking to graph problems. You've already learned the mechanics of key graph algorithms like BFS, DFS, Dijkstra's, and topological sort. This lesson shifts the focus from how these algorithms work to when and why you should choose one over the other. Our goal is to equip you with a mental checklist that allows you to confidently deconstruct an unseen Medium-level graph problem, model it correctly, and select the most appropriate algorithm from your toolbox.

A Quick Refresher on Graph Concepts

Before we build our decision framework, let's have a quick, high-energy refresher on the fundamental concepts of graphs and the main traversal strategies. The following video from Fireship provides an excellent overview.

The Three-Step Framework for Graph Problems

Facing a new graph problem can feel overwhelming due to the variety of possible approaches. The key to cutting through this complexity is a repeatable, three-step process. This structured approach helps transform ambiguity into a clear plan of action, which is invaluable for managing the "algo phobia" you've mentioned.

Here is the framework:

1. Identify the Graph Model: First, translate the problem's components into graph terminology.

   • Nodes: What entities are being represented? (e.g., cities, people, courses, grid cells).
   • Edges: What are the relationships between them? (e.g., roads, friendships, prerequisites, adjacency).
   • Direction: Are the relationships one-way (directed) or two-way (undirected)?
   • Weights: Do the connections have a cost, distance, or time associated with them? If so, the graph is weighted. If not, all edges can be considered to have a weight of 1.

2. Choose the Right Tool: Next, analyze the core question being asked. Certain keywords and problem structures are strong signals for specific algorithms.

If the problem asks for...	The primary tool is likely...	Because...
Shortest path, fewest steps, minimum moves (unweighted)	Breadth-First Search (BFS)	BFS explores layer by layer, guaranteeing it finds the shortest path in terms of the number of edges.
Shortest path, minimum cost, cheapest route (weighted)	Dijkstra's Algorithm	Dijkstra's is a modified BFS that uses a priority queue to always explore the cheapest path discovered so far.
Prerequisites, dependencies, task ordering, course schedule	Topological Sort	This algorithm specifically produces a linear ordering of nodes that respects all directed dependencies.
Path existence, reachability, connected components, "find all..."	Depth-First Search (DFS) or BFS	DFS is often more natural for exhaustive exploration and backtracking, while BFS also works for reachability.
Cycle detection	DFS (with node states) or Topological Sort (for DAGs)	DFS can track a node's visitation state (visiting vs. visited) to find back edges. A failed topological sort also implies a cycle.

3. Talk Through Edge Cases: Before you code, consider what could go wrong.
   • Disconnected Graph: What if not all nodes are reachable from the start? Your solution should handle this.
   • Cycles: How does your chosen algorithm behave if a cycle exists? This is critical for topological sort.
   • Negative Weights: Dijkstra's algorithm fails with negative edge weights. While rare in interviews, acknowledging this limitation shows depth.

To solidify this framework, let's read a guide that explicitly links these patterns to interview scenarios.

Applying the Framework: Worked Examples

Let's put this framework into practice with two classic Medium-level problems.

Example 1: Dependencies and Ordering (LeetCode 207. Course Schedule)

Problem: You are given numCourses and a list of prerequisites, where [a, b] means you must take course b before course a. Is it possible to finish all courses?

Let's apply our framework:

1. Identify the Graph Model:

   • Nodes: The courses (0 to numCourses - 1).
   • Edges: The prerequisites. A prerequisite [a, b] represents a directed edge from b to a (b -> a), signifying that b must precede a.
   • Weights: There are no weights.

2. Choose the Right Tool:

   • The keywords are "prerequisites" and the question is about "possibility to finish," which implies a valid ordering. This is a textbook signal for Topological Sort. An impossible schedule means there's a circular dependency (e.g., Course A needs B, and B needs A), which is a cycle in our directed graph.

3. Algorithm and Edge Cases:

   • The goal is to detect if a cycle exists. We can do this using Kahn's algorithm (a BFS-based topological sort). We count the "in-degrees" (number of prerequisites) for each course. We start with courses that have an in-degree of 0. As we "take" a course, we decrement the in-degree of all courses that depend on it. If any of their in-degrees become 0, they are added to our queue of courses to take.
   • If we successfully process all numCourses, no cycle exists. If the process finishes but some courses were not processed, it means they are part of a cycle.

Now, let's dive into a detailed explanation and implementation.

Example 2: Shortest Path with Costs (LeetCode 743. Network Delay Time)

Problem: You are given a network of n nodes, a list of travel times as directed edges [u, v, w], and a starting node k. Find the minimum time it takes for a signal to travel from k to all n nodes. If it's impossible for the signal to reach every node, return -1.

1. Identify the Graph Model:

   • Nodes: The n network devices.
   • Edges: The connections [u, v, w], representing a directed edge from u to v with a weight of w.
   • Weights: Yes, the travel time w.

2. Choose the Right Tool:

   • The problem asks for the "minimum time" for a signal to reach every node. This means we need the shortest path from the source k to all other nodes. Since the edges are weighted, simple BFS is not sufficient. This is the classic use case for Dijkstra's Algorithm. The final answer will be the maximum of all these shortest path distances.

3. Algorithm and Edge Cases:

   • We'll use Dijkstra's, which maintains a priority queue of (cost, node) tuples, always processing the node that is cheapest to reach next. We also need a way to track the final shortest distance to each node and a set of visited nodes to avoid cycles and redundant work.
   • The main edge case is a disconnected graph. If, after the algorithm finishes, we haven't visited all n nodes, it's impossible to reach everyone, so we should return -1.

The following video provides a clear, visual walkthrough of this problem using Dijkstra's algorithm.

Key Takeaways

• Solving graph problems systematically starts with a three-step framework: model the graph, choose the right algorithm based on the core question, and consider edge cases.
• Problem keywords are your guide:
  • "Shortest/fewest" + unweighted edges → BFS.
  • "Shortest/cheapest" + weighted edges → Dijkstra's.
  • "Prerequisites/dependencies/order" → Topological Sort.
  • "Connectivity/reachability/find all" → DFS (or BFS).
• Always be prepared to justify your choice of algorithm. Explaining why you chose Dijkstra's over BFS, for example, is a strong signal in an interview.

In our next module, we'll venture into new algorithmic territory, starting with Greedy Decisions. You'll learn how making a locally optimal choice at each step can lead to a globally optimal solution for certain classes of problems, particularly those involving intervals and resource allocation.