subroute.
Beginner8 min readlive prototype

Unweighted Graphs

Every edge counts the same, so 'shortest path' means fewest hops — and BFS reads the distance off in expanding rings.

Overview

What this concept solves

An unweighted graph is one where every edge counts the same. There is no number on a line saying 'this hop costs 5 and that one costs 1' — an edge is either there or it isn't. That single property has a surprisingly large consequence: the length of a path is simply how many edges it uses, and 'the shortest path' means nothing more than 'the path with the fewest hops'. Distance becomes a pure count.

Because cost is uniform, you don't need a fancy algorithm to find shortest paths — a plain breadth-first search reads distance straight off the graph. BFS sweeps outward in rings: everything one hop from the source, then everything two hops away, then three. The first time it reaches a vertex, the number of rings it has crossed is that vertex's shortest distance. No edge weight to compare, nothing to relax, nothing to optimise except the hop count itself.

This is the right model whenever the connections are equivalent and you only care about reachability and degrees of separation. Friends-of-friends on a social network, fewest clicks between two web pages, fewest moves in a puzzle where every move is one move. The moment some edges genuinely cost more than others — kilometres on a road, dollars on a flight, latency on a link — you've left unweighted territory and need a weighted graph plus Dijkstra. Until then, every hop is one hop, and BFS is all you need.

Mechanics

How it works

Why 'shortest' collapses to 'fewest edges'

  • Every edge has the same weight — call it 1. So the cost of a path is just its number of edges. A 3-edge path costs 3; a 2-edge path costs 2; 2 always beats 3.
  • There is nothing to optimise but the count — no clever combination of cheap-but-many vs expensive-but-few edges, because there is no 'expensive'. Fewer edges is unconditionally better.
  • A vertex's distance `d` is the number of hops on the fewest-edge path back to the source. The source itself is d=0; its neighbours are d=1; their new neighbours are d=2, and so on.
  • Distance is purely structural — it depends only on which edges exist, not on any number attached to them. Change the edges and the distances recompute; that's it.

Why BFS reads distance off directly

  1. Put the source in a queue with d=0. The queue holds the current frontier.
  2. Dequeue a vertex u. For each neighbour v you haven't seen, set d(v) = d(u) + 1 and enqueue it.
  3. Because the queue is FIFO, vertices come out in non-decreasing distance order: all the d=1 vertices before any d=2 vertex, all the d=2 before any d=3.
  4. So the first time a vertex is seen, the distance you assign it is already the smallest possible — any shorter route would have reached it on an earlier ring. First-seen = shortest.
  5. When the queue empties, every reachable vertex carries its hop-distance, and any unreached vertex is in a different component.

First-seen = shortest only because edges are equal

The whole 'first time we reach it is the shortest' guarantee rests on uniform edge cost. If one edge were 'longer' than another, a vertex reached early via a long edge could later be reached more cheaply via two short ones — and BFS, which doesn't look at weights, would already have locked in the wrong distance. That is exactly the case Dijkstra's algorithm exists to handle. On an unweighted graph, BFS is Dijkstra with every weight pinned to 1.

Adding an edge can only shrink distances

Distance is the minimum over all paths. Adding an edge gives you a new possible path without removing any old ones, so no distance can ever go up — it can only stay the same or drop. A 'shortcut' edge between two far-apart vertices is the dramatic case: a 3-hop path can collapse to 2 the instant the shortcut appears. Removing an edge is the mirror image — distances can only grow, or a vertex can fall out of reach entirely.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A seven-vertex undirected, unweighted graph across four tabs. Distance = hops runs a BFS from a source and labels every vertex with its hop-distance d=k, ring by ring; Fewest hops wins picks a start and target and highlights the path with the fewest edges; A shortcut shrinks it takes a 3-hop path, adds one shortcut edge, and re-runs to watch the distance drop to 2. Free play lets you click two vertices to toggle an edge, drag vertices, pick a source to recompute every d=k label live, and switch to Find-path mode — the live max distance stat tracks the farthest vertex.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Distance = hops

On the Distance = hops tab, press Play to run BFS from the source. Watch the rings light up: the source gets d=0, its neighbours d=1, theirs d=2. Each vertex is labelled with its hop-distance the moment it's first seen — and the narration reminds you that because every edge is weight-1, first time seen IS the shortest distance. The side panel shows the BFS queue (front → back) so you can see vertices leaving in non-decreasing distance order. Use Step / Back to move one dequeue at a time.

try 02

Fewest hops wins

Switch to Fewest hops wins. The prototype picks a start and a target and runs BFS to find the path with the fewest edges, highlighting it in orange. The narration makes the key point: with all edges equal there is nothing to optimise but the count — so 'shortest' here just means 'fewest hops'. The side panel lists the path vertices; note its edge count, the only number that matters.

try 03

A shortcut shrinks it

On A shortcut shrinks it, Play to see a 3-hop shortest path between two vertices. Then the prototype adds a shortcut edge between two non-adjacent vertices on that path and re-runs BFS — and the distance drops to 2. The before/after side panel makes it explicit. The lesson: distance is purely structural (hop count), recomputed the instant the edge set changes — adding an edge can only shrink it.

try 04

Free play — recompute distance live

Open Free play. Click any two vertices to toggle an edge; drag vertices to rearrange. Pick a source and every vertex's d=k label recomputes live — watch the max distance stat (the farthest any vertex sits from the source) shift as you add and remove edges. Add a shortcut and watch labels drop; cut an edge and watch them climb or turn to ∞ as vertices fall out of reach. Switch to Find path mode to trace the fewest-hops route between any two vertices you choose.

In practice

When to use it — and what you give up

Model it as unweighted when

  • Every connection is equivalent — a friendship is a friendship, a hyperlink is a hyperlink; none is 'worth more' than another.
  • You're counting degrees of separation — fewest hops between two people, fewest clicks between two pages, fewest moves in a puzzle where each move is one move.
  • You only care about reachability and structure — 'can I get there at all?' and 'how many steps away is it?' rather than 'how expensive is the route?'.
  • You want the cheapest correct shortest-path code — on an unweighted graph BFS gives exact answers in O(V + E) with no priority queue, no weight comparisons.

Reach for a weighted graph instead when

  • Edges genuinely cost different amounts — kilometres of road, dollars of airfare, milliseconds of latency, bandwidth on a link.
  • A longer-hop route can be cheaper — three short roads beating one long highway is invisible to BFS but is the whole point of Dijkstra.
  • You're trading off quantity against cost — when 'fewer edges' and 'cheaper total' can disagree, hop count is the wrong objective and you need real weights.

Pros

  • Shortest path is trivial — fewest edges, full stop; a single BFS reads every distance off in one O(V + E) pass.
  • No priority queue, no weight bookkeeping — just a FIFO queue and a visited set; the simplest correct shortest-path algorithm there is.
  • Distance is intuitive — 'three hops away' is exactly the degrees-of-separation number people already reason about.
  • Robust to edits — adding edges can only shrink distances, removing them can only grow distances; the model is easy to reason about as the graph changes.

Cons

  • Can't express real cost — a one-hop transatlantic flight and a one-hop bus ride look identical, which is wrong whenever distance or price matters.
  • Fewest-hops is sometimes the wrong objective — the route with the fewest edges can be the slowest or most expensive once edges differ.
  • No tie-breaking signal — many shortest paths can have the same hop count and the model gives you no reason to prefer one.
  • Migrating to weighted is a real change — once weights appear you must swap BFS for Dijkstra (or 0-1 BFS / A*); the easy guarantee doesn't survive.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

unweighted-graph.ts
// In an unweighted graph every edge costs the same, so "shortest path"
// means "fewest edges" — and BFS reads the distance off directly.
class UnweightedGraph {
  private adj = new Map<string, Set<string>>();

  addEdge(u: string, v: string) {
    if (!this.adj.has(u)) this.adj.set(u, new Set());
    if (!this.adj.has(v)) this.adj.set(v, new Set());
    this.adj.get(u)!.add(v);   // undirected: both directions
    this.adj.get(v)!.add(u);
  }

  // Hop-distance from `source` to every reachable vertex.
  // First time a vertex is dequeued-into = its shortest distance,
  // because the FIFO queue hands out vertices in distance order.
  distances(source: string): Map<string, number> {
    const dist = new Map<string, number>([[source, 0]]);
    const queue: string[] = [source];
    while (queue.length) {
      const u = queue.shift()!;            // front of the frontier
      for (const v of this.adj.get(u) ?? []) {
        if (!dist.has(v)) {                // first sighting = shortest
          dist.set(v, dist.get(u)! + 1);   // every edge adds exactly 1
          queue.push(v);
        }
      }
    }
    return dist;                           // missing key => unreachable (∞)
  }

  // The fewest-edge path itself, reconstructed from a parent map.
  shortestPath(source: string, target: string): string[] | null {
    const prev = new Map<string, string | null>([[source, null]]);
    const queue = [source];
    while (queue.length) {
      const u = queue.shift()!;
      if (u === target) break;
      for (const v of this.adj.get(u) ?? []) {
        if (!prev.has(v)) { prev.set(v, u); queue.push(v); }
      }
    }
    if (!prev.has(target)) return null;    // different component
    const path: string[] = [];
    for (let c: string | null = target; c !== null; c = prev.get(c)!) path.unshift(c);
    return path;                           // path.length - 1 === hop count
  }
}

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

In an unweighted graph, what does the 'shortest path' between two vertices mean?

question 02 / 03

Why can a plain BFS read the shortest distance off an unweighted graph without any extra optimisation?

question 03 / 03

You add a single new edge that acts as a shortcut between two distant vertices. What can happen to the shortest distances in the graph?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Graph Theory