Graph Algorithms for Coding Interviews: BFS, DFS, Dijkstra & Topo Sort

Graphs are among the most versatile and frequently tested data structures in software engineering interviews. From modeling social networks to routing delivery networks, understanding graph traversals and shortest path algorithms is indispensable.

---

1. Graph Representations: Adjacency List vs Matrix

Before writing algorithms, choose the right representation:

• Adjacency List (Recommended for Interviews): Uses vector<vector<int>> or unordered_map<int, vector<int>>. Space complexity is O(V + E). Best for sparse graphs.
• Adjacency Matrix: Uses a 2D array int graph[V][V]. Space complexity is O(V^2). Best for dense graphs or rapid edge lookups in O(1).

// Adjacency List in C++
int numVertices = 5;
vector<vector<int>> adj(numVertices);
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // for undirected graph
}

---

2. Breadth-First Search (BFS) & Shortest Path in Unweighted Graphs

BFS explores neighbors level-by-level using a Queue. It guarantees the shortest path in unweighted graphs.

void bfs(int startNode, int n, const vector<vector<int>>& adj) {
    vector<bool> visited(n, false);
    queue<int> q;

    visited[startNode] = true;
    q.push(startNode);

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

        for (int neighbor : adj[curr]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

---

3. Depth-First Search (DFS) & Connected Components

DFS dives deep into each branch before backtracking using recursion or an explicit stack. It is essential for cycle detection and finding connected components.

void dfs(int node, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, adj, visited);
        }
    }
}

---

4. Dijkstra’s Shortest Path Algorithm (Weighted Graphs)

Dijkstra's algorithm finds the shortest path from a single source to all vertices in a weighted graph with non-negative weights using a Min-Heap (Priority Queue) in O(E log V) time.

typedef pair<int, int> pii; // {distance, node}

vector<int> dijkstra(int src, int n, const vector<vector<pii>>& adj) {
    vector<int> dist(n, 1e9);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) continue;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

---

5. Topological Sort (Kahn's Algorithm - BFS)

Topological sorting provides a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, u comes before v.

• Applications: Course Schedule, Task Dependency Resolution, Build Systems.