api: YAML JSON TOON Database
version: 1.0.0
format: toon
dataset:
  id: 2801
  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."
  summary: "Essential graph algorithms with category, time and space complexity, description, use cases, pseudocode and notes: BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, Kruskal, topological sort, union-find and Ford-Fulkerson, plus graph representations."
  use_when[2]: "You need a shortest-path, spanning-tree, ordering or connectivity algorithm and its complexity.",You are choosing a graph representation.
  caveats[2]: Dijkstra's algorithm requires non-negative edge weights; use Bellman-Ford when negative edges are possible.,Complexity depends on the data structure used for the priority queue or the graph.
  related[4]: graph-traversal-algorithms,advanced-graph-algorithms,greedy-algorithms,tree-data-structures
  entry_count: 10
  fields[14]{section,field,type,example}:
    algorithms,name,string,Breadth-First Search (BFS)
    algorithms,category,string,Traversal
    algorithms,time_complexity,string,O(V + E)
    algorithms,space_complexity,string,O(V)
    algorithms,description,string,Visits nodes level by level using queue; finds …
    algorithms,use_cases,array,"[4 items]"
    algorithms,pseudocode,string,"queue ← [start]; visited ← {start}; while queue…"
    algorithms,notes,string,Guarantees shortest path in unweighted graphs; …
    algorithms,input_requirements,string,Weighted directed/undirected graph; all edge we…
    algorithms,algorithms,array,"[2 items]"
    algorithms,pseudocode_kahn,string,compute indegree of all nodes; queue ← all node…
    algorithms,operations,object,"{find,union}"
    algorithms,variants,array,"[3 items]"
    graph_representations,*,object,"{adjacency_matrix,adjacency_list,edge_list}"
  category: Data Structures
  category_slug: data-structures
  tags: "graphs,algorithms,bfs,dfs,dijkstra,mst,topological-sort,network-flow"
  view_count: 53
  created_at: 1777673262
  updated_at: 1777673262
data:
  algorithms[10]:
    - 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[4]: 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[5]: 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[2]: "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[4]: "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[4]: 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[3]: "Edmonds-Karp (BFS augmenting paths, O(VE²))","Dinic's (O(V²E), blocking flows)",Push-relabel (O(V³))
      use_cases[4]: 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[3]: O(1) edge lookup,Simple,Good for dense graphs
      cons[2]: O(V²) space even if sparse,Iterating neighbors O(V)
    adjacency_list:
      space: O(V + E)
      pros[2]: Space efficient for sparse graphs,Fast neighbor iteration
      cons[2]: O(degree(v)) edge existence check,Slower for dense graphs
    edge_list:
      space: O(E)
      pros[2]: Simple,Good for algorithms that process all edges (Kruskal)
      cons[2]: Slow edge lookup O(E),No fast neighbor access