A graph is a data structure used to model relationships between objects. The objects are called vertices (or nodes), and the connections between them are called edges.

Graphs appear across many real-world systems:

Graphs are also one of the most asked topics in coding interviews. Many problems that look unrelated, such as finding the shortest delivery route, scheduling courses with prerequisites, or detecting deadlocks, all reduce to the same underlying graph patterns.

In this chapter, we will cover:

A graph is formally defined as a pair G = (V, E), where:

Here is a small graph with 5 vertices and 6 edges:

In this graph, vertex A is connected to B and C. Vertex B is connected to A, C, and D. The line connecting two vertices is the edge.

Everything else in graph theory builds on this structure of vertices and edges.

Before we discuss graph types and representations, here are the terms used throughout the chapter and the rest of the course.

In the diagram above, the path A → B → D → E has length 3 (counting edges). The cycle A → B → C → A has length 3. The degree of vertex B is 3 because three edges touch it.

A graph without self-loops or parallel edges is called a simple graph. Simple graphs are the common assumption when none is stated.

Graphs come in a few important variations. The choice of variation affects which algorithms apply and what the time complexity looks like.

1. Directed vs Undirected

In an undirected graph, edges have no direction. If A is connected to B, then B is also connected to A. Friendships on Facebook are undirected, because if Alice is friends with Bob, Bob is friends with Alice.

In a directed graph (also called a digraph), each edge has a direction. An edge from A to B does not imply an edge from B to A. Twitter follows are directed, because Alice following Bob does not mean Bob follows Alice.

When you describe an algorithm or write code, the first question to ask is whether the graph is directed. The answer changes how edges are stored and how traversals behave.

2. Weighted vs Unweighted

In an unweighted graph, every edge is treated equally. We only care whether two vertices are connected.

In a weighted graph, each edge carries a number called its weight or cost. Road networks use distance as the weight. Flight networks use price or duration. Capacity networks use bandwidth.

Shortest-path algorithms like Dijkstra and minimum-spanning-tree algorithms like Kruskal and Prim only make sense on weighted graphs.

3. Cyclic vs Acyclic

A graph that contains at least one cycle is cyclic. A graph with no cycles is acyclic.

A directed acyclic graph, or DAG, is one of the most useful structures in computer science. Build systems, course prerequisites, task schedulers, and version-control histories are all DAGs. Topological sorting only works on DAGs.

This graph is a DAG. There is no way to start at any vertex, follow the arrows, and return to where you started.

4. Connected vs Disconnected

A graph is connected if there is a path between every pair of vertices. Otherwise it is disconnected, and it consists of two or more connected components.

This graph has two connected components: {A, B, C} and {D, E}.

For directed graphs, the analogous idea is strongly connected (every vertex can reach every other vertex) versus weakly connected (the underlying undirected graph is connected).

5. Sparse vs Dense

If V is the number of vertices, the maximum possible number of edges in a simple undirected graph is V * (V - 1) / 2. A graph close to this maximum is called dense. A graph with far fewer edges (often closer to V) is called sparse.

This distinction matters for choosing a representation. Social networks are sparse: each user has hundreds of friends, far below V. Road networks are sparse too, because each intersection has only a handful of roads.

A graph is an abstract idea. To work with it in code, we need a way to store the vertices and edges. The three common representations are the adjacency matrix, the adjacency list, and the edge list.

To make the comparisons concrete, we will use the same small graph throughout this section.

The graph has 5 vertices labeled 0 to 4 and 6 edges. Let us see how each representation stores this graph.

1. Adjacency Matrix

An adjacency matrix is a V x V 2D array where the entry at row i and column j is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

For our example graph:

For an undirected graph, the matrix is symmetric along the diagonal. For a directed graph, it is not.

For a weighted graph, instead of storing 0 or 1, we store the weight at matrix[i][j], and a sentinel value like Infinity or -1 for "no edge".

Here is how to build an adjacency matrix:

Pros

Cons

The adjacency matrix is a good fit for dense graphs and for problems that frequently ask "is there an edge between u and v?".

2. Adjacency List

An adjacency list stores a list of neighbors for each vertex. It is usually implemented as an array (or hash map) of lists.

For our example graph:

For a weighted graph, each entry stores the neighbor and the edge weight together, often as a pair or a small object.

Here is how to build an adjacency list:

Pros

Cons

The adjacency list is the most common representation for interview problems, because most graphs are sparse and most algorithms iterate over neighbors rather than test individual edges.

3. Edge List

An edge list stores the graph as a flat list of edges. Each entry is a pair (u, v) for unweighted graphs, or a triple (u, v, w) for weighted graphs.

For our example graph:

Edge lists use O(E) space. Iterating over all edges is trivial. Looking up neighbors of a specific vertex requires scanning the whole list, which is O(E).

This representation shows up in algorithms that process edges as the primary unit, such as Kruskal's algorithm for the minimum spanning tree, where edges are sorted by weight and processed in order.

Comparison

Use an adjacency matrix when the graph is dense or when constant-time edge checks are needed. Use an edge list when the algorithm processes edges as its main operation.

One row not shown above matters most for algorithm analysis: a full graph traversal (BFS/DFS) touches every vertex and every edge once, so the time complexity is O(V + E) with an adjacency list. With an adjacency matrix, it becomes O(V²) because finding neighbors requires scanning a full row for each vertex.

Once a graph is in memory, a small set of core algorithms solves a large variety of problems. Here is a preview of what the core algorithms do and when to use them.

Each of these algorithms relies on the representations covered in this chapter. Choosing the wrong representation can turn an O(V + E) algorithm into an O(V²) one, which slows it down significantly on large graphs.