BFS of graph | Practice Easy 0 attempts
GeeksforGeeks ↗

BFS of graph | Practice

Easy GraphBFSDFS GeeksforGeeks

You're given a directed graph described as an adjacency list adj, where adj[i] lists the nodes reachable directly from node i. Starting from node 0, return the order in which nodes are visited by a breadth-first traversal.

Input Format
Implement bfsOfGraph(adj). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
adj = [[1,2],[3],[4],[],[]]
Output
[0,1,2,3,4]

Example 2

Input
adj = [[1],[],[]]
Output
[0,1]
Constraints
  • 1 <= V <= 10^4
  • 0 <= E <= 10^4
  • Neighbors are visited in the listed order; vertices unreachable from 0 are omitted.
Test Cases (2)
Case 1
Args: [[[1,2],[3],[4],[],[]]] Expected: [0,1,2,3,4]
Case 2
Args: [[[1],[],[]]] Expected: [0,1]
Topics
GraphBFSDFS

Standard BFS

Use a queue and visited set to traverse level by level.

javascript
function bfsOfGraph(adj) {
  const visited = new Set([0]), q = [0], result = [];
  let head = 0;
  while (head < q.length) {
    const node = q[head++];
    result.push(node);
    for (const next of adj[node]) {
      if (!visited.has(next)) { visited.add(next); q.push(next); }
    }
  }
  return result;
}

Time: O(V + E) | Space: O(V)

Saved in this browser only. Private to you.

JavaScript