SimuVedaAlgorithms Lab Open in the lab

Graphs / Beginner

Breadth-First Search Visualizer

Visit the start, then all its neighbors, then their neighbors. A queue keeps nodes in the order they were found.

Start the Breadth-First Search simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V+E)
Average timeO(V+E)
Worst timeO(V+E)
Extra spaceO(V)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start at A. Mark it seen and put it in the queue.
  2. Take A from the front of the queue.
  3. Visit A.
  4. B is new. Mark it seen and add it to the back of the queue.
  5. C is new. Mark it seen and add it to the back of the queue.
  6. Take B from the front of the queue.
  7. Visit B.
  8. A was already seen. Skip it.
  9. C was already seen. Skip it.
  10. D is new. Mark it seen and add it to the back of the queue.
  11. Take C from the front of the queue.
  12. Visit C.
  13. A was already seen. Skip it.
  14. B was already seen. Skip it.
  15. D was already seen. Skip it.
  16. E is new. Mark it seen and add it to the back of the queue.
  17. Take D from the front of the queue.
  18. Visit D.
  19. B was already seen. Skip it.
  20. C was already seen. Skip it.
  21. … 8 more steps …
  22. Visit F.
  23. D was already seen. Skip it.
  24. E was already seen. Skip it.
  25. Done. Visit order: A, B, C, D, E, F.

Try it with your own input →

Breadth-first search in Java, Python, C++, C and JavaScript

void bfs(int start) {
  Queue<Integer> q = new ArrayDeque<>();
  boolean[] seen = new boolean[n];
  q.add(start); seen[start] = true;
  while (!q.isEmpty()) {
    int u = q.poll();
    visit(u);
    for (int v : adj[u]) {
      if (!seen[v]) {
        seen[v] = true;
        q.add(v);
      }
    }
  }
}
from collections import deque

def bfs(adj, start):
    q = deque()
    seen = [False] * len(adj)
    q.append(start); seen[start] = True
    while q:
        u = q.popleft()
        visit(u)
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                q.append(v)
void bfs(const vector<vector<int>>& adj, int start) {
  queue<int> q;
  vector<bool> seen(adj.size(), false);
  q.push(start); seen[start] = true;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    visit(u);
    for (int v : adj[u]) {
      if (!seen[v]) {
        seen[v] = true;
        q.push(v);
      }
    }
  }
}
#define MAXN 100
int n, adj[MAXN][MAXN], deg[MAXN];   /* adj[u][0..deg[u]-1] are u's neighbours */

void bfs(int start) {
  int q[MAXN], head = 0, tail = 0;
  int seen[MAXN] = {0};
  q[tail++] = start; seen[start] = 1;
  while (head < tail) {
    int u = q[head++];
    visit(u);
    for (int k = 0; k < deg[u]; k++) {
      int v = adj[u][k];
      if (!seen[v]) {
        seen[v] = 1;
        q[tail++] = v;
      }
    }
  }
}
function bfs(adj, start) {
  const q = [];
  const seen = new Array(adj.length).fill(false);
  q.push(start); seen[start] = true;
  let head = 0;
  while (head < q.length) {
    const u = q[head++];
    visit(u);
    for (const v of adj[u]) {
      if (!seen[v]) {
        seen[v] = true;
        q.push(v);
      }
    }
  }
}

In an interview

BFS finds the shortest path when every edge costs the same. Think "fewest moves" problems.

More graphs