Graphs Summary Resource

Graphs Summary Resource - aloalgo

A quick reference for graph algorithms and problems to practice. Graphs are one of the most versatile data structures in computer science. They model relationships between objects, where vertices represent entities and edges represent connections between them. Social networks, road maps, dependency chains, and even web pages linked by hyperlinks are all naturally represented as graphs.In coding interviews, graph problems test your ability to choose the right algorithm for the right situation. The most common patterns involve traversal (DFS and BFS), shortest path finding, connected component identification, and dependency ordering. Once you internalize the algorithm selection table below, you will be able to quickly map a problem description to the correct approach.

Choosing the right algorithm is the most important step in solving a graph problem. The table below maps common problem types to the algorithm that solves them most efficiently.

Problem	Algorithm	Why
Shortest path (unweighted)	BFS	Guarantees shortest
Shortest path (weighted)	Dijkstra	Handles edge weights
Any path / reachability	DFS	Simpler, less memory
Connected components	DFS or BFS	Either works
Dependency ordering	Topological Sort	DAG ordering
Cycle detection	DFS with colors	Tracks back edges
Flood fill / islands	DFS	Natural recursion

Algorithm	Time	Space
DFS / BFS	O(V + E)	O(V)
Dijkstra	O((V + E) log V)	O(V)
Topological Sort	O(V + E)	O(V)

V = vertices, E = edges. Note that for dense graphs (where E approaches V²), the time complexity of DFS and BFS effectively becomes O(V²). For sparse graphs (where E is close to V), traversal is nearly linear. Dijkstra's extra log factor comes from the priority queue operations used to always process the nearest unvisited vertex.

Graphs can be represented as an adjacency list or an adjacency matrix. An adjacency list maps each vertex to its list of neighbors and is memory-efficient for sparse graphs, using O(V + E) space. An adjacency matrix uses a 2D grid where matrix[i][j] indicates an edge from i to j, consuming O(V²) space regardless of edge count, but allowing O(1) edge lookups.In most interview problems, adjacency lists are preferred because they are more space-efficient and naturally support iteration over a node's neighbors. Adjacency matrices are useful when you need constant-time edge existence checks or when working with dense graphs.

Graph Fundamentals & Terminology - Vertices, edges, graph types
Graph Representation - Adjacency list and matrix
Graph Traversal (DFS, BFS) - Exploring graphs
Dijkstra - Weighted shortest path
Topological Sort - Dependency ordering

Convert Adjacency Matrix to Adjacency List

Count Bodies of Water

Word Ladder

Was this helpful?

Study plan All problems

Resources Cheat Sheet DSA Glossary

Graphs Summary

Algorithm Selection

Complexity

Representation Comparison

Chapters

Practice Problems

Easy

Medium

Hard

Company

Practice

Learn