Graph Algorithms

From states to relationships

In Dynamic Programming, you practiced turning a problem into states and transitions. Graph algorithms use a similar instinct, but the emphasis shifts:

• Nodes represent entities, positions, words, accounts, courses, servers, or states.
• Edges represent relationships, moves, dependencies, transformations, or costs.
• The interview challenge is often not “run BFS” — it is discovering the graph hidden inside the prompt.

Graph questions show up constantly at Google, Meta, Amazon, Microsoft, Citadel, and Netflix because they test representation, invariants, and tradeoffs under pressure.

In this lesson, we will focus on the core graph patterns that unlock most interview problems: traversal, shortest path, ordering, connectivity, and cycle reasoning.

The graph is rarely handed to you

From Introduction to Data Structures and Algorithms, remember: representation comes before implementation.

Common interview graph representations:

Problem clue Likely graph model “Can transform word A to B” Words are nodes, one-letter changes are edges “Prerequisites” Directed graph “Friend groups / islands” Undirected connectivity “Minimum cost / delay / flights” Weighted directed graph “Grid movement” Cells are nodes, legal moves are edges

Interview move

Before writing code, say out loud:

1. What is a node?
2. What creates an edge?
3. Is the graph directed?
4. Is it weighted?
5. Do I need reachability, shortest path, ordering, or components?

That 20-second framing often separates a clean solution from a tangled one.

A problem says:

You are given a list of bus routes. Each route contains stops. You can board any bus at a stop, and want the minimum number of buses needed to reach a target stop.

What graph modeling choice is usually most useful?

BFS is shortest path by layers

For an unweighted graph, BFS gives the shortest number of edges from a source because it explores in increasing distance:

source -> distance 0
neighbors -> distance 1
next layer -> distance 2
...

The invariant is simple but powerful:

When a node is first discovered by BFS, we have found the shortest unweighted path to it.

That invariant powers problems like:

• shortest path in a grid
• word ladder
• minimum jumps/moves
• infection spread time
• nearest zero / nearest gate

Here is a standalone C++ example using an adjacency list.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;
    vector<vector<int>> graph(n);

    auto addEdge = [&](int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    };

    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(2, 3);
    addEdge(3, 4);
    addEdge(4, 5);

    int source = 0;
    vector<int> dist(n, -1);
    queue<int> q;

    dist[source] = 0;
    q.push(source);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int nei : graph[node]) {
            if (dist[nei] == -1) {
                dist[nei] = dist[node] + 1;
                q.push(nei);
            }
        }
    }

    cout << "Shortest unweighted distances from node 0:\n";
    for (int i = 0; i < n; i++) {
        cout << "node " << i << ": " << dist[i] << "\n";
    }

    return 0;
}
```

True or false?

In BFS on an unweighted graph, if a node can be reached from multiple parents, marking it visited only when it is popped from the queue is always just as efficient and never causes duplicate queue entries.

DFS is about paths and unfinished work

BFS thinks in layers. DFS thinks in recursion paths.

For directed graphs, a common interview pattern is using colors:

• 0 = unvisited
• 1 = visiting — currently on recursion stack
• 2 = done — fully processed

If DFS reaches a visiting node again, we found a directed cycle.

This is the backbone of:

• course schedule feasibility
• dependency resolution
• detecting circular imports
• topological sorting

Below, we detect whether all courses can be completed.

```cpp
#include <bits/stdc++.h>
using namespace std;

bool dfs(int node, vector<vector<int>>& graph, vector<int>& color) {
    color[node] = 1; // visiting

    for (int nei : graph[node]) {
        if (color[nei] == 1) return false;       // cycle
        if (color[nei] == 0 && !dfs(nei, graph, color)) return false;
    }

    color[node] = 2; // done
    return true;
}

int main() {
    int courses = 4;
    vector<vector<int>> graph(courses);

    // Edge a -> b means: take course a before course b.
    graph[0].push_back(1);
    graph[1].push_back(2);
    graph[2].push_back(3);

    vector<int> color(courses, 0);
    bool possible = true;

    for (int i = 0; i < courses; i++) {
        if (color[i] == 0 && !dfs(i, graph, color)) {
            possible = false;
            break;
        }
    }

    cout << "Can complete all courses? " << (possible ? "yes" : "no") << "\n";

    return 0;
}
```

A linear ordering of a directed acyclic graph where every prerequisite appears before the thing that depends on it is called a ______.

When BFS is not enough

BFS works when every edge has equal cost. Once edges have different non-negative weights, the next best frontier is not “oldest in queue” — it is smallest known distance so far.

That is Dijkstra’s algorithm:

1. Keep dist[node] = best known cost.
2. Use a min-heap ordered by distance.
3. Pop the currently cheapest candidate.
4. Relax outgoing edges.
5. Ignore stale heap entries.

This is the pattern behind network delay time, cheapest delivery route, shortest weighted path, and many flight-cost variants with non-negative weights.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5;
    vector<vector<pair<int, int>>> graph(n);

    auto addDirected = [&](int u, int v, int w) {
        graph[u].push_back({v, w});
    };

    addDirected(0, 1, 4);
    addDirected(0, 2, 1);
    addDirected(2, 1, 2);
    addDirected(1, 3, 1);
    addDirected(2, 3, 5);
    addDirected(3, 4, 3);

    const int INF = 1e9;
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[0] = 0;
    pq.push({0, 0}); // {distance, node}

    while (!pq.empty()) {
        auto [d, node] = pq.top();
        pq.pop();

        if (d != dist[node]) continue; // stale entry

        for (auto [nei, weight] : graph[node]) {
            if (dist[node] + weight < dist[nei]) {
                dist[nei] = dist[node] + weight;
                pq.push({dist[nei], nei});
            }
        }
    }

    cout << "Dijkstra distances from node 0:\n";
    for (int i = 0; i < n; i++) {
        cout << "node " << i << ": " << dist[i] << "\n";
    }

    return 0;
}
```

Connected components are a different question

Not every graph problem asks for a path length. Sometimes the real question is:

• Are these two things connected?
• How many groups exist?
• Does adding this edge create redundancy?
• Can accounts, emails, or users be merged?

Two common tools:

DFS/BFS components

Best when the graph is already built and you want to explore every node.

Disjoint Set Union

Best when edges arrive as pair relationships and you repeatedly merge groups.

Think of DSU as maintaining a dynamic partition of nodes. It is especially useful for “friend circles,” “number of provinces,” “redundant connection,” and Kruskal-style minimum spanning tree problems.

We will go deeper into tree-shaped structures in the next lesson, but here the key idea is graph connectivity, not tree traversal.

A repeatable graph interview loop

When a graph problem appears, avoid jumping straight into code. Use this loop:

1. Name the node
   What exactly is one vertex?

2. Name the edge
   What relationship, move, dependency, or transformation connects nodes?

3. Classify the graph
   Directed or undirected? Weighted or unweighted? Cyclic or acyclic? Explicit or implicit?

4. Choose the question type
   Reachability, shortest path, ordering, cycle detection, or components?

5. Pick the matching pattern

   • BFS: shortest path in unweighted graphs
   • DFS: path exploration, cycles, components
   • Topological sort: dependency ordering
   • Dijkstra: non-negative weighted shortest path
   • DSU: merging connectivity groups

6. State the invariant
   For example: “When BFS first discovers a node, its distance is final.”

That last step is your interview superpower. It proves you are not just recalling a template — you understand why it works.