DSA · Theory

Islands in a graph using BFS

Theory

560/810

Islands in a graph using BFS

Islands in a graph using BFS 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 Islands in a graph using BFS.

From the example next to this theory — Islands in a graph using BFS — 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 Islands in a graph using BFS? Then show BFS queue / DFS stack. Then name the trap.

Exam tip

What is Islands in a graph using BFS? 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))

Islands in a graph using BFS — bFS explores level by level using a queue.

Short notes

DefIslands in a graph using BFS — 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))

Islands in a graph using BFS

Example

Short notes

Questions

Islands in a graph using BFS

Example

Short notes

Questions