Breadth-First Search

ব্রেডথ-ফার্স্ট সার্চ

Graph-এ start node থেকে স্তরে স্তরে প্রতিবেশী ঘুরে দেখা traversal — FIFO queue-এ চলে, unweighted graph-এ shortest path দেয়, O(V+E)।

also: bfs, breadth first search

Queue-ই সব: node প্রসেস করতে করতে তার না-দেখা neighbor-দের queue-র পেছনে বসাও — ফলে দূরত্ব ০, ১, ২, … ক্রমেই ছড়ায়।

q = deque([start]); dist = {start: 0}
while q:
    u = q.popleft()
    for v in adj[u]:
        if v not in dist:
            dist[v] = dist[u] + 1
            q.append(v)

প্রতিটা node আর edge ঠিক একবার ধরা হয় — O(V+E)।

মূল গ্যারান্টি: unweighted graph-এ dist[v]-ই shortest distance; weighted-এ Dijkstra, negative edge-এ Bellman-Ford লাগে। অন্য ব্যবহার: bipartite check, connected component, web crawler-এর frontier।