Weighted and Unweighted Graphs
What you'll learn: You'll discover the crucial difference between graphs with numerical edge values and those without, and when each type matters.
The Core Distinction
In graph theory, edges can either carry numerical values or not. An unweighted graph treats all edges as equal—they simply indicate a connection exists between two vertices. A weighted graph assigns a numerical value (called a weight) to each edge, representing some meaningful measure like cost, distance, time, or capacity.
Understanding Weights Through Analogy
Think of a city map. An unweighted graph might show which cities connect via roads—either a road exists or it doesn't. A weighted graph adds crucial information: how far apart the cities are, or how much time it takes to drive between them, or how expensive the toll is.
Similarly, in a social network, an unweighted graph shows friendships (connected or not), while a weighted graph might represent interaction frequency or friendship strength.
What Weights Represent
Edge weights commonly model:
- Distance: physical miles, network hops, or logical separation
- Cost: monetary expense, resource consumption, or computational effort
- Time: travel duration, processing delay, or transaction latency
- Capacity: bandwidth, flow limit, or maximum throughput
- Probability: likelihood of success, reliability, or confidence level
When to Use Each Type
Choose unweighted graphs when you only care about whether relationships exist—like mapping dependencies, social connections, or reachability problems.
Choose weighted graphs when the quality or strength of relationships matters—like finding shortest routes, optimizing costs, or managing network flows.
Key Takeaway: Weighted graphs add numerical edge values to represent real-world measurements like cost, distance, or capacity, while unweighted graphs simply indicate presence or absence of connections—choose based on whether relationship strength matters for your problem.