Graph Algorithms
Essential graph algorithms: traversals (BFS, DFS), shortest path (Dijkstra, Bellman-Ford), minimum spanning tree (Prim, Kruskal), topological sort, and network flow.
The data
Algorithms
| Name | Category | Time complexity | Space complexity | Description | Use cases | Pseudocode | Notes | Input requirements | Algorithms | Pseudocode kahn | Operations | Variants |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Breadth-First Search (BFS) | Traversal | O(V + E) | O(V) | Visits nodes level by level using queue; finds shortest path in unweighted graphs. |
| 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) | Guarantees shortest path in unweighted graphs; uses more memory than DFS | null | null | null | null | null |
| Depth-First Search (DFS) | Traversal | O(V + E) | O(V) (recursion stack or explicit stack) | Explores as far as possible along each branch before backtracking; uses stack (implicit or explicit). |
| 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) | Lower memory footprint than BFS; can get stuck in deep infinite branches (use iterative deepening or IDDFS) | null | null | null | null | null |
| Dijkstra's Algorithm | Shortest Path | O((V + E) log V) with min-heap, O(V²) with array | O(V) | Single-source shortest path for graphs with non-negative edge weights. | null | 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) | Fails with negative weights (use Bellman-Ford); can be optimized with Fibonacci heap (O(V log V + E)) | Weighted directed/undirected graph; all edge weights ≥ 0 | null | null | null | null |
| Bellman-Ford Algorithm | Shortest Path | O(V × E) | O(V) | Single-source shortest path handling negative weights; detects negative cycles. | null | 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 | Slower than Dijkstra but handles negatives; used in currency arbitrage detection; SPFA is optimization in practice | Weighted directed graph; negative weights allowed but no negative cycles reachable from source | null | null | null | null |
| Floyd-Warshall Algorithm | All-Pairs Shortest Path | O(V³) | O(V²) | All-pairs shortest paths for dense graphs; works with negative weights (no negative cycles). | null | 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]) | Simple triple loop; good for dense graphs (V² space); transitive closure variant | Directed/undirected weighted graph; no negative cycles | null | null | null | null |
| Prim's Algorithm | Minimum Spanning Tree | O(E log V) with min-heap, O(V²) with array | O(V) | Grows MST from a starting node; always adds cheapest edge connecting tree to new vertex. | null | 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 | Like Dijkstra but tracks vertices instead of distances; better for dense graphs | null | null | null | null | null |
| Kruskal's Algorithm | Minimum Spanning Tree | O(E log E) (sorting dominates) | O(V) | Builds MST by adding edges in increasing weight order, skipping those that create cycles. | null | 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) | Better for sparse graphs; requires Union-Find with path compression (α(n) ≈ constant) | null | null | null | null | null |
| Topological Sort | Ordering | O(V + E) | O(V) | Linear ordering of DAG vertices such that for every edge u→v, u comes before v. |
| null | Graph must be DAG; detects cycles; Kahn's also detects cycles | null |
| 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 | null | null |
| Union-Find (Disjoint Set) | Connectivity | O(α(n)) per operation (amortized nearly O(1)) | O(n) | Track partition of elements into disjoint sets; supports union and find operations. |
| null | Path compression + union by rank gives amortized α(n) ≈ constant (inverse Ackermann); one of most optimized DS | null | null | null |
| null |
| Ford-Fulkerson (Max Flow) | Network Flow | O(E × max_flow) — Edmonds-Karp is O(V × E²) | O(V + E) | Computes maximum flow from source to sink in flow network; Ford-Fulkerson method with augmenting paths. |
| null | Integral capacities → integral flow; Dinic's is faster in practice for dense graphs | null | null | null | null |
|
Graph representations
- Adjacency matrix
- Space
- O(V²)
- Pros
- O(1) edge lookup
- Simple
- Good for dense graphs
- Cons
- O(V²) space even if sparse
- Iterating neighbors O(V)
- Adjacency list
- Space
- O(V + E)
- Pros
- Space efficient for sparse graphs
- Fast neighbor iteration
- Cons
- O(degree(v)) edge existence check
- Slower for dense graphs
- Edge list
- Space
- O(E)
- Pros
- Simple
- Good for algorithms that process all edges (Kruskal)
- Cons
- Slow edge lookup O(E)
- No fast neighbor access
Fetch the same bytes
The static files are identical to what the API returns, but with no rate limit and no server round trip. Use the API when you want a query and a content type; use the files when you want to cache one document.
curl "https://yjtoon.com/api/dataset/graph-algorithms?format=toon"
const res = await fetch( "https://yjtoon.com/static-data/dataset/graph-algorithms.toon" ); const toon = await res.text();
Rate limit: 120 requests per minute per IP, no key and no signup. API reference →