Course contentsShow
← Mathematics
Lesson 2656 of 3,12153. Graph TheoryFree lesson

Graph Representations: Adjacency List and Edge List

Represent graphs using adjacency lists for each vertex and edge lists, comparing efficiency for different operations.

Graph Representations: Adjacency List and Edge List

You'll learn how to represent graphs using adjacency lists and edge lists, and when each representation is most efficient.


What Are These Representations?

Beyond the adjacency matrix you've seen, graphs can be stored in more space-efficient ways depending on how you'll use them.

An adjacency list stores, for each vertex, a list of all vertices it's adjacent to (connected by an edge). Think of it like a social network where each person keeps a list of their friends.

An edge list simply stores all edges as pairs of vertices. It's like writing down every friendship once: (Alice, Bob), (Alice, Carol), etc.


Adjacency List Structure

For a graph with vertices {1, 2, 3, 4} and edges {(1,2), (1,3), (2,3), (3,4)}:

1: [2, 3]
2: [1, 3]
3: [1, 2, 4]
4: [3]

Space complexity: O(V + E), where V = vertices, E = edges. Efficient for sparse graphs (few edges).

Operations:

  • Check if edge exists: O(degree of vertex)
  • Find all neighbors: O(degree of vertex) — very fast!
  • Add edge: O(1)

Edge List Structure

Same graph as a simple list of edges:

[(1,2), (1,3), (2,3), (3,4)]

Space complexity: O(E). Most compact for sparse graphs.

Operations:

  • Check if edge exists: O(E) — must scan entire list
  • Find all neighbors: O(E) — must scan entire list
  • Iterate over all edges: O(E) — very fast!

When to Use Each

  • Adjacency list: Best for exploring neighbors, traversing graphs (BFS, DFS), sparse graphs
  • Edge list: Best when you mainly need to iterate over all edges, like in Kruskal's algorithm

Key Takeaway: Adjacency lists excel at neighbor queries (common in graph traversal), while edge lists are simplest but slowest for queries—choose based on which operations your algorithm needs most.