Course contentsShow
← Computer Science
Lesson 677 of 2,87216. Graphs: Representation and Basic ConceptsFree lesson

Weighted Graph Representations

Extend adjacency matrices and lists to store edge weights using tuples or additional arrays.

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.