Course contentsShow
← Computer Science
Lesson 676 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Edge List Representation

Store graphs as a simple list of edges, useful for algorithms that iterate over all edges.

Edge List Representation

What you'll learn: How to store a graph as a simple list of all its edges, ideal for algorithms that need to process every connection.

The Core Idea

An edge list is the most straightforward way to represent a graph: you literally just list out every edge. For an undirected graph, each edge is a pair of vertices like (u, v). For a directed graph, the order matters: (u, v) means an edge from u to v. If your graph is weighted, you add the weight: (u, v, weight).

Think of it like writing down all the friendships in a social network without any fancy organization—just "Alice knows Bob," "Bob knows Charlie," "Alice knows David," and so on.

When Edge Lists Shine

Edge lists excel when your algorithm naturally iterates through all edges:

  • Kruskal's Minimum Spanning Tree algorithm processes edges sorted by weight
  • Detecting if a graph has any edges
  • Counting total edges
  • Edge-centric operations like filtering connections by weight

The Trade-offs

Advantages:

  • Extremely simple to implement and understand
  • Memory-efficient for sparse graphs (few edges relative to vertices)
  • Easy to sort edges by weight or other properties

Limitations:

  • Checking if a specific edge exists? You might need to scan the entire list—that's O(E) time
  • Finding all neighbors of a vertex? Again, scan the whole list
  • Not ideal for algorithms that frequently query vertex neighbors

Example Structure

For an undirected graph with vertices {0, 1, 2} and edges 0-1, 1-2, the edge list would be:

[(0, 1), (1, 2)]

Key Takeaway: An edge list stores a graph as a simple collection of edges—perfect for algorithms that process all edges sequentially, though inefficient for neighbor queries.