Represent a graph; BFS and DFS

Easy

Problem

Build an adjacency list from an edge list, then print the nodes in breadth-first order (level by level from the source) and in depth-first order (go as deep as possible before backtracking).

Example 1

Input:  edges = [[0,1], [0,2], [1,3], [2,4]], source 0
Output: BFS 0 1 2 3 4 · DFS 0 1 3 2 4

Also asked as: Create a Graph, print it · Implement BFS algorithm · Implement DFS Algo

Test cases

Case 1

Input:    [[1,2],[0,3],[0,4],[1],[2]], 0
Expected: [0,1,2,3,4]

Case 2

Input:    [[1,2],[0,3],[0,4],[1],[2]], 3
Expected: [3,1,0,2,4]

Case 3

Input:    [[1],[0],[]], 0
Expected: [0,1]

Case 4

Input:    [[]], 0
Expected: [0]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Adjacency list + queue (BFS) / stack or recursion (DFS)

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

Store neighbours per node. BFS explores in rings using a queue; DFS goes deep with recursion or an explicit stack.

function buildGraph(n, edges, directed = false) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) { adj[u].push(v); if (!directed) adj[v].push(u); }
return adj;
}
function bfs(adj, src) {
const seen = new Array(adj.length).fill(false), order = [];
const q = [src]; seen[src] = true;
for (let i = 0; i < q.length; i++) {
const u = q[i]; order.push(u);
for (const v of adj[u]) if (!seen[v]) { seen[v] = true; q.push(v); }
}
return order;
}
function dfs(adj, src, seen = new Array(adj.length).fill(false), order = []) {
seen[src] = true; order.push(src);
for (const v of adj[src]) if (!seen[v]) dfs(adj, v, seen, order);
return order;
}