Sign in
Skip to solution
mediumDSA

What is the difference between BFS and DFS?

525 views
01

Understand the problem

Compare graph traversals.

graphsbfsdfs
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

BFS explores level by level using a queue — finds shortest paths in unweighted graphs. DFS goes as deep as possible using a stack/recursion — good for cycle detection, topological sort, and connectivity. Both are O(V+E).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

BFS and DFS on an adjacency list
Run Playground
from collections import deque

def bfs(graph, start):
    seen, q, order = {start}, deque([start]), []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in seen:
                seen.add(nb); q.append(nb)
    return order

def dfs(graph, node, seen=None, order=None):
    if seen is None: seen, order = set(), []
    seen.add(node); order.append(node)
    for nb in graph[node]:
        if nb not in seen:
            dfs(graph, nb, seen, order)
    return order


# --- demo ---
graph = {0: [1, 2], 1: [0, 3, 4], 2: [0], 3: [1], 4: [1]}
print(bfs(graph, 0))   # [0, 1, 2, 3, 4]
print(dfs(graph, 0))   # [0, 1, 3, 4, 2]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 67 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track