api: "YAML JSON TOON Database"
version: "1.0.0"
format: "json"
dataset:
  id: 26
  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: 0
  created_at: 1777673262
  updated_at: 1777673262
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"