Advanced Graph Algorithms
Master complex graph algorithms that are frequently asked in technical interviews at top tech companies. This module covers advanced techniques for solving graph problems efficiently.
Module Contents
Learning Resources
Introduction to Advanced Graphs
Graph algorithms are among the most important and frequently tested topics in technical interviews. This module builds on basic graph concepts and explores advanced algorithms that solve complex graph problems efficiently.
Graph Representations Review
Adjacency Matrix:
A 2D array where matrix[i][j] represents an edge from vertex i to vertex j. Efficient for dense graphs and checking if an edge exists in O(1) time.
0 1 2 3 0 [0,1,0,1] 1 [1,0,1,0] 2 [0,1,0,1] 3 [1,0,1,0]
Adjacency List:
An array of lists where each list contains the neighbors of the corresponding vertex. Efficient for sparse graphs and traversing neighbors.
0 -> [1, 3] 1 -> [0, 2] 2 -> [1, 3] 3 -> [0, 2]
Graph Types and Properties
- Directed vs. Undirected: In directed graphs, edges have a direction, while in undirected graphs, edges are bidirectional.
- Weighted vs. Unweighted: Weighted graphs have values (weights) associated with edges, while unweighted graphs do not.
- Cyclic vs. Acyclic: Cyclic graphs contain at least one cycle, while acyclic graphs do not have any cycles.
- Connected vs. Disconnected: In a connected graph, there is a path between every pair of vertices, while disconnected graphs have at least one unreachable vertex.
- Bipartite: A graph whose vertices can be divided into two disjoint sets such that every edge connects vertices from different sets.
Basic Graph Algorithms Review
Key Algorithms:
- Breadth-First Search (BFS): Explores all neighbors at the current depth before moving to nodes at the next depth level. Time complexity: O(V + E).
- Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. Time complexity: O(V + E).
- Dijkstra's Algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. Time complexity: O((V + E) log V) with a binary heap.
- Bellman-Ford Algorithm: Finds the shortest path from a source vertex to all other vertices, even with negative edge weights (but no negative cycles). Time complexity: O(V * E).
Interactive Graph Algorithm Visualization
Experiment with different graph algorithms to better understand how they work. Select an algorithm and observe its execution step by step.
Graph Algorithms
Breadth-First Search (BFS) explores all the vertices of a graph at the present depth before moving on to vertices at the next depth level.
Queue/Stack:
Explanation:
Click play or step to start the visualization.
Visited Nodes:
Path:
Advanced Shortest Path Algorithms
Shortest path algorithms are fundamental in graph theory and have numerous applications. Let's explore advanced algorithms for finding shortest paths in different scenarios.
1. Floyd-Warshall Algorithm
The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph, including those with negative edge weights (but no negative cycles).
Key Properties:
- Computes shortest paths between all pairs of vertices
- Works with negative edge weights (but no negative cycles)
- Time complexity: O(V³)
- Space complexity: O(V²)
// Floyd-Warshall Algorithm
void floydWarshall(int[][] graph, int V) {
int[][] dist = new int[V][V];
// Initialize distance matrix
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// Update shortest paths
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != Integer.MAX_VALUE &&
dist[k][j] != Integer.MAX_VALUE &&
dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Check for negative cycles
for (int i = 0; i < V; i++) {
if (dist[i][i] < 0) {
System.out.println("Graph contains negative cycle");
return;
}
}
// Print shortest distances
printSolution(dist, V);
}2. Johnson's Algorithm
Johnson's algorithm finds the shortest paths between all pairs of vertices in a sparse weighted graph. It combines Bellman-Ford and Dijkstra's algorithms for better performance on sparse graphs.
Key Properties:
- More efficient than Floyd-Warshall for sparse graphs
- Works with negative edge weights (but no negative cycles)
- Time complexity: O(V² log V + VE)
- Uses reweighting technique to make all edge weights non-negative
3. A* Search Algorithm
A* is an informed search algorithm that finds the shortest path from a start node to a goal node using heuristics to guide the search.
Key Properties:
- Uses a heuristic function to estimate the cost from the current node to the goal
- Combines the actual cost from the start node (g) and the estimated cost to the goal (h)
- Prioritizes nodes with the lowest f = g + h value
- Guarantees the shortest path if the heuristic is admissible (never overestimates)
- Widely used in pathfinding and graph traversal
4. Bidirectional Search
Bidirectional search runs two simultaneous searches: one forward from the source and one backward from the destination, stopping when they meet in the middle.
Key Properties:
- Can significantly reduce the search space compared to unidirectional search
- Particularly effective when the branching factor is high
- Requires careful handling of the meeting point to ensure the shortest path
- Can be combined with other algorithms like Dijkstra's or A*
Minimum Spanning Trees
A Minimum Spanning Tree (MST) is a subset of the edges of a connected, undirected graph that connects all vertices together with the minimum possible total edge weight.
1. Kruskal's Algorithm
Kruskal's algorithm builds the MST by adding edges in order of increasing weight, skipping edges that would create a cycle.
Algorithm Steps:
- Sort all edges in non-decreasing order of their weight
- Initialize an empty MST
- For each edge in the sorted order:
- If adding the edge doesn't create a cycle, add it to the MST
- Otherwise, discard the edge
- Continue until the MST has (V-1) edges
// Kruskal's Algorithm using Union-Find
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
class Graph {
int V, E;
Edge[] edges;
// Find operation with path compression
int find(int[] parent, int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
}
// Union operation by rank
void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
// Kruskal's algorithm
void kruskalMST() {
Edge[] result = new Edge[V - 1];
int e = 0;
int i = 0;
// Sort edges by weight
Arrays.sort(edges);
// Initialize parent[] and rank[]
int[] parent = new int[V];
int[] rank = new int[V];
for (int v = 0; v < V; v++) {
parent[v] = v;
rank[v] = 0;
}
i = 0;
while (e < V - 1 && i < E) {
Edge nextEdge = edges[i++];
int x = find(parent, nextEdge.src);
int y = find(parent, nextEdge.dest);
if (x != y) {
result[e++] = nextEdge;
union(parent, rank, x, y);
}
}
// Print the MST
System.out.println("Minimum Spanning Tree:");
for (i = 0; i < e; i++) {
System.out.println(result[i].src + " -- " +
result[i].dest + " == " +
result[i].weight);
}
}
}2. Prim's Algorithm
Prim's algorithm builds the MST by starting from a vertex and always adding the lowest-weight edge that connects a vertex in the MST to a vertex outside the MST.
Algorithm Steps:
- Initialize a set to keep track of vertices in the MST
- Choose any vertex as the starting point and add it to the set
- While the set doesn't include all vertices:
- Find the minimum weight edge connecting a vertex in the set to a vertex outside
- Add the new vertex to the set and the edge to the MST
// Prim's Algorithm using Priority Queue
void primMST(int[][] graph, int V) {
// Array to store constructed MST
int[] parent = new int[V];
// Key values used to pick minimum weight edge
int[] key = new int[V];
// To represent set of vertices included in MST
boolean[] mstSet = new boolean[V];
// Initialize all keys as INFINITE
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
// Always include first vertex in MST
key[0] = 0; // Make key 0 so this vertex is picked first
parent[0] = -1; // First node is always root of MST
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included in MST
int u = minKey(key, mstSet, V);
// Add the picked vertex to the MST Set
mstSet[u] = true;
// Update key value and parent index of the adjacent vertices of the picked vertex
for (int v = 0; v < V; v++) {
// graph[u][v] is non-zero only for adjacent vertices of u
// mstSet[v] is false for vertices not yet included in MST
// Update the key only if graph[u][v] is smaller than key[v]
if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// Print the constructed MST
printMST(parent, graph, V);
}
// A utility function to find the vertex with minimum key value
int minKey(int[] key, boolean[] mstSet, int V) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++) {
if (mstSet[v] == false && key[v] < min) {
min = key[v];
min_index = v;
}
}
return min_index;
}3. Borůvka's Algorithm
Borůvka's algorithm builds the MST by finding the minimum-weight edge for each component and merging components.
Key Properties:
- Works well in parallel and distributed settings
- Time complexity: O(E log V)
- Less commonly used than Kruskal's or Prim's algorithms
- Particularly efficient for dense graphs
4. Applications of MST
Real-world Applications:
- Network Design: Designing networks with minimum cost (e.g., telecommunications, electrical grids)
- Clustering: Used in clustering algorithms like single-linkage clustering
- Approximation Algorithms: Used as a subroutine in approximation algorithms for NP-hard problems like the Traveling Salesman Problem
- Image Segmentation: Used in computer vision for image segmentation
Strongly Connected Components
A Strongly Connected Component (SCC) is a subgraph in which every vertex is reachable from every other vertex. SCCs are important in analyzing the structure of directed graphs.
1. Kosaraju's Algorithm
Kosaraju's algorithm finds all strongly connected components in a directed graph using two passes of DFS.
Algorithm Steps:
- Perform DFS on the original graph and store vertices in order of finish time
- Transpose the graph (reverse all edges)
- Perform DFS on the transposed graph, starting with vertices in the order obtained in step 1
- Each DFS tree in step 3 is a strongly connected component
// Kosaraju's Algorithm
class Graph {
private int V;
private LinkedList<Integer>[] adj;
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// Add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// DFS utility
void DFSUtil(int v, boolean[] visited) {
visited[v] = true;
System.out.print(v + " ");
for (Integer neighbor : adj[v]) {
if (!visited[neighbor])
DFSUtil(neighbor, visited);
}
}
// Function that returns reverse (or transpose) of this graph
Graph getTranspose() {
Graph g = new Graph(V);
for (int v = 0; v < V; v++) {
for (Integer neighbor : adj[v]) {
g.adj[neighbor].add(v);
}
}
return g;
}
// Fill vertices in stack according to their finishing times
void fillOrder(int v, boolean[] visited, Stack<Integer> stack) {
visited[v] = true;
for (Integer neighbor : adj[v]) {
if (!visited[neighbor])
fillOrder(neighbor, visited, stack);
}
stack.push(v);
}
// Print all strongly connected components
void printSCCs() {
Stack<Integer> stack = new Stack<>();
// Mark all vertices as not visited (For first DFS)
boolean[] visited = new boolean[V];
Arrays.fill(visited, false);
// Fill vertices in stack according to their finishing times
for (int i = 0; i < V; i++) {
if (!visited[i])
fillOrder(i, visited, stack);
}
// Create a reversed graph
Graph transposed = getTranspose();
// Mark all vertices as not visited (For second DFS)
Arrays.fill(visited, false);
// Process all vertices in order defined by stack
System.out.println("Strongly Connected Components:");
while (!stack.empty()) {
int v = stack.pop();
if (!visited[v]) {
transposed.DFSUtil(v, visited);
System.out.println();
}
}
}
}2. Tarjan's Algorithm
Tarjan's algorithm finds all strongly connected components in a directed graph using a single pass of DFS with additional bookkeeping.
Key Concepts:
- Discovery Time: When a vertex is first discovered during DFS
- Low Link Value: Smallest discovery time of any vertex reachable from the current vertex
- Stack: Keeps track of vertices being processed
- A vertex is the root of an SCC if its discovery time equals its low link value
// Tarjan's Algorithm
class Graph {
private int V;
private LinkedList<Integer>[] adj;
private int time = 0;
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// Add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// A recursive function that finds SCCs using DFS
void SCCUtil(int u, int[] disc, int[] low, Stack<Integer> stack, boolean[] stackMember) {
// Initialize discovery time and low value
disc[u] = low[u] = ++time;
stack.push(u);
stackMember[u] = true;
// Go through all vertices adjacent to this
for (Integer v : adj[u]) {
// If v is not visited yet, then recur for it
if (disc[v] == -1) {
SCCUtil(v, disc, low, stack, stackMember);
// Check if the subtree rooted with v has a connection to
// one of the ancestors of u
low[u] = Math.min(low[u], low[v]);
}
// Update low value of u only if v is still in stack
else if (stackMember[v]) {
low[u] = Math.min(low[u], disc[v]);
}
}
// Head node found, pop the stack and print an SCC
if (low[u] == disc[u]) {
System.out.print("SCC: ");
int w;
do {
w = stack.pop();
System.out.print(w + " ");
stackMember[w] = false;
} while (w != u);
System.out.println();
}
}
// The function to find all SCCs
void SCC() {
// Initialize discovery time, low value, and stack member arrays
int[] disc = new int[V];
int[] low = new int[V];
boolean[] stackMember = new boolean[V];
Stack<Integer> stack = new Stack<>();
// Initialize all vertices as not visited
for (int i = 0; i < V; i++) {
disc[i] = -1;
low[i] = -1;
stackMember[i] = false;
}
// Call the recursive helper function to find SCCs
for (int i = 0; i < V; i++) {
if (disc[i] == -1)
SCCUtil(i, disc, low, stack, stackMember);
}
}
}3. Applications of SCCs
Real-world Applications:
- Social Networks: Identifying communities or groups of users who interact frequently
- Web Crawling: Identifying groups of web pages that link to each other
- Dependency Resolution: Detecting circular dependencies in software packages
- Compiler Optimization: Finding loops in control flow graphs for optimization
Topological Sorting
Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering.
1. DFS-based Topological Sort
The most common approach to topological sorting uses depth-first search to build the ordering.
Algorithm Steps:
- Run DFS on the graph
- As each vertex finishes (all its descendants have been processed), add it to the front of the result list
- The final list is the topological ordering
// DFS-based Topological Sort
class Graph {
private int V;
private LinkedList<Integer>[] adj;
// Constructor
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// Add an edge to the graph
void addEdge(int v, int w) {
adj[v].add(w);
}
// A recursive function used by topologicalSort
void topologicalSortUtil(int v, boolean[] visited, Stack<Integer> stack) {
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (Integer neighbor : adj[v]) {
if (!visited[neighbor])
topologicalSortUtil(neighbor, visited, stack);
}
// Push current vertex to stack which stores the result
stack.push(v);
}
// The function to do Topological Sort
void topologicalSort() {
Stack<Integer> stack = new Stack<>();
// Mark all vertices as not visited
boolean[] visited = new boolean[V];
// Call the recursive helper function to store Topological Sort
// starting from all vertices one by one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
// Print contents of stack
System.out.println("Topological Sort:");
while (!stack.empty()) {
System.out.print(stack.pop() + " ");
}
System.out.println();
}
}2. Kahn's Algorithm
Kahn's algorithm is an alternative approach to topological sorting that uses a queue and in-degree information.
Algorithm Steps:
- Compute in-degree (number of incoming edges) for each vertex
- Enqueue all vertices with in-degree 0
- While the queue is not empty:
- Dequeue a vertex and add it to the result
- Reduce the in-degree of all its neighbors by 1
- If a neighbor's in-degree becomes 0, enqueue it
- If the result contains all vertices, it's a valid topological sort; otherwise, the graph has a cycle
// Kahn's Algorithm for Topological Sort
void topologicalSortKahn() {
// Create a array to store indegrees of all vertices
int[] inDegree = new int[V];
// Traverse adjacency lists to fill indegrees of vertices
for (int i = 0; i < V; i++) {
for (Integer neighbor : adj[i]) {
inDegree[neighbor]++;
}
}
// Create a queue and enqueue all vertices with indegree 0
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0)
queue.add(i);
}
// Initialize count of visited vertices
int count = 0;
// Create a vector to store result (A topological ordering)
List<Integer> topOrder = new ArrayList<>();
// Process vertices in topological order
while (!queue.isEmpty()) {
// Extract front of queue
int u = queue.poll();
topOrder.add(u);
// Iterate through all its neighboring nodes
for (Integer neighbor : adj[u]) {
// Reduce in-degree by 1
if (--inDegree[neighbor] == 0)
queue.add(neighbor);
}
count++;
}
// Check if there was a cycle
if (count != V) {
System.out.println("There exists a cycle in the graph");
return;
}
// Print topological order
System.out.println("Topological Sort (Kahn's Algorithm):");
for (Integer i : topOrder) {
System.out.print(i + " ");
}
System.out.println();
}
}3. Applications of Topological Sorting
Real-world Applications:
- Dependency Resolution: Determining the order to build packages or modules in a build system
- Task Scheduling: Scheduling jobs or tasks with dependencies
- Course Prerequisites: Determining a valid sequence of courses to take based on prerequisites
- Data Processing Pipelines: Ordering operations in data processing workflows
- Compilation: Ordering declarations in programming languages
4. Detecting Cycles in Directed Graphs
Topological sorting is only possible for directed acyclic graphs (DAGs). If a graph has a cycle, no valid topological ordering exists.
Cycle Detection Methods:
- Using DFS: Keep track of vertices in the current recursion stack. If a back edge is found (an edge to a vertex in the recursion stack), a cycle exists.
- Using Kahn's Algorithm: If the number of vertices in the topological order is less than the total number of vertices, the graph has a cycle.
- Using Colors: Mark vertices as white (unvisited), gray (in progress), and black (completed). A back edge to a gray vertex indicates a cycle.
Practice Problems
Test your understanding of advanced graph algorithms with these practice problems commonly asked in technical interviews.
1. Network Delay Time
You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target. We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
2. Course Schedule
There are a total of n courses you have to take, labeled from 0 to n-1. Some courses may have prerequisites. For example, to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]. Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
3. Critical Connections in a Network
There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. Any server can reach any other server directly or indirectly through the network. A critical connection is a connection that, if removed, will make some server unable to reach some other server. Return all critical connections in the network in any order.
4. Cheapest Flights Within K Stops
There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, return -1.
5. Reconstruct Itinerary
Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.