Data Structures & Algorithms·Reason about cost and structure

Trees, graphs and traversal

Recursive structure needs a visited strategy and a clear base case.

Intermediate 15 min read Lesson 10 of 300 Challenge included

What you will be able to do

Every traversal needs a base case and a visited rule.
Use BFS for shortest paths in unweighted graphs.
Do not assume a graph is a tree unless you can prove no cycles.

In plain English

A tree is a graph with no cycles; a binary search tree orders values. Depth-first traversal uses a stack or recursion; breadth-first uses a queue. For general graphs, mark visited nodes or you will revisit forever.

traverse.jsJavaScript

function breadthFirst(graph, start) {
  const visited = new Set([start])
  const queue = [start]
  const order = []

  while (queue.length) {
    const node = queue.shift()
    order.push(node)
    for (const neighbour of graph[node] ?? []) {
      if (!visited.has(neighbour)) {
        visited.add(neighbour)
        queue.push(neighbour)
      }
    }
  }
  return order
}

Your turn

Traverse a graph

Hard

Return the breadth-first order of a graph starting at "html", avoiding visited nodes.

JS · starter

function bfs(graph, start) {}

Check your understanding before moving on.

Knowledge checkQuestion 1

Which traversal is the natural choice for shortest paths in an unweighted graph?

Select an answer to continue

Study tools

Make it yours.

Keep a private note for this lesson, then turn the key ideas into flashcards you can revisit.

Sign in to save notes and flashcards.Both are private to your account and stay with your progress.

Finished reading?

Lock in what you just learned.

Mark this lesson complete to save your place and move one step closer to the certificate.

Next: Drill 1: Summarise — Recursion

Lesson 10 of 300 · 0% of course