Advanced Algorithms - DSA Interview Guide

Shortest Path Algorithms

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

🗺️ Real-Life Analogy:

Think of finding the shortest route on a GPS navigation system. The algorithm explores the closest unvisited locations first, gradually expanding outward while keeping track of the shortest known distance to each destination.

TypeScript

// Priority Queue implementation for Dijkstra
class PriorityQueue {
    private heap: Array<{item: T, priority: number}> = [];
    
    enqueue(item: T, priority: number): void {
        this.heap.push({item, priority});
        this.heapifyUp(this.heap.length - 1);
    }
    
    dequeue(): T | undefined {
        if (this.heap.length === 0) return undefined;
        
        const result = this.heap[0];
        const last = this.heap.pop()!;
        
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.heapifyDown(0);
        }
        
        return result.item;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    private heapifyUp(index: number): void {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index].priority >= this.heap[parentIndex].priority) break;
            
            [this.heap[index], this.heap[parentIndex]] = 
            [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }
    
    private heapifyDown(index: number): void {
        while (true) {
            const leftChild = 2 * index + 1;
            const rightChild = 2 * index + 2;
            let smallest = index;
            
            if (leftChild < this.heap.length && 
                this.heap[leftChild].priority < this.heap[smallest].priority) {
                smallest = leftChild;
            }
            
            if (rightChild < this.heap.length && 
                this.heap[rightChild].priority < this.heap[smallest].priority) {
                smallest = rightChild;
            }
            
            if (smallest === index) break;
            
            [this.heap[index], this.heap[smallest]] = 
            [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}

// Dijkstra's Algorithm implementation
class Graph {
    private adjacencyList: Map>;
    
    constructor() {
        this.adjacencyList = new Map();
    }
    
    addVertex(vertex: number): void {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }
    
    addEdge(from: number, to: number, weight: number): void {
        this.addVertex(from);
        this.addVertex(to);
        this.adjacencyList.get(from)!.push({node: to, weight});
    }
    
    dijkstra(start: number): {distances: Map, previous: Map} {
        const distances = new Map();
        const previous = new Map();
        const pq = new PriorityQueue();
        const visited = new Set();
        
        // Initialize distances
        for (const vertex of this.adjacencyList.keys()) {
            distances.set(vertex, vertex === start ? 0 : Infinity);
            previous.set(vertex, null);
        }
        
        pq.enqueue(start, 0);
        
        while (!pq.isEmpty()) {
            const current = pq.dequeue()!;
            
            if (visited.has(current)) continue;
            visited.add(current);
            
            const neighbors = this.adjacencyList.get(current) || [];
            
            for (const neighbor of neighbors) {
                const {node, weight} = neighbor;
                const newDistance = distances.get(current)! + weight;
                
                if (newDistance < distances.get(node)!) {
                    distances.set(node, newDistance);
                    previous.set(node, current);
                    pq.enqueue(node, newDistance);
                }
            }
        }
        
        return {distances, previous};
    }
    
    getShortestPath(start: number, end: number): number[] {
        const {previous} = this.dijkstra(start);
        const path: number[] = [];
        let current: number | null = end;
        
        while (current !== null) {
            path.unshift(current);
            current = previous.get(current)!;
        }
        
        return path[0] === start ? path : [];
    }
}

// Bellman-Ford Algorithm (handles negative weights)
class BellmanFord {
    static findShortestPaths(
        edges: Array<{from: number, to: number, weight: number}>,
        vertices: number[],
        source: number
    ): {distances: Map, hasNegativeCycle: boolean} {
        const distances = new Map();
        
        // Initialize distances
        for (const vertex of vertices) {
            distances.set(vertex, vertex === source ? 0 : Infinity);
        }
        
        // Relax edges V-1 times
        for (let i = 0; i < vertices.length - 1; i++) {
            for (const edge of edges) {
                const {from, to, weight} = edge;
                const fromDist = distances.get(from)!;
                const toDist = distances.get(to)!;
                
                if (fromDist !== Infinity && fromDist + weight < toDist) {
                    distances.set(to, fromDist + weight);
                }
            }
        }
        
        // Check for negative cycles
        let hasNegativeCycle = false;
        for (const edge of edges) {
            const {from, to, weight} = edge;
            const fromDist = distances.get(from)!;
            const toDist = distances.get(to)!;
            
            if (fromDist !== Infinity && fromDist + weight < toDist) {
                hasNegativeCycle = true;
                break;
            }
        }
        
        return {distances, hasNegativeCycle};
    }
}

// Floyd-Warshall Algorithm (all-pairs shortest paths)
class FloydWarshall {
    static allPairsShortestPaths(
        vertices: number[],
        edges: Array<{from: number, to: number, weight: number}>
    ): Map {
        const dist = new Map();
        const n = vertices.length;
        
        // Initialize distances
        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                const key = `${vertices[i]}-${vertices[j]}`;
                dist.set(key, i === j ? 0 : Infinity);
            }
        }
        
        // Set edge weights
        for (const edge of edges) {
            const key = `${edge.from}-${edge.to}`;
            dist.set(key, edge.weight);
        }
        
        // Floyd-Warshall main loop
        for (let k = 0; k < n; k++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    const ikKey = `${vertices[i]}-${vertices[k]}`;
                    const kjKey = `${vertices[k]}-${vertices[j]}`;
                    const ijKey = `${vertices[i]}-${vertices[j]}`;
                    
                    const ikDist = dist.get(ikKey)!;
                    const kjDist = dist.get(kjKey)!;
                    const ijDist = dist.get(ijKey)!;
                    
                    if (ikDist + kjDist < ijDist) {
                        dist.set(ijKey, ikDist + kjDist);
                    }
                }
            }
        }
        
        return dist;
    }
}

Python

import heapq
from collections import defaultdict
from typing import Dict, List, Tuple, Optional

class Graph:
    def __init__(self):
        self.adjacency_list = defaultdict(list)
    
    def add_edge(self, from_vertex: int, to_vertex: int, weight: int):
        self.adjacency_list[from_vertex].append((to_vertex, weight))
    
    def dijkstra(self, start: int) -> Tuple[Dict[int, int], Dict[int, Optional[int]]]:
        """Dijkstra's algorithm for shortest paths"""
        distances = defaultdict(lambda: float('inf'))
        previous = {}
        distances[start] = 0
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_distance, current = heapq.heappop(pq)
            
            if current in visited:
                continue
                
            visited.add(current)
            
            for neighbor, weight in self.adjacency_list[current]:
                distance = current_distance + weight
                
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current
                    heapq.heappush(pq, (distance, neighbor))
        
        return dict(distances), previous
    
    def get_shortest_path(self, start: int, end: int) -> List[int]:
        """Get shortest path between two vertices"""
        _, previous = self.dijkstra(start)
        
        if end not in previous:
            return []
        
        path = []
        current = end
        
        while current is not None:
            path.append(current)
            current = previous.get(current)
        
        path.reverse()
        return path if path[0] == start else []

def bellman_ford(edges: List[Tuple[int, int, int]], 
                vertices: List[int], 
                source: int) -> Tuple[Dict[int, int], bool]:
    """Bellman-Ford algorithm (handles negative weights)"""
    distances = {v: float('inf') for v in vertices}
    distances[source] = 0
    
    # Relax edges V-1 times
    for _ in range(len(vertices) - 1):
        for from_v, to_v, weight in edges:
            if distances[from_v] != float('inf') and \
               distances[from_v] + weight < distances[to_v]:
                distances[to_v] = distances[from_v] + weight
    
    # Check for negative cycles
    has_negative_cycle = False
    for from_v, to_v, weight in edges:
        if distances[from_v] != float('inf') and \
           distances[from_v] + weight < distances[to_v]:
            has_negative_cycle = True
            break
    
    return distances, has_negative_cycle

def floyd_warshall(vertices: List[int], 
                  edges: List[Tuple[int, int, int]]) -> Dict[Tuple[int, int], int]:
    """Floyd-Warshall algorithm for all-pairs shortest paths"""
    n = len(vertices)
    dist = {}
    
    # Initialize distances
    for i in range(n):
        for j in range(n):
            key = (vertices[i], vertices[j])
            dist[key] = 0 if i == j else float('inf')
    
    # Set edge weights
    for from_v, to_v, weight in edges:
        dist[(from_v, to_v)] = weight
    
    # Floyd-Warshall main loop
    for k in range(n):
        for i in range(n):
            for j in range(n):
                v_k = vertices[k]
                v_i = vertices[i]
                v_j = vertices[j]
                
                if dist[(v_i, v_k)] + dist[(v_k, v_j)] < dist[(v_i, v_j)]:
                    dist[(v_i, v_j)] = dist[(v_i, v_k)] + dist[(v_k, v_j)]
    
    return dist

# A* Algorithm for pathfinding with heuristic
def a_star(graph: Dict[int, List[Tuple[int, int]]], 
          start: int, 
          goal: int, 
          heuristic: Dict[int, int]) -> List[int]:
    """A* pathfinding algorithm with heuristic"""
    open_set = [(0, start)]
    came_from = {}
    g_score = defaultdict(lambda: float('inf'))
    g_score[start] = 0
    f_score = defaultdict(lambda: float('inf'))
    f_score[start] = heuristic[start]
    
    while open_set:
        current = heapq.heappop(open_set)[1]
        
        if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]
        
        for neighbor, weight in graph.get(current, []):
            tentative_g = g_score[current] + weight
            
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = tentative_g + heuristic[neighbor]
                heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return []  # No path found

# Johnson's Algorithm (all-pairs with negative weights)
def johnsons_algorithm(vertices: List[int], 
                      edges: List[Tuple[int, int, int]]) -> Dict[Tuple[int, int], int]:
    """Johnson's algorithm for all-pairs shortest paths with negative weights"""
    # Add auxiliary vertex connected to all vertices with weight 0
    aux_vertex = max(vertices) + 1
    extended_edges = edges + [(aux_vertex, v, 0) for v in vertices]
    extended_vertices = vertices + [aux_vertex]
    
    # Run Bellman-Ford from auxiliary vertex
    h, has_negative_cycle = bellman_ford(extended_edges, extended_vertices, aux_vertex)
    
    if has_negative_cycle:
        raise ValueError("Graph contains negative cycle")
    
    # Reweight edges
    reweighted_edges = []
    for from_v, to_v, weight in edges:
        new_weight = weight + h[from_v] - h[to_v]
        reweighted_edges.append((from_v, to_v, new_weight))
    
    # Build graph for Dijkstra
    graph = defaultdict(list)
    for from_v, to_v, weight in reweighted_edges:
        graph[from_v].append((to_v, weight))
    
    # Run Dijkstra from each vertex
    all_distances = {}
    for source in vertices:
        graph_obj = Graph()
        for from_v, neighbors in graph.items():
            for to_v, weight in neighbors:
                graph_obj.add_edge(from_v, to_v, weight)
        
        distances, _ = graph_obj.dijkstra(source)
        
        # Restore original weights
        for target in vertices:
            if target in distances:
                original_distance = distances[target] - h[source] + h[target]
                all_distances[(source, target)] = original_distance
    
    return all_distances

OCaml

(* Priority Queue implementation using binary heap *)
module PriorityQueue = struct
  type 'a t = {
    mutable heap: ('a * int) array;
    mutable size: int;
  }
  
  let create capacity = {
    heap = Array.make capacity (Obj.magic (), 0);
    size = 0;
  }
  
  let parent i = (i - 1) / 2
  let left_child i = 2 * i + 1
  let right_child i = 2 * i + 2
  
  let swap heap i j =
    let temp = heap.(i) in
    heap.(i) <- heap.(j);
    heap.(j) <- temp
  
  let rec heapify_up heap i =
    if i > 0 then
      let p = parent i in
      if snd heap.(i) < snd heap.(p) then begin
        swap heap i p;
        heapify_up heap p
      end
  
  let rec heapify_down heap size i =
    let l = left_child i in
    let r = right_child i in
    let smallest = ref i in
    
    if l < size && snd heap.(l) < snd heap.(!smallest) then
      smallest := l;
    
    if r < size && snd heap.(r) < snd heap.(!smallest) then
      smallest := r;
    
    if !smallest <> i then begin
      swap heap i !smallest;
      heapify_down heap size !smallest
    end
  
  let enqueue pq item priority =
    let {heap; size} = pq in
    heap.(size) <- (item, priority);
    heapify_up heap size;
    pq.size <- size + 1
  
  let dequeue pq =
    if pq.size = 0 then None
    else begin
      let result = fst pq.heap.(0) in
      pq.size <- pq.size - 1;
      if pq.size > 0 then begin
        pq.heap.(0) <- pq.heap.(pq.size);
        heapify_down pq.heap pq.size 0
      end;
      Some result
    end
  
  let is_empty pq = pq.size = 0
end

(* Graph representation *)
module Graph = struct
  type t = (int, (int * int) list) Hashtbl.t
  
  let create () = Hashtbl.create 16
  
  let add_edge graph from_v to_v weight =
    let neighbors = try Hashtbl.find graph from_v with Not_found -> [] in
    Hashtbl.replace graph from_v ((to_v, weight) :: neighbors)
  
  (* Dijkstra's algorithm *)
  let dijkstra graph start =
    let distances = Hashtbl.create 16 in
    let previous = Hashtbl.create 16 in
    let pq = PriorityQueue.create 100 in
    let visited = Hashtbl.create 16 in
    
    (* Initialize distances *)
    Hashtbl.iter (fun vertex _ ->
      Hashtbl.add distances vertex (if vertex = start then 0 else max_int);
      Hashtbl.add previous vertex None
    ) graph;
    
    PriorityQueue.enqueue pq start 0;
    
    let rec loop () =
      match PriorityQueue.dequeue pq with
      | None -> ()
      | Some current ->
          if not (Hashtbl.mem visited current) then begin
            Hashtbl.add visited current true;
            let current_dist = Hashtbl.find distances current in
            
            let neighbors = try Hashtbl.find graph current with Not_found -> [] in
            List.iter (fun (neighbor, weight) ->
              let new_dist = current_dist + weight in
              let old_dist = Hashtbl.find distances neighbor in
              if new_dist < old_dist then begin
                Hashtbl.replace distances neighbor new_dist;
                Hashtbl.replace previous neighbor (Some current);
                PriorityQueue.enqueue pq neighbor new_dist
              end
            ) neighbors
          end;
          loop ()
    in
    
    loop ();
    (distances, previous)
  
  let get_shortest_path graph start target =
    let (_, previous) = dijkstra graph start in
    let rec build_path acc current =
      match Hashtbl.find previous current with
      | None -> if current = start then current :: acc else []
      | Some prev -> build_path (current :: acc) prev
    in
    try build_path [] target
    with Not_found -> []
end

(* Bellman-Ford algorithm *)
let bellman_ford edges vertices source =
  let distances = Hashtbl.create 16 in
  
  (* Initialize distances *)
  List.iter (fun v ->
    Hashtbl.add distances v (if v = source then 0 else max_int)
  ) vertices;
  
  (* Relax edges V-1 times *)
  for _ = 1 to List.length vertices - 1 do
    List.iter (fun (from_v, to_v, weight) ->
      let from_dist = Hashtbl.find distances from_v in
      let to_dist = Hashtbl.find distances to_v in
      if from_dist <> max_int && from_dist + weight < to_dist then
        Hashtbl.replace distances to_v (from_dist + weight)
    ) edges
  done;
  
  (* Check for negative cycles *)
  let has_negative_cycle = ref false in
  List.iter (fun (from_v, to_v, weight) ->
    let from_dist = Hashtbl.find distances from_v in
    let to_dist = Hashtbl.find distances to_v in
    if from_dist <> max_int && from_dist + weight < to_dist then
      has_negative_cycle := true
  ) edges;
  
  (distances, !has_negative_cycle)

(* Floyd-Warshall algorithm *)
let floyd_warshall vertices edges =
  let n = List.length vertices in
  let dist = Hashtbl.create (n * n) in
  
  (* Initialize distances *)
  List.iteri (fun i v_i ->
    List.iteri (fun j v_j ->
      let key = (v_i, v_j) in
      Hashtbl.add dist key (if i = j then 0 else max_int)
    ) vertices
  ) vertices;
  
  (* Set edge weights *)
  List.iter (fun (from_v, to_v, weight) ->
    Hashtbl.replace dist (from_v, to_v) weight
  ) edges;
  
  (* Main Floyd-Warshall loop *)
  List.iter (fun v_k ->
    List.iter (fun v_i ->
      List.iter (fun v_j ->
        let ik_dist = try Hashtbl.find dist (v_i, v_k) with Not_found -> max_int in
        let kj_dist = try Hashtbl.find dist (v_k, v_j) with Not_found -> max_int in
        let ij_dist = try Hashtbl.find dist (v_i, v_j) with Not_found -> max_int in
        if ik_dist <> max_int && kj_dist <> max_int && 
           ik_dist + kj_dist < ij_dist then
          Hashtbl.replace dist (v_i, v_j) (ik_dist + kj_dist)
      ) vertices
    ) vertices
  ) vertices;
  dist

⏱️ Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Best Use Case
Dijkstra's	O((V + E) log V)	O(V)	Single source, non-negative weights
Bellman-Ford	O(VE)	O(V)	Single source, negative weights
Floyd-Warshall	O(V³)	O(V²)	All pairs shortest paths
A*	O(b^d)	O(b^d)	Pathfinding with heuristic

Tarjan's Algorithm for Strongly Connected Components

Strongly Connected Components (SCC)

Tarjan's algorithm finds all strongly connected components in a directed graph in linear time. A strongly connected component is a maximal set of vertices where every vertex is reachable from every other vertex in the set.

🌐 Real-Life Analogy:

Think of social media networks where users follow each other. A strongly connected component represents a group where everyone can reach everyone else through mutual connections - like a tight-knit community where information can flow in all directions.

📊 DFS Traversal Visualization:

Graph:     A → B → C
           ↑   ↓   ↓
           D ← E ← F

DFS Stack Evolution:
Step 1: [A] - discovery[A]=0, low[A]=0
Step 2: [A,B] - discovery[B]=1, low[B]=1  
Step 3: [A,B,C] - discovery[C]=2, low[C]=2
Step 4: [A,B,C,F] - discovery[F]=3, low[F]=3
Step 5: [A,B,C,F,E] - discovery[E]=4, low[E]=4
Step 6: [A,B,C,F,E,D] - discovery[D]=5, low[D]=5
Step 7: Back edge D→A: low[D] = min(low[D], discovery[A]) = 0

SCC Found: {A,B,C,D,E,F} when low[A] == discovery[A]

TypeScript

class TarjanSCC {
    private graph: Map;
    private time: number;
    private stack: number[];
    private onStack: Set;
    private discovered: Map;
    private low: Map;
    private sccs: number[][];

    constructor() {
        this.graph = new Map();
        this.time = 0;
        this.stack = [];
        this.onStack = new Set();
        this.discovered = new Map();
        this.low = new Map();
        this.sccs = [];
    }

    addEdge(from: number, to: number): void {
        if (!this.graph.has(from)) {
            this.graph.set(from, []);
        }
        this.graph.get(from)!.push(to);
    }

    findSCCs(): number[][] {
        // Initialize all vertices
        for (const vertex of this.graph.keys()) {
            if (!this.discovered.has(vertex)) {
                this.dfs(vertex);
            }
        }
        return this.sccs;
    }

    private dfs(vertex: number): void {
        // Initialize discovery time and low value
        this.discovered.set(vertex, this.time);
        this.low.set(vertex, this.time);
        this.time++;
        
        // Push current vertex to stack
        this.stack.push(vertex);
        this.onStack.add(vertex);

        // Visit all adjacent vertices
        const neighbors = this.graph.get(vertex) || [];
        for (const neighbor of neighbors) {
            if (!this.discovered.has(neighbor)) {
                // Tree edge: recursively visit
                this.dfs(neighbor);
                this.low.set(vertex, Math.min(
                    this.low.get(vertex)!,
                    this.low.get(neighbor)!
                ));
            } else if (this.onStack.has(neighbor)) {
                // Back edge: update low value
                this.low.set(vertex, Math.min(
                    this.low.get(vertex)!,
                    this.discovered.get(neighbor)!
                ));
            }
        }

        // If vertex is a root of SCC
        if (this.low.get(vertex) === this.discovered.get(vertex)) {
            const scc: number[] = [];
            let current: number;
            
            // Pop vertices from stack until current vertex
            do {
                current = this.stack.pop()!;
                this.onStack.delete(current);
                scc.push(current);
            } while (current !== vertex);
            
            this.sccs.push(scc);
        }
    }

    // Check if graph is strongly connected
    isStronglyConnected(): boolean {
        const sccs = this.findSCCs();
        return sccs.length === 1;
    }

    // Find condensation graph (DAG of SCCs)
    getCondensationGraph(): {nodes: number[], edges: Array<{from: number, to: number}>} {
        const sccs = this.findSCCs();
        const vertexToSCC = new Map();
        
        // Map each vertex to its SCC index
        sccs.forEach((scc, index) => {
            scc.forEach(vertex => {
                vertexToSCC.set(vertex, index);
            });
        });

        const condensationEdges = new Set();
        
        // Add edges between different SCCs
        for (const [from, neighbors] of this.graph) {
            const fromSCC = vertexToSCC.get(from)!;
            for (const to of neighbors) {
                const toSCC = vertexToSCC.get(to)!;
                if (fromSCC !== toSCC) {
                    condensationEdges.add(`${fromSCC}-${toSCC}`);
                }
            }
        }

        const edges = Array.from(condensationEdges).map(edge => {
            const [from, to] = edge.split('-').map(Number);
            return {from, to};
        });

        return {
            nodes: Array.from({length: sccs.length}, (_, i) => i),
            edges
        };
    }
}

// Usage example for social network analysis
class SocialNetworkAnalyzer {
    static findCommunities(followGraph: Map): string[][] {
        const tarjan = new TarjanSCC();
        const userToId = new Map();
        const idToUser = new Map();
        let nextId = 0;

        // Convert usernames to numeric IDs
        for (const [user, follows] of followGraph) {
            if (!userToId.has(user)) {
                userToId.set(user, nextId);
                idToUser.set(nextId, user);
                nextId++;
            }
            for (const followed of follows) {
                if (!userToId.has(followed)) {
                    userToId.set(followed, nextId);
                    idToUser.set(nextId, followed);
                    nextId++;
                }
            }
        }

        // Build graph with numeric IDs
        for (const [user, follows] of followGraph) {
            const userId = userToId.get(user)!;
            for (const followed of follows) {
                const followedId = userToId.get(followed)!;
                tarjan.addEdge(userId, followedId);
            }
        }

        // Find SCCs and convert back to usernames
        const numericSCCs = tarjan.findSCCs();
        return numericSCCs.map(scc => 
            scc.map(id => idToUser.get(id)!)
        );
    }
}

Python

from collections import defaultdict
from typing import List, Dict, Set, Tuple

class TarjanSCC:
    def __init__(self):
        self.graph = defaultdict(list)
        self.time = 0
        self.stack = []
        self.on_stack = set()
        self.discovered = {}
        self.low = {}
        self.sccs = []
    
    def add_edge(self, from_vertex: int, to_vertex: int):
        """Add directed edge to graph"""
        self.graph[from_vertex].append(to_vertex)
    
    def find_sccs(self) -> List[List[int]]:
        """Find all strongly connected components"""
        self.time = 0
        self.stack = []
        self.on_stack = set()
        self.discovered = {}
        self.low = {}
        self.sccs = []
        
        # Get all vertices
        vertices = set(self.graph.keys())
        for neighbors in self.graph.values():
            vertices.update(neighbors)
        
        # Run DFS from each unvisited vertex
        for vertex in vertices:
            if vertex not in self.discovered:
                self._dfs(vertex)
        
        return self.sccs
    
    def _dfs(self, vertex: int):
        """DFS with Tarjan's algorithm logic"""
        # Initialize discovery time and low value
        self.discovered[vertex] = self.time
        self.low[vertex] = self.time
        self.time += 1
        
        # Push to stack
        self.stack.append(vertex)
        self.on_stack.add(vertex)
        
        # Visit all neighbors
        for neighbor in self.graph[vertex]:
            if neighbor not in self.discovered:
                # Tree edge
                self._dfs(neighbor)
                self.low[vertex] = min(self.low[vertex], self.low[neighbor])
            elif neighbor in self.on_stack:
                # Back edge
                self.low[vertex] = min(self.low[vertex], self.discovered[neighbor])
        
        # Check if vertex is root of SCC
        if self.low[vertex] == self.discovered[vertex]:
            scc = []
            while True:
                current = self.stack.pop()
                self.on_stack.remove(current)
                scc.append(current)
                if current == vertex:
                    break
            self.sccs.append(scc)
    
    def is_strongly_connected(self) -> bool:
        """Check if entire graph is strongly connected"""
        sccs = self.find_sccs()
        return len(sccs) == 1
    
    def get_condensation_graph(self) -> Tuple[List[int], List[Tuple[int, int]]]:
        """Get condensation graph (DAG of SCCs)"""
        sccs = self.find_sccs()
        vertex_to_scc = {}
        
        # Map vertices to SCC indices
        for i, scc in enumerate(sccs):
            for vertex in scc:
                vertex_to_scc[vertex] = i
        
        # Find edges between different SCCs
        condensation_edges = set()
        for from_vertex, neighbors in self.graph.items():
            from_scc = vertex_to_scc[from_vertex]
            for to_vertex in neighbors:
                to_scc = vertex_to_scc[to_vertex]
                if from_scc != to_scc:
                    condensation_edges.add((from_scc, to_scc))
        
        nodes = list(range(len(sccs)))
        edges = list(condensation_edges)
        return nodes, edges

def web_crawler_analysis(web_links: Dict[str, List[str]]) -> List[List[str]]:
    """Analyze web pages for strongly connected link clusters"""
    tarjan = TarjanSCC()
    url_to_id = {}
    id_to_url = {}
    next_id = 0
    
    # Convert URLs to numeric IDs
    for url, links in web_links.items():
        if url not in url_to_id:
            url_to_id[url] = next_id
            id_to_url[next_id] = url
            next_id += 1
        
        for link in links:
            if link not in url_to_id:
                url_to_id[link] = next_id
                id_to_url[next_id] = link
                next_id += 1
    
    # Build graph
    for url, links in web_links.items():
        url_id = url_to_id[url]
        for link in links:
            link_id = url_to_id[link]
            tarjan.add_edge(url_id, link_id)
    
    # Find SCCs and convert back to URLs
    numeric_sccs = tarjan.find_sccs()
    return [[id_to_url[node_id] for node_id in scc] for scc in numeric_sccs]

# Example: Kosaraju's algorithm alternative
def kosaraju_scc(graph: Dict[int, List[int]]) -> List[List[int]]:
    """Alternative SCC algorithm using two DFS passes"""
    def dfs1(vertex, visited, stack):
        visited.add(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                dfs1(neighbor, visited, stack)
        stack.append(vertex)
    
    def dfs2(vertex, visited, component, transpose):
        visited.add(vertex)
        component.append(vertex)
        for neighbor in transpose.get(vertex, []):
            if neighbor not in visited:
                dfs2(neighbor, visited, component, transpose)
    
    # Get all vertices
    vertices = set(graph.keys())
    for neighbors in graph.values():
        vertices.update(neighbors)
    
    # First DFS to get finish times
    visited = set()
    stack = []
    for vertex in vertices:
        if vertex not in visited:
            dfs1(vertex, visited, stack)
    
    # Create transpose graph
    transpose = defaultdict(list)
    for vertex, neighbors in graph.items():
        for neighbor in neighbors:
            transpose[neighbor].append(vertex)
    
    # Second DFS on transpose in reverse finish order
    visited = set()
    sccs = []
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            component = []
            dfs2(vertex, visited, component, transpose)
            sccs.append(component)
    
    return sccs

OCaml

(* Tarjan's Strongly Connected Components Algorithm *)
module TarjanSCC = struct
  type graph = (int, int list) Hashtbl.t
  
  type state = {
    mutable time: int;
    mutable stack: int list;
    on_stack: (int, bool) Hashtbl.t;
    discovered: (int, int) Hashtbl.t;
    low: (int, int) Hashtbl.t;
    mutable sccs: int list list;
  }
  
  let create_state () = {
    time = 0;
    stack = [];
    on_stack = Hashtbl.create 16;
    discovered = Hashtbl.create 16;
    low = Hashtbl.create 16;
    sccs = [];
  }
  
  let add_edge graph from_v to_v =
    let neighbors = try Hashtbl.find graph from_v with Not_found -> [] in
    Hashtbl.replace graph from_v (to_v :: neighbors)
  
  let rec dfs graph state vertex =
    (* Initialize discovery time and low value *)
    Hashtbl.add state.discovered vertex state.time;
    Hashtbl.add state.low vertex state.time;
    state.time <- state.time + 1;
    
    (* Push to stack *)
    state.stack <- vertex :: state.stack;
    Hashtbl.add state.on_stack vertex true;
    
    (* Visit all neighbors *)
    let neighbors = try Hashtbl.find graph vertex with Not_found -> [] in
    List.iter (fun neighbor ->
      if not (Hashtbl.mem state.discovered neighbor) then begin
        (* Tree edge *)
        dfs graph state neighbor;
        let low_vertex = Hashtbl.find state.low vertex in
        let low_neighbor = Hashtbl.find state.low neighbor in
        Hashtbl.replace state.low vertex (min low_vertex low_neighbor)
      end else if Hashtbl.mem state.on_stack neighbor then begin
        (* Back edge *)
        let low_vertex = Hashtbl.find state.low vertex in
        let disc_neighbor = Hashtbl.find state.discovered neighbor in
        Hashtbl.replace state.low vertex (min low_vertex disc_neighbor)
      end
    ) neighbors;
    
    (* Check if vertex is root of SCC *)
    let low_vertex = Hashtbl.find state.low vertex in
    let disc_vertex = Hashtbl.find state.discovered vertex in
    if low_vertex = disc_vertex then begin
      let rec pop_scc acc =
        match state.stack with
        | [] -> acc
        | current :: rest ->
            state.stack <- rest;
            Hashtbl.remove state.on_stack current;
            let new_acc = current :: acc in
            if current = vertex then new_acc
            else pop_scc new_acc
      in
      let scc = pop_scc [] in
      state.sccs <- scc :: state.sccs
    end
  
  let find_sccs graph =
    let state = create_state () in
    
    (* Get all vertices *)
    let vertices = Hashtbl.fold (fun v neighbors acc ->
      let all_neighbors = List.fold_left (fun acc n -> n :: acc) acc neighbors in
      v :: all_neighbors
    ) graph [] in
    let unique_vertices = List.sort_uniq compare vertices in
    
    (* Run DFS from each unvisited vertex *)
    List.iter (fun vertex ->
      if not (Hashtbl.mem state.discovered vertex) then
        dfs graph state vertex
    ) unique_vertices;
    
    List.rev state.sccs
  
  let is_strongly_connected graph =
    let sccs = find_sccs graph in
    List.length sccs = 1
  
  let get_condensation_graph graph =
    let sccs = find_sccs graph in
    let vertex_to_scc = Hashtbl.create 16 in
    
    (* Map vertices to SCC indices *)
    List.iteri (fun i scc ->
      List.iter (fun vertex ->
        Hashtbl.add vertex_to_scc vertex i
      ) scc
    ) sccs;
    
    (* Find edges between different SCCs *)
    let condensation_edges = ref [] in
    Hashtbl.iter (fun from_vertex neighbors ->
      let from_scc = Hashtbl.find vertex_to_scc from_vertex in
      List.iter (fun to_vertex ->
        let to_scc = Hashtbl.find vertex_to_scc to_vertex in
        if from_scc <> to_scc then
          condensation_edges := (from_scc, to_scc) :: !condensation_edges
      ) neighbors
    ) graph;
    
    let unique_edges = List.sort_uniq compare !condensation_edges in
    let nodes = Array.to_list (Array.init (List.length sccs) (fun i -> i)) in
    (nodes, unique_edges)
end

(* Application: Web crawling analysis *)
let analyze_web_graph url_links =
  let graph = Hashtbl.create 16 in
  let url_to_id = Hashtbl.create 16 in
  let id_to_url = Hashtbl.create 16 in
  let next_id = ref 0 in
  
  (* Convert URLs to numeric IDs *)
  List.iter (fun (url, links) ->
    if not (Hashtbl.mem url_to_id url) then begin
      Hashtbl.add url_to_id url !next_id;
      Hashtbl.add id_to_url !next_id url;
      incr next_id
    end;
    List.iter (fun link ->
      if not (Hashtbl.mem url_to_id link) then begin
        Hashtbl.add url_to_id link !next_id;
        Hashtbl.add id_to_url !next_id link;
        incr next_id
      end
    ) links
  ) url_links;
  
  (* Build numeric graph *)
  List.iter (fun (url, links) ->
    let url_id = Hashtbl.find url_to_id url in
    List.iter (fun link ->
      let link_id = Hashtbl.find url_to_id link in
      TarjanSCC.add_edge graph url_id link_id
    ) links
  ) url_links;
  
  (* Find SCCs and convert back to URLs *)
  let numeric_sccs = TarjanSCC.find_sccs graph in
  List.map (fun scc ->
    List.map (fun id -> Hashtbl.find id_to_url id) scc
  ) numeric_sccs

⏱️ Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Find all SCCs	O(V + E)	O(V)	Linear time, single DFS pass
Condensation graph	O(V + E)	O(V + E)	Creates DAG representation
Strong connectivity check	O(V + E)	O(V)	Single SCC means strongly connected

🌍 Real-World Applications

Social Networks: Find communities where users mutually follow each other
Web Crawling: Identify clusters of pages that link to each other
Dependency Analysis: Find circular dependencies in software modules
Circuit Analysis: Identify strongly connected components in electrical circuits
Call Graph Analysis: Find recursive function groups in programs

Articulation Points and Bridges

Critical Network Components

Articulation points (cut vertices) are vertices whose removal increases the number of connected components. Bridges (cut edges) are edges whose removal increases the number of connected components. These are critical for network reliability analysis.

🌉 Real-Life Analogy:

Think of a transportation network where articulation points are critical intersections and bridges are critical roads. If a bridge collapses or an intersection is blocked, parts of the network become disconnected, causing major disruptions.

⏱️ Complexity Analysis

Operation	Time Complexity	Space Complexity	Notes
Find articulation points	O(V + E)	O(V)	Single DFS traversal
Find bridges	O(V + E)	O(V)	Same traversal as articulation points

🌍 Real-World Applications

Network Reliability: Identify critical infrastructure points and connections
Transportation Systems: Find critical intersections and roads in traffic networks
Communication Networks: Locate critical routers and links in internet infrastructure
Social Network Analysis: Find key influencers whose removal fragments communities
Supply Chain Management: Identify critical suppliers and distribution points

Network Flow Algorithms

Maximum Flow and Minimum Cut

Network flow algorithms solve problems related to finding the maximum amount of flow that can be sent from a source to a sink in a flow network. The Ford-Fulkerson method and its implementations like Edmonds-Karp are fundamental algorithms for this problem.

🚰 Real-Life Analogy:

Think of a water distribution system with pipes of different capacities. You want to find the maximum amount of water that can flow from a reservoir (source) to a city (sink) through the network of pipes, where each pipe has a maximum capacity constraint.

⏱️ Complexity Analysis

Algorithm	Time Complexity	Space Complexity	Notes
Ford-Fulkerson	O(E × max_flow)	O(V + E)	With DFS path finding
Edmonds-Karp	O(VE²)	O(V + E)	With BFS path finding
Dinic's Algorithm	O(V²E)	O(V + E)	Uses level graphs and blocking flows

🌍 Real-World Applications

Resource Allocation: Optimal distribution of resources across networks
Traffic Flow: Maximize vehicle throughput in transportation networks
Network Capacity: Find bottlenecks in communication networks
Supply Chain: Optimize material flow through manufacturing pipelines
Bipartite Matching: Assignment problems like job scheduling

A* Search Algorithm

Heuristic-Based Pathfinding

A* is an extension of Dijkstra's algorithm that uses a heuristic function to guide the search toward the goal more efficiently. It guarantees the shortest path if the heuristic is admissible (never overestimates the true cost).

🧭 Real-Life Analogy:

Think of using a GPS with traffic prediction. While Dijkstra's explores all roads equally, A* is like having a smart navigator that prioritizes roads that seem to lead toward your destination, using both the distance traveled and an estimate of remaining distance.

📊 A* vs Dijkstra Comparison:

Grid Pathfinding (S = Start, G = Goal, # = Wall):

S . . . . G
. # # . . .
. . . . # .
. # # . . .
. . . . . .

Dijkstra explores: O O O O O G
                   O # # O O O
                   O O O O # O
                   O # # O O O
                   O O O O O O

A* with Manhattan heuristic explores:
                   S → → → → G
                   ↓ # # → → ↑
                   ↓ ↓ ↓ → # ↑
                   ↓ # # → → ↑
                   ↓ ↓ ↓ ↓ ↓ ↓

A* explores fewer nodes by focusing on promising directions!

⏱️ Complexity Analysis

Scenario	Time Complexity	Space Complexity	Notes
Perfect heuristic	O(d)	O(d)	Follows optimal path directly
Admissible heuristic	O(b^d)	O(b^d)	b = branching factor, d = depth
Poor heuristic	O(b^d)	O(b^d)	Degrades to breadth-first search

💡 Interview Key Points

Heuristic Design: Must be admissible (h(n) ≤ actual cost) for optimality
f(n) = g(n) + h(n): Total cost = actual cost + heuristic estimate
vs Dijkstra: A* uses domain knowledge to search smarter, not harder
vs Greedy: A* considers both path cost and heuristic, ensuring optimality
Trade-offs: Better heuristics mean faster search but more computation per node

🌍 Real-World Applications

Game AI: Pathfinding for NPCs in video games
Robotics: Navigation planning for autonomous vehicles
GPS Navigation: Route planning with traffic and road conditions
Puzzle Solving: Finding optimal solutions in search spaces
Network Routing: Efficient packet routing in computer networks