BFS (Graph)

Graphs

avgO(V + E)worstO(V + E)spaceO(V)

Start at A: mark it seen and put it in the queue

1 / 30

Code

function bfs(graph: Graph, source: number) {  const order: number[] = [];  const seen = new Set([source]);  const queue = [source];  while (queue.length > 0) {    const node = queue.shift()!;    order.push(node);    for (const next of graph.neighbours(node)) {      if (seen.has(next)) continue;      seen.add(next);      queue.push(next);    }  }  return order;}

procedure BFS(G, source)  order ← []  seen ← {source}  queue ← [source]  while queue is not empty do    node ← dequeue(queue)    append node to order    for each neighbour next of node, in label order do      if next ∈ seen then skip it      add next to seen      enqueue(queue, next)    end for  end while  return orderend procedure

Variables

queue=A

Counters

visited: 0
edges considered: 0

Nodes8

Source

Edges

How it works

Breadth-first search visits the source, then all of its neighbours, then their unseen neighbours, using a FIFO queue. Nodes come out in order of hop distance from the source, and the edges that discover new nodes form a shortest-path tree.

Complexity

Best: O(V + E)
Average: O(V + E)
Worst: O(V + E)
Space: O(V)

BFS (Graph)

How it works

Complexity

Search algorithms