BFS Shortest Path — அடிப்படை

BFS Shortest Path — வரைபடத்தில் முக்கியமான நுட்பம்.

உண்மை உலகில் இது ஏன் முக்கியம்?

வரைபடம், சமூக வலை, சார்பு அமைப்பு — தலைகோடுகள்/விளிம்புகள் மாதிரி.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

FIFO வரிசை; dist/parent; கட்டத்தில் (r,c).

Pythonில் முயற்சி செய்வோம்

from collections import deque


def bfs_shortest(adj: list[list[int]], start: int) -> list[int]:
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist


print(bfs_shortest([[1, 2], [0], [0]], 0))

பொதுவான தவறுகள்

• எடையுள்ளில் BFS தவறு.
• visited மறப்பு.

முக்கிய பாடங்கள்

• பல மூல BFS.
• 0-1 deque.