Weighted Graph Representations
What you'll learn: How to extend basic graph structures to store numerical weights on edges, enabling graphs to model real-world distances, costs, or capacities.
The Core Idea
In many practical applications—like GPS routing (distances), network bandwidth (capacities), or flight booking (ticket prices)—edges have numerical values attached to them. We call these values weights. To represent weighted graphs, we adapt our familiar adjacency matrices and adjacency lists by storing weight information alongside connectivity data.
Extending Adjacency Matrices
For an unweighted graph, the adjacency matrix stores 1 (edge exists) or 0 (no edge). For a weighted graph, simply replace the 1 with the actual edge weight:
A B C
A 0 50 ∞
B 50 0 20
C ∞ 20 0
Here, 50 means edge A→B has weight 50. Use ∞ (infinity, or a very large number) to indicate "no edge."
Extending Adjacency Lists
Instead of storing just neighbor vertices, each entry now includes the weight. You have two common approaches:
1. Tuples/Pairs: Each list element becomes a (neighbor, weight) pair:
A: [(B, 50), (C, 100)]
B: [(A, 50), (C, 20)]
C: [(A, 100), (B, 20)]
2. Parallel arrays: Keep one list for neighbors and a matching list for weights (less common, but possible).
The tuple approach is cleaner and keeps related data together.
When to Use Which
- Weighted adjacency matrix: Fast weight lookups for dense graphs, but wastes space storing many
∞values. - Weighted adjacency list: Space-efficient for sparse graphs, supports easy iteration over actual edges.
Key Takeaway: Weighted graphs store edge costs by replacing boolean connectivity with numerical values—use actual weights in matrix cells or (vertex, weight) tuples in adjacency lists.