Weighted vs Unweighted Graphs
What you'll learn: You'll understand the difference between graphs where edges have numeric values (weights) versus graphs where edges simply exist or don't.
The Core Distinction
In the graphs you've seen so far, edges either connect two vertices or they don't—like friendships on social media where you're either friends or you're not. These are unweighted graphs: the edge's existence is all that matters.
But many real-world relationships aren't just yes/no—they have degrees or costs associated with them. This is where weighted graphs come in. Each edge carries a numeric value called a weight that represents some meaningful quantity.
Real-World Analogies
Unweighted graph: A map showing which cities have direct flights between them. Either a flight exists or it doesn't.
Weighted graph: The same map, but now each flight edge shows the distance in miles, ticket price, or flight duration. The connection exists and has a meaningful number attached.
Common Weight Meanings
- Distance: Road networks where weights represent miles/kilometers
- Cost: Networks where weights represent monetary expense
- Time: Routes where weights represent travel duration
- Capacity: Pipelines where weights represent maximum flow
- Strength: Social networks where weights represent interaction frequency
Representation Impact
In an unweighted graph, you only track which vertices connect. In a weighted graph, you must also store the weight value for each edge—this affects how you represent the graph in memory and how you process it algorithmically. For example, finding the "shortest path" in an unweighted graph means fewest edges; in a weighted graph, it means minimum total weight.
Key Takeaway: Unweighted graphs model binary relationships (connected or not), while weighted graphs add numeric values to edges to represent costs, distances, capacities, or other meaningful quantities—enabling richer modeling of real-world networks.