GraphsData structureaka list of edges, edge array

Edge List

The graph as a flat list of (u, v[, w]) tuples — minimal, sortable, and exactly what Kruskal and Bellman-Ford need.

▶ Visualize Pattern: Union-Find Practice (4)

Progress

Definition

An edge list is the simplest graph representation: an array of edges, each a pair (u, v) or a triple (u, v, w). It is also the most common input format in problems ("edges[i] = [uᵢ, vᵢ, wᵢ]") and is usually converted into an Adjacency List before traversal.

A few algorithms work directly on the edge list and are simpler for it: Kruskal's Algorithm sorts edges by weight and unions endpoints with Union-Find (Disjoint Set Union); Bellman-Ford relaxes every edge V - 1 times; counting degrees or detecting a redundant connection is a single pass.

It offers no way to find a vertex's neighbors without scanning all E edges, so it is unsuitable for Breadth-First Search (BFS), Depth-First Search (DFS), or Dijkstra's Algorithm as-is.

O(E) spacesortableKruskalBellman-Fordinput format

Intuition

A mental model before the formal terms.

A spreadsheet with one row per road: from, to, length. Sorting the sheet by length and walking down it is Kruskal. Asking "which roads leave town X?" means reading every row — that is why you build a per-town index (an adjacency list) before doing traversals.

How it works

Store edges = [(u, v, w), …]; for an undirected graph store each edge once.
addEdge: append. removeEdge: find and splice, O(E).
toAdjacencyList(): create V empty lists and push each edge into adj[u] (and adj[v]).
Kruskal's Algorithm: sort by w, then for each edge union(u, v); edges whose endpoints are already connected are skipped (they would form a cycle).
Bellman-Ford: dist[s] = 0; repeat V - 1 times: for every (u, v, w), dist[v] = min(dist[v], dist[u] + w).
Degree counting: one pass incrementing deg[u] and deg[v].

Why it works

Any graph is fully determined by its vertex count and edge set, so the list is a complete (if unindexed) representation.

Algorithms that process edges in a global order (by weight, or all edges per round) never need adjacency, so the list is not just sufficient but ideal for them.

Operations

Operation	Description	Cost
addEdge(u, v, w)	Append a tuple.	O(1)
removeEdge(u, v)	Linear search and splice.	O(E)
hasEdge(u, v)	Linear scan.	O(E)
neighbors(u)	Scan every edge for endpoint u.	O(E)
sortByWeight	Standard sort.	O(E log E)
toAdjacencyList	One pass.	O(V + E)
degrees	One pass.	O(V + E)

Recognition

How to tell a problem wants this.

The input is given as edges = [[u, v], …] — always the starting point.
Minimum spanning tree → sort edges → Kruskal.
Negative weights or "at most k edges" → Bellman-Ford over the edge list.
A question about a single edge (redundant connection, critical edge) is often a scan plus union-find.

“connected groups” → Union-Find “maximum number of non-overlapping” → Greedy

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Kruskal's Algorithm visualization.

Weighted graph — One edge per line: "A B 4". Optional "source: A" / "target: F" lines.

Edges by weight

B–G (1)A–C (2)G–E (2)E–F (3)G–D (3)A–B (4)B–D (5)D–F (6)C–G (8)C–E (10)

DSU parent

node	parent	root
A	A	A
B	B	B
C	C	C
D	D	D
E	E	E
F	F	F
G	G	G

1/15Sort the 10 edges by weight and put each node in its own set. Kruskal grows a forest by taking the cheapest edge that joins two different trees.

Edge under considerationAccepted (MST)Rejected (cycle)Node in some tree

PseudocodeLearn Kruskal's Algorithm →

1sort edges by weight ascending
2make_set(v) for every node
3for (u, v, w) in edges:
4  if find(u) != find(v):
5    union(u, v); mst.add((u, v, w))
6  else: skip — u and v already connected, edge would close a cycle
7return mst

Complexity

best O(E log E)

avg O(E log E)

worst O(E log E)

space O(V + E)

Speed

Pseudocode

1edges = [(u, v, w), ...]
2kruskal(): sort edges by w; dsu = UnionFind(V); total = 0
3  for u, v, w in edges: if dsu.union(u, v): total += w; picked.append((u, v))
4to_adj(): adj = [[]]*V; for u, v, w in edges: adj[u].append((v, w)); adj[v].append((u, w))

Implementation

1from typing import NamedTuple
2 
3 
4class Edge(NamedTuple):
5    u: int
6    v: int
7    weight: int = 1
8 
9 
10class EdgeList:
11    """The flattest representation: just the edges, in whatever order they
12    came. Nothing is indexed, so it is the natural input format and the
13    natural working set for algorithms that sort edges."""
14 
151 · State: one flat list of edges plus the vertex count
16    def __init__(self, n: int) -> None:
17        self.n = n
18        self.edges: list[Edge] = []
19 
202 · Appending is O(1) and needs no per-vertex bookkeeping at all
21    def add_edge(self, u: int, v: int, weight: int = 1) -> None:
22        self.edges.append(Edge(u, v, weight))
23 
243 · Sorting by weight is the whole reason Kruskal prefers this form
25    def sort_by_weight(self) -> None:
26        self.edges.sort(key=lambda e: e.weight)
27 
284 · Any per-vertex query is O(E) — convert to lists if you need many
29    def to_adjacency_list(self, directed: bool) -> list[list[int]]:
30        adj: list[list[int]] = [[] for _ in range(self.n)]
31        for e in self.edges:
32            adj[e.u].append(e.v)
33            if not directed:
34                adj[e.v].append(e.u)
35        return adj
36 
375 · Degree needs a full scan, which is the representation weak point
38    def degree(self, u: int) -> int:
39        return sum((e.u == u) + (e.v == u) for e in self.edges)

Walkthrough

class Edge(NamedTuple) gives an immutable, tuple-backed record with named fields, __eq__, __repr__ and a default weight, all for three lines.
self.edges.sort(key=lambda e: e.weight) uses a key function rather than a comparator, which is the Python convention and calls the key once per element.
sum((e.u == u) + (e.v == u) for e in self.edges) relies on bool being an int subclass, so True + False is 1 — compact and idiomatic.
to_adjacency_list builds distinct rows with a comprehension, the fix for the [[]] * n aliasing trap.
Because Edge is a tuple, sorted(self.edges) would order by (u, v, weight) lexicographically — occasionally useful, and worth knowing is the default.

Complexity (this implementation)

time O(1) add_edge, O(E log E) sort, O(E) any per-vertex query, O(V + E) conversion · space O(E)

NamedTuple instances are tuples, so they are noticeably smaller than equivalent class instances without __slots__.

Language notes

NamedTuple is immutable and tuple-compatible; @dataclass(slots=True) is the mutable equivalent with similar memory characteristics.
list.sort(key=...) is stable TimSort and evaluates the key once per element (a Schwartzian transform done for you); a cmp_to_key comparator is much slower.
bool subclasses int, which is why (e.u == u) + (e.v == u) counts endpoints without a conditional.
operator.attrgetter("weight") is a slightly faster key than a lambda for large sorts, since it avoids a Python-level call.

Common mistakes in this language

Trying to mutate a NamedTuple field (e.weight = 5), which raises AttributeError — use e._replace(weight=5) or a dataclass.
Sorting with sorted(edges) and getting lexicographic (u, v, weight) order when weight order was intended.
Building to_adjacency_list with [[]] * n and aliasing every row.

Language differences that matter here

Record types: C++ uses an aggregate struct, TypeScript an interface, Python a NamedTuple, and JavaScript a plain object literal — only Python gets immutability and value equality for free.
Sorting API: C++ and JS/TS take a comparator (a < b and a - b respectively — note the different conventions), while Python takes a key projection, which is both faster and harder to get wrong.
JavaScript is the only one whose default sort is actively wrong for this data: with no comparator it stringifies every edge object.
Stability: Python sort and JS/TS sort (since ES2019) are stable; C++ std::sort is not, and std::stable_sort must be requested explicitly.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Edge by index.
Search	O(E)	O(E)	Edge (u, v) or neighbors of u.
Insert	O(1)	O(1)
Delete	O(E)	O(E)
Update	O(E)	O(E)	O(1) if the index is known.
Neighbors	O(E)	O(E)
Sort by weight	O(E log E)	O(E log E)
Convert to adjacency list	O(V + E)	O(V + E)
Space	O(E)		Plus O(V) if isolated vertices must be tracked.

Advantages & disadvantages

Advantages

Minimal memory: exactly E records, no per-vertex overhead.
Trivial to sort, filter, or shuffle edges.
Directly usable by Kruskal's Algorithm and Bellman-Ford.
Easy to serialise and matches typical input formats.

Disadvantages

No neighbor access — traversals are O(E) per vertex, O(VE) overall.
Edge lookup and deletion are O(E).
Isolated vertices are invisible unless V is stored separately.

Use cases

Kruskal's Algorithm minimum spanning tree.
Bellman-Ford and Cheapest Flights Within K Stops.
Redundant Connection: process edges in order with union-find.
Counting degrees, finding the center of a star graph, town judge.
Input parsing before building an Adjacency List.

Use it when

Kruskal's MST or any algorithm that sorts edges globally.
Bellman-Ford and bounded-hop shortest paths.
Single-pass edge statistics (degrees, duplicate detection, redundant edge).
As the input format before converting.

Avoid it when

Any traversal (BFS, DFS, Dijkstra) — convert to an Adjacency List first.
Frequent edge-existence queries — use an Adjacency Matrix or hash set of pairs.
Graphs with isolated vertices where vertex enumeration matters — store V explicitly.

Alternatives

Adjacency List Adjacency Matrix

Common mistakes

Running BFS by scanning the edge list for every vertex — O(VE).
Storing undirected edges twice and then double-counting weights in Kruskal.
Forgetting that vertices with no edges do not appear in the list.
Sorting in place when the original order matters (e.g. Redundant Connection needs input order).

Interview patterns

Min Cost to Connect All Points: generate all n(n-1)/2 edges, sort, Kruskal.
Redundant Connection: iterate edges in input order with union-find; the first failing union is the answer.
Cheapest Flights Within K Stops: k + 1 rounds of Bellman-Ford over the edge list with a copied distance array.
Find the Town Judge / Center of Star Graph: degree counting in one pass.

Interview questions on this

Greedy or dynamic programming?Advanced
Union-Find or DFS for connectivity?Advanced
Convincing me your algorithm is correctExpert

Mock interviews

Number of IslandsIntermediate
Merge IntervalsIntermediate

Interview problems

Critical Connections in a Networkhard Cheapest Flights Within K Stopsmedium Min Cost to Connect All Pointsmedium Redundant Connectionmedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related