---
title: "Breadth-First and Depth-First Search"
description: "Two ways to visit every node reachable from a start point: one takes a queue and spreads out level by level, the other takes a stack and follows one path as far as it goes. The choice of structure is "
canonical: https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy
source: https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Breadth-First and Depth-First Search

Two ways to visit every node reachable from a start point: one takes a queue and spreads out level by level, the other takes a stack and follows one path as far as it goes. The choice of structure is the whole difference between them.

Subject: Computing · Area: Algorithms & Data Structures · Ages 17 to 18
Page: https://lightmysky.com/learn/computing/breadth-first-and-depth-first-search-mt_q8IEzoBhzy

## Ready when they can

- Give the visit order both searches produce on the same graph from the same start
- Explain why swapping the queue for a stack turns one search into the other
- Say why visited nodes must be recorded, and what happens on a cycle if they are not

## Lesson: Two ways to walk a graph

Breadth first search spreads level by level using a queue. You visit every neighbour of the start before stepping further out, so the first time you reach a node you arrived by the fewest hops. That makes it the route finder for unweighted graphs.

**Example.** You run the queue by taking its front, visiting unvisited neighbours, and joining them to the back. The queue forces level order. Swap the queue for a stack and the walk turns into depth first search: you dive down one path as far as it goes and backtrack only when stuck.

You always keep a visited record beside the waiting line. Each vertex and edge is then handled once, which costs order V plus E. Without the record, a cycle sends the search around forever, queueing the same nodes again and again.

**Tip.** You usually store the graph as adjacency lists pairing each node with neighbours, which stays compact on sparse graphs. When asked for the fewest hops route, you reach for breadth first search, not depth first.

**Recap.** Queues spread in waves for fewest hops, stacks dive deep, and visited records stop cycles.

## Practice

8 questions on this page, each with its working shown.

## Needs first

- [Queues: First In, First Out](https://lightmysky.com/learn/computing/queues-first-in-first-out-mt_4U1bT0JW4g)
- [Graphs and How to Store Them](https://lightmysky.com/learn/computing/graphs-and-how-to-store-them-mt_tSO-F1sTuu)

## Opens up

- [Dijkstra's Shortest Path](https://lightmysky.com/learn/computing/dijkstras-shortest-path-mt_GvUzbY92qL)
- [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n)