Practical examples of graph representation: matrix vs list examples

Before definitions, let’s jump straight into the best examples of graph representation: matrix vs list examples using the same tiny graph.

Imagine a directed graph with four vertices: A, B, C, D.

Edges:

• A → B
• A → C
• B → D
• C → D

Label the vertices as indices: A = 0, B = 1, C = 2, D = 3.

Adjacency matrix example

For this graph, the adjacency matrix M is a 4×4 matrix where M[i][j] = 1 if there is an edge from i to j, otherwise 0.

In code (Python-style):

M = [
    [0, 1, 1, 0],  # A
    [0, 0, 0, 1],  # B
    [0, 0, 0, 1],  # C
    [0, 0, 0, 0]   # D
]

Checking if A → C exists is just M[0][2] == 1, a constant-time lookup.

Adjacency list example

Now the same graph as an adjacency list:

adj = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

Here, each vertex stores only its outgoing neighbors. Instead of a full 4×4 grid, you only store four lists of neighbors. For a small graph, it doesn’t matter much. For a million-node sparse graph, it matters a lot.

Already you have your first pair of examples of graph representation: matrix vs list examples: same structure, two very different memory and performance profiles.

Dense vs sparse: examples of when a matrix shines

Let’s talk density. A graph with n vertices can have up to n² directed edges (or n(n−1)/2 undirected). When you have a large fraction of those possible edges, you’re in dense graph territory.

Example of a dense graph: fully connected classroom

Say you have a small class of 30 students, and you model who has messaged whom in a group chat at least once. Over a semester, almost everyone messages everyone. That’s close to a complete graph.

• Vertices: 30 students
• Edges: message-sent relationships
• Edge density: very high

Adjacency matrix representation:

• Size: 30×30 = 900 entries
• Memory: proportional to 900, regardless of exact edges
• Edge lookup ("Did Alice message Bob?"): O(1)

Adjacency list representation:

• Each student has neighbors ≈ 29
• Total stored neighbors ≈ 30 × 29 ≈ 870

In this case, an adjacency matrix is not wasteful. You get:

• Very simple implementation
• Very fast, direct edge tests

This is a clean example of graph representation: matrix vs list examples where the matrix is at least as good as the list, and often easier to reason about.

Example: small weighted graph in algorithms courses

Textbooks and courses (see, for instance, MIT OpenCourseWare’s graph lectures at mit.edu) often use adjacency matrices for small, weighted dense graphs:

• Vertices: {1, 2, 3, 4, 5}
• Edge weights: costs between every pair of cities

Adjacency matrix with weights (∞ means no edge):

    1   2   3   4   5
1 [ 0   3   8   ∞  -4]
2 [∞   0   ∞   1   7]
3 [∞   4   0   ∞   ∞]
4 [2   ∞  -5   0   ∞]
5 [∞   ∞   ∞   6   0]

Algorithms like Floyd–Warshall (all-pairs shortest paths) are usually taught with matrices, because the triple-nested loops map naturally onto the 2D structure. This is another classic example of graph representation: matrix vs list examples where the matrix fits the algorithm’s brain.

Real examples where adjacency lists win by a mile

Most real-world graphs are sparse: think social networks, road networks, citation graphs. The number of edges is closer to O(n) than O(n²).

Example: US road network

Consider a simplified road graph:

• Vertices: intersections
• Edges: road segments

Each intersection connects to only a few roads. According to transportation studies, average road intersection degree is usually under 10, even in dense cities.

If the U.S. road network has on the order of tens of millions of intersections, a matrix would require on the order of (10^7)² = 10^14 entries. That’s astronomically large.

Adjacency list instead:

roads = {
    'I-80@Exit42': ['I-80@Exit41', 'I-80@Exit43', 'US-45@Junction'],
    'US-45@Junction': ['I-80@Exit42', 'MainSt@3rdAve'],
#    # ... millions more
}

Memory is proportional to actual edges, not all possible pairs. This is one of the best real examples of graph representation: matrix vs list examples you’ll encounter in practice.

For background on road network modeling, the U.S. Department of Transportation provides data and methodology at transportation.gov, which is typically processed with adjacency-list-like structures under the hood.

Example: social network friend graph

Take a simplified social network:

• Vertices: users
• Edges: mutual friendships (undirected)

Even on large platforms, the average number of friends per user is in the hundreds, not millions. For n = 1,000,000 users:

• Matrix: 10¹² entries (trillion) → not realistic
• List: about n × average_degree / 2 edges → manageable

Adjacency list sketch:

friends = {
    'user_1': ['user_5', 'user_20', 'user_999'],
    'user_2': ['user_10'],
#    # ...
}

Graph traversal algorithms like BFS and DFS are naturally written on top of adjacency lists. That’s why most graph libraries (e.g., NetworkX in Python) default to list-like structures.

Example: citation networks and knowledge graphs

Academic citation networks (papers citing papers) and biomedical knowledge graphs (genes, diseases, drugs) are textbook sparse graphs.

For instance, the National Institutes of Health (NIH) and the National Library of Medicine maintain PubMed and related datasets (nih.gov). A single paper cites maybe 20–50 others, not millions. Representing this as an adjacency matrix would be absurdly wasteful; adjacency lists are the obvious choice.

Example adjacency list for a tiny citation graph:

citations = {
    'paper_A': ['paper_B', 'paper_C'],
    'paper_B': ['paper_C'],
    'paper_C': [],
}

This is a perfect example of graph representation: matrix vs list examples where the list is not just more efficient; it’s practically the only sane option.

Mixed examples: when you might use both matrix and list

Real systems sometimes use both representations at different layers.

Example: recommendation system pipeline

Imagine a movie recommendation system:

• Global graph: users and movies as nodes, edges for ratings or interactions
• Local subgraph: a small batch of candidates for a given user

Global scale (millions of users, hundreds of thousands of movies):

• Stored as adjacency lists or compressed sparse structures
• Example: user → [movies watched], movie → [users who watched]

But during a single recommendation query, you might extract a small induced subgraph (say, 500 movies and 5,000 users) and represent that subgraph as a dense matrix to run fast linear algebra operations on a GPU.

So you get:

• Long-term storage: adjacency list
• Short-term compute: adjacency matrix (or a sparse matrix format like CSR/CSC)

This hybrid design is a modern, 2024-style example of graph representation: matrix vs list examples in real machine learning systems.

Example: graph neural networks (GNNs)

In graph neural networks, the data pipeline often:

• Starts with an adjacency list (edges in a file: u v per line)
• Converts to a sparse matrix format for GPU processing (e.g., PyTorch Geometric, DGL)

You can think of sparse matrices as a middle ground between lists and full matrices: matrix-like interface, list-like memory usage. Libraries from universities and research labs (for example, Stanford’s CS224W materials at stanford.edu) highlight this pattern.

Comparing operations: matrix vs list with concrete examples

Let’s pin this down with operations you actually care about. We’ll keep coming back to examples of graph representation: matrix vs list examples so the differences stay concrete.

Edge existence check

Graph: 10,000 vertices, around 100,000 edges.

• Adjacency matrix:
  • Memory: 10,000² = 100,000,000 entries
  • Edge check: M[u][v] in O(1)
• Adjacency list:
  • Memory: proportional to 100,000 edges
  • Edge check: need to scan neighbors of u → O(degree(u))

If you’re building something like a small routing table where you constantly ask, “Is there a direct link from X to Y?”, and the graph is moderately dense, the matrix wins.

Iterating over neighbors

Same graph, but now you’re doing BFS or DFS from a node u.

• Adjacency matrix:
  • You scan the entire row M[u], length n
  • Time: O(n) per node
• Adjacency list:
  • You only visit actual neighbors
  • Time: O(degree(u)) per node

For sparse graphs (which is almost everything at scale), adjacency lists are dramatically faster for traversals.

Example: BFS on a sparse web graph

Imagine a toy web graph:

• Vertices: 1,000,000 pages
• Edges: 5,000,000 links

With an adjacency matrix, each BFS step from a node scans 1,000,000 entries. With an adjacency list, it only scans the handful of outgoing links.

This is another real example of graph representation: matrix vs list examples that matters in practice: search engines, crawler infrastructure, and link analysis almost always use list-based or sparse-matrix-based representations.

Memory and scaling: back-of-the-envelope examples

Let’s put some approximate numbers on memory. Assume:

• Each matrix entry: 1 byte (this is optimistic)
• Each adjacency list neighbor entry: 8 bytes (node id + pointer/overhead, also simplified)

Example: 100,000-node graph

Case 1: Dense (about 50 million edges)

• Matrix: 100,000² = 10¹⁰ bytes ≈ 10 GB
• List: 50,000,000 edges × 8 bytes ≈ 400 MB

Case 2: Sparse (about 300,000 edges)

• Matrix: still 10 GB
• List: 300,000 × 8 bytes ≈ 2.4 MB

The sparse case is the reality for most large graphs. That 2.4 MB vs 10 GB contrast is the strongest quantitative example of graph representation: matrix vs list examples you could ask for.

For more on graph sparsity and scaling, many algorithms courses hosted on .edu domains (e.g., Cornell, MIT, Stanford) emphasize adjacency lists for exactly these reasons.

Summary: how to choose, with examples in mind

If you remember nothing else from these examples of graph representation: matrix vs list examples, keep this mental checklist:

• Use an adjacency matrix when:

  • The graph is small to medium and relatively dense
  • You need lightning-fast edge existence checks
  • You’re using matrix-based algorithms (e.g., Floyd–Warshall, some spectral methods)
  • You’re working with small induced subgraphs in ML pipelines

• Use an adjacency list when:

  • The graph is large and sparse (social networks, road networks, citation graphs)
  • You care about traversals (BFS/DFS), shortest paths (Dijkstra on sparse graphs), or connected components
  • You’re memory-constrained
  • You’re storing graphs persistently or streaming edges

The best way to internalize this is to keep these real examples in your head: classroom chat (matrix is fine), U.S. road network (list or sparse matrix only), social graph (list), citation graph (list), and ML subgraphs (often both).

FAQ: examples of graph representation and common questions

What are simple examples of graph representation for beginners?

The simplest example of graph representation is a tiny directed graph with three nodes A, B, C and edges A → B, B → C. As a matrix, you get a 3×3 grid with a couple of 1s; as a list, you get {'A': ['B'], 'B': ['C'], 'C': []}. This tiny case makes it easy to see how rows/columns map to lists of neighbors.

Which is better for real examples: adjacency matrix or adjacency list?

For almost all real examples at scale—social networks, road networks, citation graphs—an adjacency list (or a sparse matrix format) is better. Adjacency matrices are better for small, dense graphs or for algorithms that are naturally expressed as matrix operations.

Can you give examples of weighted graph representation in matrix vs list form?

Yes. In a weighted adjacency matrix, each entry M[i][j] stores the weight (like distance or cost), and non-edges use a sentinel like 0 or ∞. In a weighted adjacency list, each neighbor is stored with its weight, for example {'A': [('B', 5), ('C', 2)]}. Routing problems, like modeling highways and distances between cities in the U.S., are classic examples of weighted graph representation.

Are adjacency matrices ever used in large-scale systems?

They are, but usually as sparse matrices, not full dense ones. Large-scale recommendation systems and graph neural networks often convert adjacency lists into sparse matrix formats to run efficient linear algebra on GPUs. So even in big systems, you’ll see a mix: lists for storage, matrix-like structures for computation.

How do I choose the right representation in an interview setting?

Describe the graph’s size and density. If the interviewer hints at millions of nodes and relatively few edges per node, say “I’ll use an adjacency list.” If the graph is small or you need very fast edge lookups, say “Adjacency matrix works well here.” Bonus points if you mention that your choice is guided by the same kind of examples of graph representation: matrix vs list examples that show up in real-world systems.