DSA · Theory

Difference between BFS and DFS

Theory

77/810

Difference between BFS and DFS

Difference between BFS and DFS is a DSA topic. In plain words you use it for bus routes in a city map. Don’t start with a slogan — start with that picture.

Smallest example: BFS queue / DFS stack. Type it, run it, and say what you see. If you can do that from memory, you know Difference between BFS and DFS.

From the example next to this theory — Difference between BFS and DFS — bFS explores level by level using a queue.

Trap — no visited set → infinite loop. Fix that before you talk about advanced DSA.

Viva — what is Difference between BFS and DFS? Then show BFS queue / DFS stack. Then name the trap.

Exam tip

What is Difference between BFS and DFS? Show this: BFS queue / DFS stack. Trap: no visited set → infinite loop.

Example

from collections import deque

graph = {1: [2, 3], 2: [4], 3: [], 4: []}

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

print(bfs(1))

Difference between BFS and DFS — bFS explores level by level using a queue.

Short notes

DefDifference between BFS and DFS — bus routes in a city map.
RuleBFS queue / DFS stack
Trapno visited set → infinite loop
Usea city map

from collections import deque graph = {1: [2, 3], 2: [4], 3: [], 4: []} def bfs(start): seen, q = {start}, deque([start]) order = [] while q: u = q.popleft() order.append(u) for v in graph[u]: if v not in seen: seen.add(v) q.append(v) return order print(bfs(1))

Difference between BFS and DFS

Example

Short notes

Questions

Difference between BFS and DFS

Example

Short notes

Questions