---
title: "breadth first search"
type: concept
source: https://www.jemoka.com/posts/kbhbreadth_first_search/
confidence: high
status: active
---

L = [[start_node]]+[[] for _ in 1 ... n] start_node.visited = True for i = 0 ... n-1: for u in L[i]: for v in neighbor(u): if not v.visited: v.visited = True L[i+1].append(v) This uses \(O\qty(n+m)\). We can find the shortest paths in \(O\qty(m)\)
