Beyond basic BFS/DFS, advanced graph algorithms solve optimization problems: finding the cheapest path with constraints, detecting negative cycles, computing all-pairs shortest paths, and building minimum spanning trees. These appear in 5-10% of senior coding interviews. This guide covers the algorithms and their interview applications.
Bipartite Graph Check
A bipartite graph can be divided into two sets such that every edge connects a node in one set to a node in the other. Equivalently: the graph can be 2-colored. Algorithm: BFS or DFS with 2-coloring. Start at any node, color it 0. Color all neighbors 1. Color their uncolored neighbors 0. If any neighbor already has the same color as the current node, the graph is NOT bipartite. Time: O(V + E). Applications: (1) Is Graph Bipartite? (LeetCode 785) — direct application. (2) Possible Bipartition (LeetCode 886) — given dislike pairs, can people be divided into two groups with no dislikes within a group? Build a graph from dislike pairs and check bipartiteness. (3) Matching problems — in a bipartite graph, find the maximum matching (maximum set of edges with no shared vertices). Used for: job assignment (workers to tasks), interval scheduling, and network flow. Hungarian algorithm solves this in O(V^3). For coding interviews, bipartite checking (not matching) is most commonly tested.
Dijkstra with Constraints
Standard Dijkstra finds the shortest path in a graph with non-negative weights. Many interview problems add constraints. Cheapest Flights Within K Stops: find the cheapest route from source to destination with at most K intermediate stops. Standard Dijkstra does not work because the shortest path may have too many stops. Modified Dijkstra: the state is (cost, node, stops_remaining). Push (0, source, K) to the min-heap. For each state, explore neighbors only if stops_remaining > 0. Track the minimum cost to reach each node with each number of remaining stops. Time: O(E * K * log(V * K)). Alternative: Bellman-Ford relaxation for K+1 iterations (see below). Network Delay Time: find the time for a signal from a source to reach all nodes. Standard Dijkstra. Answer: the maximum distance to any node. If any node is unreachable, return -1. Path With Minimum Effort: find the path from top-left to bottom-right in a grid minimizing the maximum absolute height difference between adjacent cells. Modified Dijkstra where the “distance” is the maximum effort along the path. Use a min-heap on effort. Relax: new_effort = max(current_effort, |height_diff|).
Bellman-Ford Algorithm
Bellman-Ford finds the shortest path from a single source, even with negative edge weights. It also detects negative cycles. Algorithm: initialize distance[source] = 0, all others = infinity. Repeat V-1 times: for each edge (u, v, w): if distance[u] + w < distance[v], update distance[v] = distance[u] + w. After V-1 iterations, all shortest paths are computed. Negative cycle detection: run one more iteration. If any distance is updated, a negative cycle exists (the graph has a path that gets cheaper with each loop — shortest path is undefined). Time: O(V * E). Slower than Dijkstra (O(E log V)) but handles negative weights. When to use: (1) Graph has negative edge weights (Dijkstra fails). (2) Need to detect negative cycles. (3) Cheapest Flights Within K Stops — run Bellman-Ford for K+1 iterations instead of V-1. After K+1 iterations, distance[destination] is the cheapest path with at most K stops. This is simpler than modified Dijkstra for this specific problem. SPFA (Shortest Path Faster Algorithm): a queue-based optimization of Bellman-Ford. Average case is much faster than O(VE) but worst case is the same. Used in competitive programming.
Floyd-Warshall: All-Pairs Shortest Path
Floyd-Warshall computes the shortest path between every pair of nodes. Algorithm: initialize dist[i][j] = weight of edge (i,j) if exists, infinity otherwise. dist[i][i] = 0. For each intermediate node k from 0 to V-1: for each pair (i, j): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After processing all k, dist[i][j] contains the shortest path from i to j (possibly through intermediate nodes). Time: O(V^3). Space: O(V^2). When to use: (1) V is small (under 500) and you need shortest paths between ALL pairs. (2) The graph may have negative weights (no negative cycles). (3) Problems asking “for each node, what is the minimum distance to all other nodes?” Applications: (1) Find the City With the Smallest Number of Neighbors at a Threshold Distance (LeetCode 1334). (2) Shortest path in a graph that changes (edges added/removed — recompute Floyd-Warshall incrementally). (3) Transitive closure — can node i reach node j? Set dist[i][j] = dist[i][k] AND dist[k][j]. For larger graphs (V > 500), run Dijkstra from each node: O(V * E log V), which is faster than Floyd-Warshall when E << V^2.
Minimum Spanning Tree: Kruskal and Prim
MST connects all nodes with the minimum total edge weight without cycles. Kruskal: sort edges by weight. Process from lightest to heaviest. For each edge: if it connects two different components (Union-Find check), include it. Time: O(E log E) for sort + O(E * alpha(V)) for Union-Find = O(E log E). Best when edges are given as a list. Prim: start from any node. Maintain a min-heap of edges from the growing tree to non-tree nodes. Repeatedly extract the minimum edge, add the new node to the tree, and push its edges. Time: O(E log V) with a binary heap. Best for dense graphs (adjacency matrix). Applications: (1) Min Cost to Connect All Points (LeetCode 1584) — points are nodes, edge weight = Manhattan distance. Kruskal or Prim. (2) Optimize Water Distribution (LeetCode 1168) — connect houses to water with minimum pipe cost. (3) Network infrastructure — minimum cost to connect all offices with cables. Both algorithms produce the same MST (MST is unique when all edge weights are distinct). Kruskal is simpler with Union-Find. Prim is easier with an adjacency list + heap. Know both for interviews; Kruskal is more commonly asked.