{
    "api": "YAML JSON TOON Database",
    "version": "1.0.0",
    "format": "json",
    "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\u2026"
            },
            {
                "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\u2026"
            }
        ],
        "category": "Data Structures",
        "category_slug": "data-structures",
        "tags": "graphs,algorithms,max-flow,matching,strongly-connected-components,graph-coloring,ford-fulkerson",
        "view_count": 59,
        "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 \u0394+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"
            }
        ]
    }
}