Whenever a problem is about things and the connections between them, consider a graph. Cities connected by roads, people connected by friendships, and web pages connected by links are all graph-shaped problems.
Vertices and edges
A graph contains vertices (also called nodes) and edges that connect pairs of vertices. Edges can be directed, like a one-way street, or undirected, like a two-way friendship. They may also carry weights such as distance, cost, or travel time.
Two common ways to store a graph
An adjacency list records the neighbors of each vertex. It uses O(V + E) space and works especially well for sparse graphs, where there are far fewer edges than possible connections.
An adjacency matrix stores a table with one row and column per vertex. It uses O(V²) space, but checking whether a particular edge exists is O(1). It can be a good fit for dense graphs or when constant-time edge checks matter.
Questions graphs can answer
- Can one vertex reach another?
- What is the shortest path when every edge has equal cost?
- How many connected groups are there?
Graph algorithms usually start by choosing a representation. Match it to the expected operations and graph density, then account for whether connections are directed and weighted.