Sonith ManakkatA road map, a friendship network and the links between web pages look nothing alike, yet they share one shape: things joined by connections. Computer scientists call that shape a graph, and a handful of algorithms can answer questions about any graph: Can I get from here to there? What is the fewest number of steps? What is the cheapest route? This part shows three of them on a small map of six towns. Each section has a plain picture, then an Expert view. Every animation also has a text version of its steps underneath.
What a graph is
Two extra ideas make graphs more useful:
- Weights. An edge can carry a number, such as the distance or travel time of a road. A graph with such numbers is a weighted graph. Without them every edge counts the same.
- Direction. A road may be two-way, or one-way. A friendship on a network that needs both people to agree is two-way; a web page linking to another page is one-way. A graph with one-way edges is directed.
Undirected, unweighted
- Friendship: if A knows B, B knows A
- Every link counts as one step
Directed, weighted
- A page links to another, not always back
- Each link has a cost, such as minutes
Expert viewRepresenting a graph in memory
Two standard representations exist. An adjacency list stores, for each node, a list of its neighbours (and weights). It uses O(V + E) space, where V is the number of nodes and E the number of edges, and it lets you walk through a node's neighbours quickly. An adjacency matrix is a V by V table where entry (i, j) says whether an edge from i to j exists (or holds its weight). It uses O(V squared) space but answers "is there an edge from i to j?" in constant time.
Rule of thumb: sparse graphs, where E is much smaller than V squared (road networks, most social networks), suit adjacency lists. Dense graphs, or problems that constantly ask "is there an edge here?", can suit a matrix. In an undirected graph each edge appears twice (once in each direction).
The two basic ways to explore
Both searches begin at a start node and visit every node they can reach. They differ in one thing: which waiting node they visit next.
Queue (BFS)
- First in, first out, like a shop line
- The oldest waiting town goes next
Stack (DFS)
- Last in, first out, like a pile of plates
- The newest waiting town goes next
Breadth-first search (BFS)
Show the 8 steps as text
- Start at A: a map of six towns joined by roads.
- Visit A (number 1): the oldest waiting town is next.
- Visit B (number 2): the oldest waiting town is next.
- Visit C (number 3): the oldest waiting town is next.
- Visit D (number 4): the oldest waiting town is next.
- Visit E (number 5): the oldest waiting town is next.
- Visit F (number 6): the oldest waiting town is next.
- Done: towns were reached ring by ring from A.
BFS keeps a queue of towns to visit. It takes the town at the front, marks it visited and adds its unvisited neighbours to the back. Because it finishes each ring before starting the next, it reaches every town by a route with the fewest edges.
BFS(start):
queue = [start]; mark start visited
while queue is not empty:
town = take from the front of queue
for each neighbour of town:
if neighbour not visited:
mark visited; add to the back of queueExpert viewBFS in more detail
BFS runs in O(V + E) time with an adjacency list, because each node is queued once and each edge examined once (twice for undirected graphs). Space is O(V) for the queue and visited set. To recover the actual route, store each node's parent when it is first discovered, then walk parents back from the target. Typical uses include shortest path by number of edges, finding connected components, checking whether a graph can be coloured with two colours, and "degrees of separation" questions. If edges have different weights, the fewest-hop route is not necessarily the cheapest, which is where Dijkstra comes in.
Depth-first search (DFS)
Show the 8 steps as text
- Start at A: a map of six towns joined by roads.
- Visit A (number 1): the newest town found is next, so we dive deeper.
- Visit C (number 2): the newest town found is next, so we dive deeper.
- Visit E (number 3): the newest town found is next, so we dive deeper.
- Visit F (number 4): the newest town found is next, so we dive deeper.
- Visit D (number 5): the newest town found is next, so we dive deeper.
- Visit B (number 6): the newest town found is next, so we dive deeper.
- Done: each branch was followed to its end before backing up.
DFS follows a road to a town, then onward from there, and only backs up when it hits a dead end or a town it has already seen. It can be written with an explicit stack, or with recursion (which uses the call stack; see part 6).
DFS(town):
mark town visited
for each neighbour of town:
if neighbour not visited:
DFS(neighbour)- Exploring all pathsTry every route, as in puzzles and planning
- Detecting cyclesMeeting a node already on the current trail reveals a loop
- Solving mazesGo until stuck, then back up
- Ordering tasksTopological order of jobs that depend on each other
Expert viewDFS in more detail
DFS also runs in O(V + E) time and uses O(V) space in the worst case for the stack or recursion depth. The order in which nodes finish gives useful structure: in a directed acyclic graph, listing nodes in reverse finishing order gives a valid order for tasks with dependencies (topological sort). In a directed graph, a cycle exists exactly when DFS meets an edge back to a node still on the current trail. DFS does not find shortest routes in general: the first route it finds can be very long. Very deep graphs can overflow the recursion limit, so an explicit stack is safer there.
Cheapest route: Dijkstra's algorithm
Show the 8 steps as text
- Start at A with distance 0. Numbers on roads are travel costs.
- Settle A (cost 0): the cheapest unfinished town. Update its neighbours.
- Settle C (cost 2): the cheapest unfinished town. Update its neighbours.
- Settle B (cost 3): the cheapest unfinished town. Update its neighbours.
- Settle E (cost 5): the cheapest unfinished town. Update its neighbours.
- Settle D (cost 6): the cheapest unfinished town. Update its neighbours.
- Settle F (cost 8): the cheapest unfinished town. Update its neighbours.
- Done: the cheapest cost from A to F is 8.
Dijkstra(start):
cost[start] = 0; cost[others] = infinity
repeat until every town is settled:
town = unsettled town with the smallest cost
settle town
for each road (town, next) with weight w:
if cost[town] + w < cost[next]:
cost[next] = cost[town] + wExpert viewCosts and the priority queue
The step "find the unsettled town with the smallest cost" is done with a priority queue. With a binary heap the total time is O((V + E) log V). Simple versions that scan an array for the minimum take O(V squared), which can be fine for small dense graphs. The correctness rests on this fact: with non-negative weights, the cheapest unsettled node cannot be improved by a route through other unsettled nodes, so its cost is final. As with BFS, storing a parent for each node recovers the route itself. For graphs with negative weights but no negative cycles, the Bellman-Ford algorithm works, at O(V times E) time.
A smarter guess: A*
Expert viewA* in one panel
A* (pronounced "A star") is Dijkstra with a hint. Instead of settling the node with the smallest cost so far, it picks the smallest of cost so far plus an estimate of the remaining distance to the goal, such as straight-line distance on a map. If the estimate never overestimates the true remaining cost (an admissible heuristic), A* still finds a cheapest route, usually exploring far fewer nodes because it leans towards the goal. A poor or overestimating guess loses that guarantee. The worst case is still no better than Dijkstra's, so the gain depends on how good the estimate is.
How navigation apps relate
In general terms, a navigation app can model junctions as nodes and road segments as weighted edges, with weights such as expected travel time, then use shortest-path ideas to pick a route. Real systems usually add faster refinements and live data for very large maps. I am describing the general idea and not how any particular product works.
Side by side
| Method | Finds | Time | Needs |
|---|---|---|---|
| BFS | Fewest hops | O(V + E) | Nothing special (edges all count the same) |
| DFS | A path, cycles, structure | O(V + E) | Nothing special |
| Dijkstra | Cheapest route | O((V + E) log V) with a binary heap | No negative weights |
| A* | Cheapest route, guided | Depends on the estimate | A sound distance estimate |
Try it by hand
- Draw six townsJoin them with about eight roads
- Number the roadsGive each a distance from 1 to 9
- Run BFSWrite the visit order using a queue on a side list
- Run DFSUse a stack, or follow trails and back up
- Run DijkstraKeep a table of best costs and cross out settled towns
- CompareIs the fewest-hops route also the cheapest?
Breadth counts steps, depth follows trails, and Dijkstra counts cost.
Frequently asked questions
Is BFS or DFS faster?
Both take O(V + E) time. They differ in the order of visiting and so in what they are good at.
Why not use BFS on a road map with distances?
BFS counts hops, not distance. The route with fewest roads may be much longer than a route with more, shorter roads.
Can Dijkstra handle one-way roads?
Yes. Direction only changes which neighbours are listed for each node.
What if two routes cost the same?
Any of them is a valid cheapest route. Which one an implementation returns depends on its tie-breaking.