Graph Algorithms Guide — BFS, DFS, Shortest Paths
Graphs model relationships of all kinds — social networks connecting people, maps connecting locations, web pages linking to each other, dependency trees connecting software packages, and neural networks connecting artificial neurons. Mastering graph traversal and analysis algorithms is essential for solving complex programming problems across virtually every domain of computer science. According to LeetCode, graph problems appear in approximately 20 percent of technical interviews at major technology companies, making graph algorithm proficiency a critical interview skill.
The study of graph algorithms dates back to Leonhard Euler’s 1736 solution to the Seven Bridges of Königsberg problem, which founded graph theory. Today, graph algorithms power Google Maps navigation, Facebook’s friend recommendations, Netflix’s content discovery, and Google’s PageRank search algorithm. Understanding graph representations and traversal algorithms is the foundation for building systems that operate on connected data.
Graph Coloring and Bipartite Graphs
Graph coloring assigns colors to vertices such that no adjacent vertices share the same color. The minimum number of colors needed is the graph’s chromatic number. Bipartite graphs are graphs that can be colored with exactly two colors, meaning their vertices can be partitioned into two sets where all edges cross between sets. Bipartite graphs model matching problems like job assignment, dating websites, and recommendation systems.
Detecting bipartiteness is accomplished with a simple modification to BFS. Starting from any vertex, assign it color 0. Assign all its neighbors color 1. Continue BFS, assigning each uncolored vertex the opposite color of its parent. If any edge connects two vertices of the same color, the graph is not bipartite. This algorithm runs in O(V+E) time and is widely used in scheduling problems where tasks must alternate between two resources.
Advanced Shortest Path Algorithms
Beyond Dijkstra and Bellman-Ford, specialized shortest path algorithms address specific constraints. The A-star search algorithm extends Dijkstra with a heuristic function that estimates the remaining distance to the target, dramatically reducing search space for navigation problems. A-star is the standard algorithm used in GPS navigation and video game pathfinding because it finds optimal paths while exploring far fewer vertices than Dijkstra.
The Floyd-Warshall algorithm computes shortest paths between all pairs of vertices in O(V cubed) time. Despite its cubic runtime, it is practical for graphs with up to a few hundred vertices and is much simpler to implement than running Dijkstra from every vertex. The algorithm uses dynamic programming, considering each vertex as a potential intermediate point on the shortest path. It also handles negative edge weights and can detect negative cycles.
Graph Representations
Choosing the right graph representation is the first decision in any graph algorithm implementation. The two primary representations are adjacency lists and adjacency matrices, each with distinct space and time characteristics.
Adjacency List
An adjacency list stores each vertex along with its list of neighboring vertices. This is the most common representation for sparse graphs, which describe most real-world networks where each vertex connects to only a small fraction of all possible vertices. Adjacency lists are space-efficient at O(V+E) and provide fast neighbor iteration, which is the dominant operation in most graph algorithms like BFS and DFS. The trade-off is O(V) time to check if a specific edge exists, since you must scan the neighbor list.
Adjacency Matrix
An adjacency matrix uses a 2D array where the entry at row i and column j indicates whether an edge exists from vertex i to vertex j. This representation is best for dense graphs where the number of edges approaches V squared, or when edge existence checks are the primary operation. Space complexity is O(V squared), which becomes prohibitive for graphs with tens of thousands of vertices. Use adjacency lists for sparse graphs and adjacency matrices for dense graphs or when O(1) edge existence checks are required.
Breadth-First Search
BFS explores a graph level by level, visiting all nodes at distance k from the start before moving to distance k+1. It uses a queue to manage the frontier of exploration, ensuring nodes are visited in order of their distance from the source. BFS finds the shortest path in unweighted graphs because the first time a node is discovered during traversal, it is reached via the minimum number of edges from the start.
Time complexity is O(V+E), space complexity is O(V). Applications of BFS include shortest path in unweighted graphs, level-order tree traversal, web crawling within a fixed number of clicks, social network degrees of separation analysis, and finding connected components in undirected graphs. BFS is also used in the Ford-Fulkerson algorithm for maximum flow, where it finds augmenting paths in the residual graph.
Depth-First Search
DFS explores as far as possible along each branch before backtracking, using a stack for iterative implementation or the call stack for recursive implementation. DFS uses less memory than BFS for deep graphs because it only needs to store a single path from the root, rather than an entire frontier level.
Applications of DFS include topological sorting for dependency resolution, cycle detection in directed and undirected graphs, pathfinding where any path is acceptable, finding connected components and strongly connected components, maze generation and solving, backtracking problems like N-Queens and Sudoku, and identifying articulation points and bridges in networks.
Recursive vs Iterative DFS
The choice between recursive and iterative implementations has significant practical consequences. Recursive DFS is elegant and concise but risks stack overflow for deep graphs since the call stack is typically limited to a few thousand frames. Iterative DFS using an explicit stack avoids this limitation and provides more control over traversal order. For BFS, the iterative implementation using a deque is the natural form and handles arbitrary graph sizes without recursion risks.
Topological Sort
Topological ordering places nodes so that for every directed edge from u to v, u appears before v in the ordering. This is only possible in Directed Acyclic Graphs. The standard algorithm uses DFS with post-order traversal — we add each node to the result after all its descendants have been processed, then reverse the result for the topological order. An alternative algorithm, Kahn’s algorithm, uses BFS with in-degree counting and is often easier to reason about. Applications include build systems where library A must be built before library B, course prerequisite planning, and task scheduling with dependency constraints.
Cycle Detection
Detecting cycles in directed graphs uses a three-color marking scheme: WHITE for unvisited nodes, GRAY for nodes in the current DFS path, and BLACK for fully explored nodes. A back edge to a GRAY node indicates a cycle in a directed graph. For undirected graphs, a cycle exists if we encounter a visited vertex that is not the parent of the current vertex in the DFS tree. Cycle detection is essential for deadlock detection in operating systems, dependency validation in build systems, and garbage collection algorithms.
Dijkstra’s Algorithm
Dijkstra’s algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to efficiently select the unvisited vertex with the smallest distance, relaxing edges from that vertex to update distances to its neighbors. Time complexity is O((V+E) log V) with a binary heap priority queue. For graphs with negative edge weights, use the Bellman-Ford algorithm instead. For all-pairs shortest paths on small graphs, use the Floyd-Warshall algorithm at O(V cubed) time.
Dijkstra’s algorithm is used in GPS navigation systems to find the fastest route, in network routing protocols like OSPF to compute shortest paths, and in social network analysis to find the shortest connection path between two people.
Minimum Spanning Trees
A minimum spanning tree connects all vertices in a weighted, undirected graph with the minimum possible total edge weight, without forming cycles. Kruskal’s algorithm sorts edges by weight and greedily adds edges that do not create cycles, using a union-find data structure for efficient cycle detection. Prim’s algorithm grows the tree from a starting vertex, always adding the minimum-weight edge connecting the tree to a vertex outside it, using a priority queue for efficient edge selection.
Strongly Connected Components
Strongly connected components partition a directed graph into subgraphs where every vertex is reachable from every other vertex within the same subgraph. Kosaraju’s algorithm performs two DFS passes — the first on the original graph records finish times, and the second on the transposed graph processes vertices in reverse finish order to identify SCCs. Tarjan’s algorithm achieves the same result in a single DFS pass using a stack and low-link values.
Algorithm Selection Guide
For shortest paths in unweighted graphs, use BFS at O(V+E). For weighted graphs without negative edges, use Dijkstra at O((V+E) log V). For graphs with negative weights, use Bellman-Ford at O(VE). For topological ordering or cycle detection, use DFS at O(V+E). For connected components, use BFS or DFS. For minimum spanning trees, use Kruskal’s or Prim’s algorithm at O(E log V).
Frequently Asked Questions
What is the difference between BFS and DFS? BFS explores level by level using a queue, finding shortest paths in unweighted graphs. DFS explores depth-first using a stack or recursion, using less memory for deep graphs.
When should I use an adjacency list versus an adjacency matrix? Use an adjacency list for sparse graphs since it uses O(V+E) space and provides fast neighbor iteration. Use an adjacency matrix for dense graphs or when O(1) edge checks are required.
What is a DAG and why is it important? A Directed Acyclic Graph has directed edges and no cycles. DAGs are essential for modeling dependencies, scheduling tasks, and representing causal relationships.
How does Dijkstra handle graphs with negative edge weights? Dijkstra assumes non-negative weights and fails on negative edges. For negative weights, use Bellman-Ford which can detect negative cycles.
What is the fastest shortest-path algorithm for a single pair? A* search with a heuristic can be faster than Dijkstra for single-pair queries. Bidirectional search also reduces search space.
Heaps and Priority Queues Guide — Hash Tables Guide — Trees and Graphs Guide