api: YAML JSON TOON Database
version: 1.0.0
format: json
dataset:
  id: 57
  slug: advanced-graph-algorithms
  title: Advanced Graph Algorithms
  description: "Advanced graph algorithms: strongly connected components (Tarjan's, Kosaraju's), max flow (Ford-Fulkerson, Edmonds-Karp, Dinic), matching, and graph coloring."
  summary: "Advanced graph algorithms: strongly connected components (Tarjan, Kosaraju), maximum flow (Ford-Fulkerson, Edmonds-Karp, Dinic), bipartite matching (Hopcroft-Karp), greedy coloring and negative-cycle detection, each with type, time, space, uses and notes."
  use_when[2]: "You need the right algorithm and complexity for a flow, matching or connectivity problem.",You are comparing max-flow algorithms.
  caveats[2]: "Complexity depends on the graph representation and, for flow algorithms, on capacities; bounds are stated for common cases.",Greedy coloring does not give the minimum number of colors in general.
  related[4]: graph-algorithms,graph-traversal-algorithms,complexity-classes,greedy-algorithms
  category: Data Structures
  category_slug: data-structures
  tags: "graphs,algorithms,max-flow,matching,strongly-connected-components,graph-coloring,ford-fulkerson"
  view_count: 0
  created_at: 1778695229
  updated_at: 1778695229
  entry_count: 8
  fields[7]{section,field,type,example}:
    algorithms,name,string,Tarjan's SCC Algorithm
    algorithms,type,string,Strongly Connected Components
    algorithms,time,string,O(V + E)
    algorithms,space,string,O(V)
    algorithms,description,string,Finds all strongly connected components in a di…
    algorithms,use_cases,array,"[4 items]"
    algorithms,notes,string,Single DFS pass; low-link value = lowest discov…
data:
  algorithms[8]:
    - name: Tarjan's SCC Algorithm
      type: Strongly Connected Components
      time: O(V + E)
      space: O(V)
      description: Finds all strongly connected components in a directed graph using DFS with low-link values and a stack
      use_cases[4]: Dependency resolution,Deadlock detection,Circuit analysis,2-SAT solving
      notes: Single DFS pass; low-link value = lowest discovery time reachable from subtree
    - name: Kosaraju's SCC Algorithm
      type: Strongly Connected Components
      time: O(V + E)
      space: O(V)
      description: "Two-pass algorithm: first DFS on original graph for finish times, second DFS on reversed graph in decreasing finish time order"
      use_cases[3]: SCC detection,Graph condensation,Course prerequisite analysis
      notes: Simpler to understand than Tarjan's but requires graph reversal and two passes
    - name: Ford-Fulkerson Algorithm
      type: Maximum Flow
      time: O(E * max_flow)
      space: O(V + E)
      description: Repeatedly finds augmenting paths in residual graph and pushes flow until no path exists
      use_cases[4]: Network flow,Bipartite matching,Baseball elimination,Image segmentation
      notes: May not terminate for irrational capacities; use BFS variant (Edmonds-Karp) for guaranteed termination
    - name: Edmonds-Karp Algorithm
      type: Maximum Flow
      time: O(V * E^2)
      space: O(V + E)
      description: Ford-Fulkerson using BFS to find shortest augmenting path (by edges)
      use_cases[2]: Network flow with guaranteed termination,Bipartite matching at scale
      notes: BFS ensures O(VE) augmentations; each augmentation found in O(E)
    - name: Dinic's Algorithm
      type: Maximum Flow
      time: O(V^2 * E) or O(VE log U) with scaling
      space: O(V + E)
      description: "Builds level graph via BFS, then finds blocking flow via DFS; repeats until no augmenting path"
      use_cases[3]: Large-scale network flow,Competitive programming,High-performance flow computation
      notes: O(V^2 E) worst case but O(E sqrt(V)) for unit networks; fastest practical max-flow algorithm
    - name: Hopcroft-Karp Algorithm
      type: Maximum Bipartite Matching
      time: O(E * sqrt(V))
      space: O(V + E)
      description: Finds maximum matching in bipartite graphs by repeatedly finding augmenting paths in batches
      use_cases[4]: Job assignment,Ad matching,Student-course allocation,Dating apps matching
      notes: Much faster than simple augmenting path for dense bipartite graphs
    - name: Graph Coloring (Greedy)
      type: Vertex Coloring
      time: O(V + E)
      space: O(V)
      description: Assigns colors to vertices so no adjacent vertices share a color; greedy uses at most Δ+1 colors
      use_cases[4]: Register allocation,Scheduling,Sudoku solving,Frequency assignment
      notes: Finding chromatic number is NP-hard; greedy gives approximation. Welsh-Powell orders by degree for better results
    - name: Bellman-Ford (Negative Cycles)
      type: Shortest Path with Negative Weights
      time: O(V * E)
      space: O(V)
      description: Detects negative-weight cycles reachable from source while computing shortest paths
      use_cases[3]: Arbitrage detection in currency exchange,Negative cycle detection,Shortest path with negative edges
      notes: "After V-1 relaxations, one more pass: if any distance improves, negative cycle exists"