Overview
An edge list stores each edge as a pair or record of endpoints. It is simple, compact for algorithms that scan edges, and common in graph input formats.
FoundationSource checked
Edge List Representation
Represents a graph as a list of edges, optionally with weights or other edge data.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Graph Data Structures
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
edge recordendpoint pairgraph inputedge scan
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(E)
Worst
O(E)
Space
O(E)
When to Use
- Use it when algorithms need to scan all edges.
- Use it for simple graph input, output, or interchange formats.
- Use it when the graph is mostly processed edge by edge.
When Not to Use
- Avoid it when frequent neighbor lookup is needed.
- Avoid it when constant-time edge-existence checks are required.
- Avoid it when repeated traversal from vertices dominates the workload.
What It Does
- Stores graph edges as endpoint records
- Supports algorithms that process edges directly
Use Cases
- Graph file formats
- Kruskal-style minimum spanning tree algorithms
- Bulk edge processing
Inputs
- Keys, values, items, or graph records
- Operations such as insert, delete, or query
Outputs
- Stored structure state
- Query result or updated collection
Pseudocode
- 1.Create an empty edge list.
- 2.For each graph connection:
- 3.Append a record containing the endpoints and optional edge data.
- 4.When processing, iterate through the records in the list.
Canonical Example
- Input
- edges = [(A, B), (B, C)]
- Output
- two edge records
- Explanation
- Each tuple directly names one connection in the graph.
Implementation Notes
- Represent each edge as (source, target) plus optional weight or metadata.
- For undirected graphs, decide whether one record or two directed records are stored.
- Build adjacency lists from an edge list when traversal becomes frequent.
Common Pitfalls
- Forgetting to store direction or weight when the graph requires it.
- Scanning the entire edge list for every neighbor query.
- Duplicating undirected edges without documenting the convention.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow storing graph edges as endpoint records on a small graph representation example.
Step 1 of 4: Create an empty edge list.
data-structures-mechanismNotes
Edge lists are easy to store and sort, but they are not optimized for neighbor queries.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for Edge List Representation graph representation choices and traversal implications.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toGraph Adjacency List
Data Structures · Foundation
Adjacency lists organize the same graph around neighbor queries instead of edge scans.
Compare with thisRelationships
View full relationship pageAlternative toGraph Adjacency List
Adjacency lists organize the same graph around neighbor queries instead of edge scans.
Alternative toGraph Adjacency Matrix
Adjacency matrices favor direct edge-existence checks at higher memory cost.
Alternative toCompressed Sparse Row
CSR stores sparse adjacency more compactly for indexed traversal and numerical-style graph processing.
Related Algorithms
Tags
Data StructureGraph