api: "YAML JSON TOON Database" version: 1.0.0 format: toon dataset: id: 415 slug: graph-algorithms title: "Graph Algorithms" description: "Essential graph algorithms: traversals (BFS, DFS), shortest path (Dijkstra, Bellman-Ford), minimum spanning tree (Prim, Kruskal), topological sort, and network flow." category: "Data Structures" category_slug: data-structures tags: "graphs,algorithms,bfs,dfs,dijkstra,mst,topological-sort,network-flow" view_count: 2 created_at: 1781275786 updated_at: 1781275786 data: algorithms - name: "Breadth-First Search (BFS)" category: Traversal time_complexity: "O(V + E)" space_complexity: O(V) description: "Visits nodes level by level using queue; finds shortest path in unweighted graphs." use_cases: [4]: "Shortest path (unweighted)","Web crawling","Social network friend suggestions","Garbage collection (mark-sweep)" pseudocode: "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)" notes: "Guarantees shortest path in unweighted graphs; uses more memory than DFS" - name: "Depth-First Search (DFS)" category: Traversal time_complexity: "O(V + E)" space_complexity: "O(V) (recursion stack or explicit stack)" description: "Explores as far as possible along each branch before backtracking; uses stack (implicit or explicit)." use_cases: [5]: "Cycle detection","Topological sorting","Maze solving","Connected components","Path existence" pseudocode: "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)" notes: "Lower memory footprint than BFS; can get stuck in deep infinite branches (use iterative deepening or IDDFS)" - name: "Dijkstra's Algorithm" category: "Shortest Path" time_complexity: "O((V + E) log V) with min-heap, O(V²) with array" space_complexity: O(V) description: "Single-source shortest path for graphs with non-negative edge weights." input_requirements: "Weighted directed/undirected graph; all edge weights ≥ 0" pseudocode: "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)" notes: "Fails with negative weights (use Bellman-Ford); can be optimized with Fibonacci heap (O(V log V + E))" - name: "Bellman-Ford Algorithm" category: "Shortest Path" time_complexity: "O(V × E)" space_complexity: O(V) description: "Single-source shortest path handling negative weights; detects negative cycles." input_requirements: "Weighted directed graph; negative weights allowed but no negative cycles reachable from source" pseudocode: "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" notes: "Slower than Dijkstra but handles negatives; used in currency arbitrage detection; SPFA is optimization in practice" - name: "Floyd-Warshall Algorithm" category: "All-Pairs Shortest Path" time_complexity: O(V³) space_complexity: O(V²) description: "All-pairs shortest paths for dense graphs; works with negative weights (no negative cycles)." input_requirements: "Directed/undirected weighted graph; no negative cycles" pseudocode: "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])" notes: "Simple triple loop; good for dense graphs (V² space); transitive closure variant" - name: "Prim's Algorithm" category: "Minimum Spanning Tree" time_complexity: "O(E log V) with min-heap, O(V²) with array" space_complexity: O(V) description: "Grows MST from a starting node; always adds cheapest edge connecting tree to new vertex." pseudocode: "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" notes: "Like Dijkstra but tracks vertices instead of distances; better for dense graphs" - name: "Kruskal's Algorithm" category: "Minimum Spanning Tree" time_complexity: "O(E log E) (sorting dominates)" space_complexity: O(V) description: "Builds MST by adding edges in increasing weight order, skipping those that create cycles." pseudocode: "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)" notes: "Better for sparse graphs; requires Union-Find with path compression (α(n) ≈ constant)" - name: "Topological Sort" category: Ordering time_complexity: "O(V + E)" space_complexity: O(V) description: "Linear ordering of DAG vertices such that for every edge u→v, u comes before v." algorithms: [2]: "Kahn's (BFS-based: indegree zero queue)","DFS-based (postorder reverse)" pseudocode_kahn: "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" use_cases: [4]: "Task scheduling (build systems, job queues)","Course prerequisites","Dependency resolution",Makefiles notes: "Graph must be DAG; detects cycles; Kahn's also detects cycles" - name: "Union-Find (Disjoint Set)" category: Connectivity time_complexity: "O(α(n)) per operation (amortized nearly O(1))" space_complexity: O(n) description: "Track partition of elements into disjoint sets; supports union and find operations." operations: find: "Returns representative (root) of set containing element; uses path compression" union: "Merges two sets; uses union by rank/size" use_cases: [4]: "Kruskal's MST","Connected components","Maze generation (Kruskal's)",Percolation notes: "Path compression + union by rank gives amortized α(n) ≈ constant (inverse Ackermann); one of most optimized DS" - name: "Ford-Fulkerson (Max Flow)" category: "Network Flow" time_complexity: "O(E × max_flow) — Edmonds-Karp is O(V × E²)" space_complexity: "O(V + E)" description: "Computes maximum flow from source to sink in flow network; Ford-Fulkerson method with augmenting paths." variants: [3]: "Edmonds-Karp (BFS augmenting paths, O(VE²))","Dinic's (O(V²E), blocking flows)","Push-relabel (O(V³))" use_cases: [4]: "Bipartite matching","Assignment problems","Network capacity planning","Image segmentation (min-cut)" notes: "Integral capacities → integral flow; Dinic's is faster in practice for dense graphs" graph_representations: adjacency_matrix: space: O(V²) pros: [3]: "O(1) edge lookup",Simple,"Good for dense graphs" cons: [2]: "O(V²) space even if sparse","Iterating neighbors O(V)" adjacency_list: space: "O(V + E)" pros: [2]: "Space efficient for sparse graphs","Fast neighbor iteration" cons: [2]: "O(degree(v)) edge existence check","Slower for dense graphs" edge_list: space: O(E) pros: [2]: Simple,"Good for algorithms that process all edges (Kruskal)" cons: [2]: "Slow edge lookup O(E)","No fast neighbor access"