Advanced Graph Algorithms
Advanced graph algorithms: strongly connected components (Tarjan's, Kosaraju's), max flow (Ford-Fulkerson, Edmonds-Karp, Dinic), matching, and graph coloring.
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 it when
- You need the right algorithm and complexity for a flow, matching or connectivity problem.
- You are comparing max-flow algorithms.
Watch out for
- 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.
The data
Algorithms
8 rows
| Name | Type | Time | Space | Description | Use cases | Notes |
|---|---|---|---|---|---|---|
| Tarjan's SCC Algorithm | Strongly Connected Components | O(V + E) | O(V) | Finds all strongly connected components in a directed graph using DFS with low-link values and a stack |
| Single DFS pass; low-link value = lowest discovery time reachable from subtree |
| Kosaraju's SCC Algorithm | Strongly Connected Components | O(V + E) | O(V) | Two-pass algorithm: first DFS on original graph for finish times, second DFS on reversed graph in decreasing finish time order |
| Simpler to understand than Tarjan's but requires graph reversal and two passes |
| Ford-Fulkerson Algorithm | Maximum Flow | O(E * max_flow) | O(V + E) | Repeatedly finds augmenting paths in residual graph and pushes flow until no path exists |
| May not terminate for irrational capacities; use BFS variant (Edmonds-Karp) for guaranteed termination |
| Edmonds-Karp Algorithm | Maximum Flow | O(V * E^2) | O(V + E) | Ford-Fulkerson using BFS to find shortest augmenting path (by edges) |
| BFS ensures O(VE) augmentations; each augmentation found in O(E) |
| Dinic's Algorithm | Maximum Flow | O(V^2 * E) or O(VE log U) with scaling | O(V + E) | Builds level graph via BFS, then finds blocking flow via DFS; repeats until no augmenting path |
| O(V^2 E) worst case but O(E sqrt(V)) for unit networks; fastest practical max-flow algorithm |
| Hopcroft-Karp Algorithm | Maximum Bipartite Matching | O(E * sqrt(V)) | O(V + E) | Finds maximum matching in bipartite graphs by repeatedly finding augmenting paths in batches |
| Much faster than simple augmenting path for dense bipartite graphs |
| Graph Coloring (Greedy) | Vertex Coloring | O(V + E) | O(V) | Assigns colors to vertices so no adjacent vertices share a color; greedy uses at most Δ+1 colors |
| Finding chromatic number is NP-hard; greedy gives approximation. Welsh-Powell orders by degree for better results |
| Bellman-Ford (Negative Cycles) | Shortest Path with Negative Weights | O(V * E) | O(V) | Detects negative-weight cycles reachable from source while computing shortest paths |
| After V-1 relaxations, one more pass: if any distance improves, negative cycle exists |
Fields
The shape of this dataset, read from the data itself: every column, its type and a real value. Agents can use this to plan a query without fetching the whole document.
| 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… |
Fetch the same bytes
The static files contain the same reference rows as the API, with no API rate limit. Live metadata, such as view counts, may differ. Use the API for content negotiation; use the static files for a cacheable snapshot.
curl "https://yjtoon.yunusemrevurgun.com/api/dataset/advanced-graph-algorithms?format=toon"
const res = await fetch( "https://yjtoon.yunusemrevurgun.com/static-data/dataset/advanced-graph-algorithms.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →