dsa2 min read
Advanced Graphs — Complete Guide (MST, SCC, Bridges, Floyd-Warshall, A*)
Master advanced graph algorithms: Kruskal and Prim MST, Tarjan SCC, articulation points, bridges, Floyd-Warshall all-pairs shortest path, and A* search.
Read →
Advanced-graphs
20 articles
dsa2 min read
Kruskal's Algorithm — Minimum Spanning Tree with Union-Find
Find the minimum spanning tree of a weighted graph using Kruskal's algorithm. Sort edges by weight, use Union-Find to avoid cycles. O(E log E) time.
Read →
dsa2 min read
Prim's Algorithm — MST via Min-Heap Greedy Expansion
Build the minimum spanning tree using Prim's algorithm: start from any vertex, greedily expand by always adding the minimum-weight crossing edge using a min-heap.
Read →
dsa2 min read
Tarjan's Algorithm — Strongly Connected Components
Find all strongly connected components in a directed graph using Tarjan's single-pass DFS algorithm with discovery time, low-link values, and a stack.
Read →
dsa2 min read
Bridges and Articulation Points — Graph Vulnerability Detection
Find all bridge edges and articulation point vertices in an undirected graph using a single DFS pass with discovery time and low-link tracking.
Read →
dsa2 min read
Floyd-Warshall — All-Pairs Shortest Path
Compute shortest paths between all pairs of vertices using Floyd-Warshall's O(V³) DP. Handles negative weights and detects negative cycles.
Read →
dsa2 min read
Bellman-Ford — SSSP with Negative Edges and Cycle Detection
Compute single-source shortest paths in graphs with negative weight edges using Bellman-Ford. V-1 relaxation passes detect negative cycles on the Vth pass.
Read →
dsa2 min read
A* Search — Heuristic Shortest Path for Grid Problems
A* combines Dijkstra's correctness with a heuristic to guide search toward the goal. Uses f(n)=g(n)+h(n) priority. Optimal when heuristic is admissible.
Read →
dsa2 min read
Topological Sort — Advanced Applications (DFS, Kahn, Cycle Detection)
Advanced topological sort: DFS-based with 3-color marking for cycle detection, Kahn's BFS approach, and applications in course scheduling, build systems, and task ordering.
Read →
dsa2 min read
Dijkstra Advanced — Modified Dijkstra Patterns (K Stops, States, Constraints)
Advanced Dijkstra patterns: state-space Dijkstra for problems with extra constraints like K stops, fuel limit, or restricted nodes. The key is augmenting the state beyond just the node.
Read →
dsa1 min read
Graph Coloring and Bipartite Check
Check if a graph is bipartite using BFS 2-coloring. A graph is bipartite if and only if it contains no odd-length cycles — equivalent to being 2-colorable.
Read →
dsa1 min read
Minimum Cost to Connect All Points — Prim's on Complete Graph
Connect all n points with minimum total Manhattan distance cost. Models the problem as a complete graph MST and applies optimised Prim's without building all O(n²) edges explicitly.
Read →
dsa1 min read
Path with Minimum Maximum Weight — Binary Search + BFS
Find the path from source to destination minimising the maximum edge weight. Binary search on the answer + BFS/DFS connectivity check. O(E log W) total.
Read →
dsa2 min read
Number of Ways to Arrive at Destination — Dijkstra + Count
Count the number of shortest paths from source to destination using modified Dijkstra that tracks both minimum distance and path count simultaneously.
Read →
dsa2 min read
Find Critical Connections in Network — Bridge Finding
LeetCode 1192: Find all critical edges (bridges) in a network. A connection is critical if removing it disconnects the network. Uses Tarjan's bridge algorithm.
Read →
dsa2 min read
Reconstruct Itinerary — Hierholzer's Eulerian Path
Find the itinerary using all flight tickets exactly once (Eulerian path). Uses Hierholzer's algorithm: DFS with post-order insertion into result — the only graph algorithm that uses post-order for path construction.
Read →
dsa2 min read
Swim in Rising Water — Dijkstra / Binary Search + BFS
Find the minimum time to swim from (0,0) to (n-1,n-1) where you can only move to a cell when time >= cell value. Two approaches: Dijkstra O(n² log n) and binary search + BFS O(n² log n).
Read →
dsa2 min read
Longest Path in DAG — Graph DP with Memoisation
Find the longest path in a directed acyclic graph using DFS with memoisation. Since cycles are absent, DFS never revisits nodes, making top-down DP straightforward.
Read →
dsa2 min read
Network Flow Concepts — Max Flow and Min Cut Overview
Introduction to network flow: max flow problem, Ford-Fulkerson algorithm with BFS (Edmonds-Karp), max-flow min-cut theorem, and applications in matching and connectivity.
Read →
dsa3 min read
Advanced Graphs — Master Recap and Algorithm Selection Guide
Complete recap of all 20 advanced graph problems with algorithm selection guide, complexity comparison, and pattern recognition cues.
Read →