Graph Algorithms

From structure to strategy

In Trees and Graphs, you learned how graphs model relationships and how BFS explores neighbors level by level. In Greedy Algorithms, you learned that sometimes the best local choice can safely build a global answer.

Now we combine those ideas.

Graph algorithms help answer interview-famous questions like:

• Can every node be reached?
• What is the shortest route?
• Is there a cycle?
• In what order should tasks run?
• How do we connect everything cheaply?

Think of this lesson as your first graph problem playbook: not every graph question needs a brand-new idea. Most are a variation of a few core patterns.

Graph questions usually reveal their algorithm

Before coding, classify the graph problem. This prevents random trial-and-error in interviews.

Common clues

Problem asks... Usually think... Visit everything reachable BFS or DFS Fewest edges in an unweighted graph BFS Cheapest path with positive weights Dijkstra Task ordering with dependencies Topological sort Detect cycle / components DFS or BFS variants

Representation reminder

You already saw graph representation in Trees and Graphs. For interviews, an adjacency list is usually the default:

0 -> [1, 2]
1 -> [3]
2 -> [3]
3 -> []

It is efficient because you only store real edges, not every possible pair of nodes.

DFS goes deep first

BFS uses a queue and expands in layers. DFS, depth-first search, follows one path as far as possible before backing up.

This makes DFS especially useful for:

• connected components
• cycle detection
• exploring all possibilities
• graph/tree recursion patterns

Because you already practiced recursion in Recursion and Backtracking, DFS should feel familiar: mark the node, visit its neighbors, recurse.

```java
import java.util.*;

public class Main {
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;

    static void dfs(int node) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(0).add(1);
        graph.get(0).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);

        visited = new boolean[n];

        System.out.print("DFS order: ");
        dfs(0);
    }
}
```

You are given an unweighted graph and need the minimum number of edges from a start node to every reachable node.

Which algorithm is the best first choice?

When edges have costs

In an unweighted graph, BFS works because every edge has the same cost: 1.

But if edges have different positive weights, BFS can be fooled.

A --10--> B
A --1 --> C --1--> B

BFS might see B quickly through the direct edge, but the cheaper path is A -> C -> B with cost 2.

Dijkstra's algorithm

Dijkstra repeatedly chooses the currently known cheapest unprocessed node, then relaxes its outgoing edges.

That word relax means:

If going through this node gives a cheaper distance to a neighbor, update that neighbor's distance.

This is where your Greedy Algorithms lesson returns: Dijkstra makes a safe greedy choice when all edge weights are non-negative.

PriorityQueue drives the greedy choice

Java's PriorityQueue lets us repeatedly pull the node with the smallest known distance.

The core loop is:

1. Start distance of source as 0.
2. Pop the cheapest node candidate.
3. Skip it if it is stale.
4. Relax its neighbors.
5. Push improved distances into the queue.

This version assumes all edge weights are non-negative.

```java
import java.util.*;

public class Main {
    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(0).add(new Edge(1, 4));
        graph.get(0).add(new Edge(2, 1));
        graph.get(2).add(new Edge(1, 2));
        graph.get(1).add(new Edge(3, 1));
        graph.get(2).add(new Edge(3, 5));
        graph.get(3).add(new Edge(4, 3));

        int source = 0;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{source, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int node = current[0];
            int cost = current[1];

            if (cost > dist[node]) continue;

            for (Edge edge : graph.get(node)) {
                int newCost = cost + edge.weight;
                if (newCost < dist[edge.to]) {
                    dist[edge.to] = newCost;
                    pq.offer(new int[]{edge.to, newCost});
                }
            }
        }

        System.out.println("Shortest distances from node 0:");
        System.out.println(Arrays.toString(dist));
    }
}
```

In Java, Dijkstra commonly uses a min-priority behavior so we can repeatedly process the node with the smallest known distance.

Fill in the Java class name:

__________

Dependencies form directed graphs

Some graph problems are not about distance. They are about valid order.

Examples:

• Course prerequisites
• Build systems
• Package installation
• Task scheduling

If task A must happen before task B, draw a directed edge:

A -> B

A topological sort returns an order where every prerequisite appears before the thing that depends on it.

Important condition: topological sort only works for a DAG — a Directed Acyclic Graph.

Topological sort with indegrees

Kahn's algorithm uses a queue of nodes with 0 incoming edges.

Mental model:

1. Count each node's indegree.
2. Start with nodes that have no prerequisites.
3. Remove one from the queue and add it to the order.
4. Decrease indegree of its neighbors.
5. If a neighbor reaches 0, enqueue it.

If we cannot process all nodes, the graph had a cycle.

```java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // Edges mean: prerequisite -> course
        graph.get(0).add(2);
        graph.get(1).add(2);
        graph.get(2).add(3);
        graph.get(2).add(4);
        graph.get(3).add(5);
        graph.get(4).add(5);

        int[] indegree = new int[n];
        for (int from = 0; from < n; from++) {
            for (int to : graph.get(from)) {
                indegree[to]++;
            }
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);

            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) queue.offer(neighbor);
            }
        }

        if (order.size() == n) {
            System.out.println("Valid course order: " + order);
        } else {
            System.out.println("Cycle detected; no valid order.");
        }
    }
}
```

True or false?

Topological sort works on any directed graph, even when the graph contains a cycle.

How to attack graph problems

When you see a graph interview problem, pause before coding and ask:

1. Directed or undirected?
2. Weighted or unweighted?
3. Can there be cycles?
4. Do I need reachability, shortest path, ordering, or components?
5. What should happen with disconnected nodes?

Pattern map

• Reach all possible nodes → BFS / DFS
• Minimum edges in unweighted graph → BFS
• Minimum cost with non-negative weights → Dijkstra
• Dependency ordering → Topological sort
• Cycle detection → DFS/BFS variant or topological-sort failure

Your MAANG-level habit

Do not just name an algorithm. Explain why the graph's constraints justify it.

Next, we will study Hashing, a technique that often pairs with graph problems to track visited states, frequencies, and fast lookups.