api: YAML JSON TOON Database
version: 1.0.0
format: yaml
dataset:
  id: 2727
  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:
    - You need the right algorithm and complexity for a flow, matching or connectivity problem.
    - You are comparing max-flow algorithms.
  caveats:
    - 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:
    - graph-algorithms
    - graph-traversal-algorithms
    - complexity-classes
    - greedy-algorithms
  entry_count: 8
  fields:
    - section: algorithms
      field: name
      type: string
      example: Tarjan's SCC Algorithm
    - section: algorithms
      field: type
      type: string
      example: Strongly Connected Components
    - section: algorithms
      field: time
      type: string
      example: O(V + E)
    - section: algorithms
      field: space
      type: string
      example: O(V)
    - section: algorithms
      field: description
      type: string
      example: Finds all strongly connected components in a di…
    - section: algorithms
      field: use_cases
      type: array
      example: "[4 items]"
    - section: algorithms
      field: notes
      type: string
      example: Single DFS pass; low-link value = lowest discov…
  category: Data Structures
  category_slug: data-structures
  tags: graphs,algorithms,max-flow,matching,strongly-connected-components,graph-coloring,ford-fulkerson
  view_count: 60
  created_at: 1778695229
  updated_at: 1778695229
data:
  algorithms:
    - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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:
        - 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"