Data Structures
Graphs: Representation Basics
Difficulty: Beginner
A social network is a graph, a road map is a graph, an import graph in your codebase is a graph, and so is the dependency tree of a package manager. The reason graphs feel everywhere is that they are the most general relationship...
Graphs: Representation Basics
A social network is a graph, a road map is a graph, an import graph in your codebase is a graph, and so is the dependency tree of a package manager. The reason graphs feel everywhere is that they are the most general relationship structure: just vertices and edges, with no required root, no acyclic constraint, and no fixed branching factor. Graphs: Representation Basics is where you stop drawing them on whiteboards and start storing them in code.
This lesson defines the core vocabulary (vertex, edge, degree, path, cycle, directed and undirected, connected and disconnected) and walks through the three canonical representations: an adjacency list backed by a hash map of vertex to neighbors, an adjacency matrix for dense graphs and O(1) edge-existence queries, and an edge list for algorithms that just iterate over edges. You will analyze the space and time trade-offs of each so you can pick the right one before writing any traversal logic.
In Hash Map (Dictionary) Basics, you saw that a hash map maps keys to values in expected O(1); an adjacency list is exactly that, mapping each vertex to its list of neighbors. Queue & Deque gave you the FIFO machinery that BFS will run on top of these representations once traversal lessons begin.
With a graph stored in memory, the algorithms track is where it comes alive: BFS, DFS, shortest paths, connected components, and the rest of the graph algorithm canon.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Define graph terminology (vertex, edge, degree, path, cycle) and distinguish directed from undirected graphs.
Build an adjacency list representation of a graph using a hash map in JavaScript and Python.
Build an adjacency matrix representation and explain when it is preferred over an adjacency list.
Describe the edge list representation and its use cases.
Analyze space and time complexity of each representation and choose the appropriate one for a given scenario.
Identify real-world systems that are naturally modeled as graphs and explain why.
Why This Matters
01
Graphs model an enormous range of real-world systems -- social networks (friends), maps (cities and roads), the internet (web pages and links), package managers (dependencies), and recommendation engines. Understanding graph representation is the first step to solving any graph problem.
02
Graph problems are among the most commonly tested in technical interviews at top companies, including BFS/DFS traversals, shortest paths, cycle detection, and connected components -- all of which depend on choosing the right representation.
03
Knowing the space and time trade-offs between adjacency lists and adjacency matrices lets you make informed engineering decisions: use lists for sparse real-world graphs and matrices for dense or small graphs with frequent edge-existence queries.
Key Terms
8 terms you'll encounter in this lesson
Vertex (Node)
A fundamental unit in a graph representing an entity. Vertices are connected by edges. The set of all vertices is denoted V.
Edge
A connection between two vertices. In an undirected graph, an edge {u, v} goes both ways. In a directed graph, edge (u, v) goes from u to v only. The set of all edges is denoted E.
Adjacency List
A graph representation where each vertex stores a list of its neighbors. Uses O(V + E) space and is preferred for sparse graphs.
Adjacency Matrix
A V x V matrix where entry [i][j] is 1 (or the edge weight) if an edge exists from vertex i to vertex j, and 0 otherwise. Uses O(V^2) space.
Degree
The number of edges connected to a vertex. In directed graphs, in-degree counts incoming edges and out-degree counts outgoing edges.
Sparse Graph
A graph where |E| is much less than |V|^2. Most real-world graphs (social networks, road maps) are sparse. Adjacency lists are preferred.
Dense Graph
A graph where |E| is close to |V|^2 (most possible edges exist). Adjacency matrices are efficient for dense graphs.
Connected Component
A maximal set of vertices such that every pair is connected by a path. A graph with one connected component is called a connected graph.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Graphs must have a root node like trees"
Trees are a special case of graphs (connected, acyclic). General graphs have no required root -- any vertex can be a starting point. You choose a start vertex when running BFS/DFS, but it is not structurally special.
"An adjacency matrix always wastes space"
For dense graphs (close to V^2 edges), an adjacency matrix uses roughly the same space as an adjacency list but provides O(1) edge-existence checks. The matrix wastes space only when the graph is sparse.
"Directed and undirected graphs use different data structures"
Both use the same representations (adjacency list, adjacency matrix, edge list). The difference is implementation: for an undirected edge {u, v}, you add the edge in both directions (u->v and v->u); for directed, you add only the specified direction.
"The number of edges is always V^2"
V^2 is the maximum for a directed graph (V*(V-1) without self-loops). For undirected graphs the max is V*(V-1)/2. Real-world graphs are usually far below these limits -- a social network with a million users does not have a trillion friendships.