Tag
#graphs
8 articles tagged graphs.
Breadth-First Search: Finding the Shortest Path One Ripple at a Time
The breadth-first search (BFS) algorithm: explore a graph level by level with a queue, find the shortest path in an unweighted graph, grid and multi-source BFS, time complexity, and interview prep.
Depth-First Search: Go Deep, Backtrack, and the Three-Colour Cycle Trick
The depth-first search (DFS) algorithm explained: recursion vs an explicit stack, three-colour cycle detection, connected components, flood fill, O(V+E) time complexity, and interview questions.
The Graph: How Software Models Maps, Friends, and the Web
A diagram-first guide to the graph data structure: vertices and edges, adjacency list vs matrix, degree, connected components, time complexity, and a complete implementation for interviews.
Topological Sort: Ordering a DAG So Every Prerequisite Comes First
The topological sort algorithm on a DAG: Kahn's algorithm with in-degrees and DFS post-order, how it detects a cycle, O(V+E) time complexity, and interview questions.
Union-Find (Disjoint Set Union): Merging Groups in Almost No Time
A diagram-first guide to the union-find (disjoint set union) data structure: find and union, path compression, union by rank, near-constant time complexity, and interview code.
LinkedIn HLD: Degrees of Separation on a Billion-Edge Graph
A LinkedIn system design: the connection graph, degrees of separation via BFS, People You May Know ranked by mutual connections, why deep traversal is precomputed, and scaling the graph.
Google Maps HLD: Fastest Route on a Planet-Sized Graph
A Google Maps system design: modelling roads as a weighted graph, A* routing with an admissible heuristic, precomputation for continent scale, live-traffic edge weights, and map tiles.
Dijkstra's Algorithm: How Your Map Finds the Fastest Route
A friendly, diagram-first walk through Dijkstra's shortest path algorithm: the ripple intuition, the invariant behind it, a step-by-step trace on a real graph, and a complete implementation.