api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 415
  slug: graph-algorithms
  title: Graph Algorithms
  description: "Essential graph algorithms: traversals (BFS, DFS), shortest path (Dijkstra, Bellman-Ford), minimum spanning tree (Prim, Kruskal), topological sort, and network flow."
  category: Data Structures
  category_slug: data-structures
  tags: graphs,algorithms,bfs,dfs,dijkstra,mst,topological-sort,network-flow
  view_count: 1
  created_at: 1781275786
  updated_at: 1781275786
data:
  algorithms:
    - name: Breadth-First Search (BFS)
      category: Traversal
      time_complexity: O(V + E)
      space_complexity: O(V)
      description: Visits nodes level by level using queue; finds shortest path in unweighted graphs.
      use_cases:
        - Shortest path (unweighted)
        - Web crawling
        - Social network friend suggestions
        - Garbage collection (mark-sweep)
      pseudocode: "queue ← [start]; visited ← {start}; while queue not empty: node ← queue.pop(); for each neighbor of node: if neighbor not visited: visited.add(neighbor); queue.push(neighbor)"
      notes: Guarantees shortest path in unweighted graphs; uses more memory than DFS
    - name: Depth-First Search (DFS)
      category: Traversal
      time_complexity: O(V + E)
      space_complexity: O(V) (recursion stack or explicit stack)
      description: Explores as far as possible along each branch before backtracking; uses stack (implicit or explicit).
      use_cases:
        - Cycle detection
        - Topological sorting
        - Maze solving
        - Connected components
        - Path existence
      pseudocode: "stack ← [start]; visited ← {}; while stack not empty: node ← stack.pop(); if node not visited: visited.add(node); for each neighbor of node: if neighbor not visited: stack.push(neighbor)"
      notes: Lower memory footprint than BFS; can get stuck in deep infinite branches (use iterative deepening or IDDFS)
    - name: Dijkstra's Algorithm
      category: Shortest Path
      time_complexity: O((V + E) log V) with min-heap, O(V²) with array
      space_complexity: O(V)
      description: Single-source shortest path for graphs with non-negative edge weights.
      input_requirements: Weighted directed/undirected graph; all edge weights ≥ 0
      pseudocode: "dist[start] ← 0; pq ← min-heap of (distance, node); while pq not empty: d, u ← pq.pop(); if d > dist[u]: continue; for each edge u→v with weight w: if dist[u] + w < dist[v]: dist[v] ← dist[u] + w; pq.push(dist[v], v)"
      notes: Fails with negative weights (use Bellman-Ford); can be optimized with Fibonacci heap (O(V log V + E))
    - name: Bellman-Ford Algorithm
      category: Shortest Path
      time_complexity: O(V × E)
      space_complexity: O(V)
      description: Single-source shortest path handling negative weights; detects negative cycles.
      input_requirements: Weighted directed graph; negative weights allowed but no negative cycles reachable from source
      pseudocode: "dist[all] ← ∞; dist[source] ← 0; repeat V-1 times: for each edge (u,v,w): if dist[u] + w < dist[v]: dist[v] ← dist[u] + w; // Check negative cycle: for each edge (u,v,w): if dist[u] + w < dist[v]: negative cycle exists"
      notes: Slower than Dijkstra but handles negatives; used in currency arbitrage detection; SPFA is optimization in practice
    - name: Floyd-Warshall Algorithm
      category: All-Pairs Shortest Path
      time_complexity: O(V³)
      space_complexity: O(V²)
      description: All-pairs shortest paths for dense graphs; works with negative weights (no negative cycles).
      input_requirements: Directed/undirected weighted graph; no negative cycles
      pseudocode: "for k from 1 to V: for i from 1 to V: for j from 1 to V: dist[i][j] ← min(dist[i][j], dist[i][k] + dist[k][j])"
      notes: Simple triple loop; good for dense graphs (V² space); transitive closure variant
    - name: Prim's Algorithm
      category: Minimum Spanning Tree
      time_complexity: O(E log V) with min-heap, O(V²) with array
      space_complexity: O(V)
      description: Grows MST from a starting node; always adds cheapest edge connecting tree to new vertex.
      pseudocode: "start ← arbitrary node; mst_set ← {start}; while |mst_set| < V: find minimum weight edge (u,v) where u in mst_set, v not in mst_set; add v to mst_set; add edge to MST"
      notes: Like Dijkstra but tracks vertices instead of distances; better for dense graphs
    - name: Kruskal's Algorithm
      category: Minimum Spanning Tree
      time_complexity: O(E log E) (sorting dominates)
      space_complexity: O(V)
      description: Builds MST by adding edges in increasing weight order, skipping those that create cycles.
      pseudocode: "sort edges by weight; mst ← {}; for each edge (u,v,w) in sorted edges: if find(u) ≠ find(v): mst.add(edge); union(u,v); // uses Disjoint Set (Union-Find)"
      notes: Better for sparse graphs; requires Union-Find with path compression (α(n) ≈ constant)
    - name: Topological Sort
      category: Ordering
      time_complexity: O(V + E)
      space_complexity: O(V)
      description: Linear ordering of DAG vertices such that for every edge u→v, u comes before v.
      algorithms:
        - "Kahn's (BFS-based: indegree zero queue)"
        - DFS-based (postorder reverse)
      pseudocode_kahn: "compute indegree of all nodes; queue ← all nodes with indegree 0; while queue not empty: u ← queue.pop(); order.append(u); for each neighbor v of u: indegree[v]--; if indegree[v] == 0: queue.push(v); if order.size < V: cycle detected"
      use_cases:
        - Task scheduling (build systems, job queues)
        - Course prerequisites
        - Dependency resolution
        - Makefiles
      notes: Graph must be DAG; detects cycles; Kahn's also detects cycles
    - name: Union-Find (Disjoint Set)
      category: Connectivity
      time_complexity: O(α(n)) per operation (amortized nearly O(1))
      space_complexity: O(n)
      description: Track partition of elements into disjoint sets; supports union and find operations.
      operations:
        find: Returns representative (root) of set containing element; uses path compression
        union: Merges two sets; uses union by rank/size
      use_cases:
        - Kruskal's MST
        - Connected components
        - Maze generation (Kruskal's)
        - Percolation
      notes: Path compression + union by rank gives amortized α(n) ≈ constant (inverse Ackermann); one of most optimized DS
    - name: Ford-Fulkerson (Max Flow)
      category: Network Flow
      time_complexity: O(E × max_flow) — Edmonds-Karp is O(V × E²)
      space_complexity: O(V + E)
      description: Computes maximum flow from source to sink in flow network; Ford-Fulkerson method with augmenting paths.
      variants:
        - Edmonds-Karp (BFS augmenting paths, O(VE²))
        - Dinic's (O(V²E), blocking flows)
        - Push-relabel (O(V³))
      use_cases:
        - Bipartite matching
        - Assignment problems
        - Network capacity planning
        - Image segmentation (min-cut)
      notes: Integral capacities → integral flow; Dinic's is faster in practice for dense graphs
  graph_representations:
    adjacency_matrix:
      space: O(V²)
      pros:
        - O(1) edge lookup
        - Simple
        - Good for dense graphs
      cons:
        - O(V²) space even if sparse
        - Iterating neighbors O(V)
    adjacency_list:
      space: O(V + E)
      pros:
        - Space efficient for sparse graphs
        - Fast neighbor iteration
      cons:
        - O(degree(v)) edge existence check
        - Slower for dense graphs
    edge_list:
      space: O(E)
      pros:
        - Simple
        - Good for algorithms that process all edges (Kruskal)
      cons:
        - Slow edge lookup O(E)
        - No fast neighbor access