Graph Algorithms
Essential graph algorithms: traversals (BFS, DFS), shortest path (Dijkstra, Bellman-Ford), minimum spanning tree (Prim, Kruskal), topological sort, and network flow.
Essential graph algorithms with category, time and space complexity, description, use cases, pseudocode and notes: BFS, DFS, Dijkstra, Bellman-Ford, Floyd-Warshall, Prim, Kruskal, topological sort, union-find and Ford-Fulkerson, plus graph representations.
Use it when
- You need a shortest-path, spanning-tree, ordering or connectivity algorithm and its complexity.
- You are choosing a graph representation.
Watch out for
- Dijkstra's algorithm requires non-negative edge weights; use Bellman-Ford when negative edges are possible.
- Complexity depends on the data structure used for the priority queue or the graph.
The data
Algorithms
10 rows
| 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
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 | Breadth-First Search (BFS) |
| algorithms | category | string | Traversal |
| algorithms | time_complexity | string | O(V + E) |
| algorithms | space_complexity | string | O(V) |
| algorithms | description | string | Visits nodes level by level using queue; finds … |
| algorithms | use_cases | array | [4 items] |
| algorithms | pseudocode | string | queue ← [start]; visited ← {start}; while queue… |
| algorithms | notes | string | Guarantees shortest path in unweighted graphs; … |
| algorithms | input_requirements | string | Weighted directed/undirected graph; all edge we… |
| algorithms | algorithms | array | [2 items] |
| algorithms | pseudocode_kahn | string | compute indegree of all nodes; queue ← all node… |
| algorithms | operations | object | {find,union} |
| algorithms | variants | array | [3 items] |
| graph_representations | * | object | {adjacency_matrix,adjacency_list,edge_list} |
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.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 →