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.