A graph is formally an ordered pair of a vertex set and an edge set, and the edge-list representation stores it literally as two lists: one of vertex names and one of edge records, each edge holding its two endpoints (plus a weight field when the graph is weighted). Storing endpoints as indices into the vertex list rather than as copied names makes every edge row a fixed size, giving space complexity O(|V| + |E|), which is near-optimal for storing a graph. Its weakness is time: the fundamental queries — enumerating a vertex's neighbours, or testing adjacency between two vertices — require a linear scan of the edge list at O(|E|), and since |E| can reach the order of |V|², this representation is considered inefficient and motivates the adjacency-based representations studied next in graph theory and data structures.
A graph is formally an ordered pair of a vertex set and an edge set, and the edge-list representation stores it literally as two lists: one of vertex names and one of edge records, each edge holding …