DSA · Theory

Breadth First Search or BFS for a Graph

Theory

237/810

Breadth First Search or BFS for a Graph

Breadth First Search or BFS for a Graph 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 Breadth First Search or BFS for a Graph.

From the example next to this theory: Breadth First Search or BFS for a Graph — 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 Breadth First Search or BFS for a Graph? Then show BFS queue / DFS stack. Then name the trap.

Exam tip

What is Breadth First Search or BFS for a Graph? 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))

Breadth First Search or BFS for a Graph — bFS explores level by level using a queue.

Short notes

DefBreadth First Search or BFS for a Graph — 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))

Breadth First Search or BFS for a Graph

Example

Short notes

Questions

Breadth First Search or BFS for a Graph

Example

Short notes

Questions