Breadth-first search (BFS) શું છે?

Question

IT Interview Practice · Accepted Answer

**BFS** એક આલેખને સ્તર-દર-સ્તર શોધે છે, નોડના બધા પાડોશીઓને વધુ ગહરાણમાં જતા પહેલાં મુલાકાત લે છે. તે **queue** નો ઉપયોગ કરે છે અને બિન-વજનવાળા આલેખમાં **સૌથી ટૂંકો પાથ** (સૌથી ઓછી ધાર) શોધે છે.

## આશયો

સ્ત્રોત પર શરૂ કરો, તેને enqueue કરો, પછી વારંવાર નોડને dequeue કરો, તેના અવિક્ષીત પાડોશીઓને મુલાકાત લો અને તેમને enqueue કરો. એક `visited` સમૂહ પુનઃમુલાકાતને રોકે છે.

## ઉદાહરણ

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## જટિલતા

- **સમય:** O(V + E) — દરેક શિરોબિંદુ અને ધાર એકવાર.
- **સ્થાન:** O(V) queue અને visited સમૂહ માટે.

## ક્યારે વાપરવું / નુકસાન

**બિન-વજનવાળા આલેખમાં સૌથી ટૂંકો પાથ**, સ્તર-ક્રમ ટ્રેવર્સલ અને જોડાયેલ ઘટકો શોધવા માટે BFS નો ઉપયોગ કરો. તે DFS કરતાં વધુ મેમરી વાપરે છે (એક સમયે સંપૂર્ણ સરહદ). હંમેશા `visited` ટ્રેક કરો અથવા તમે ચક્રમાં હંમેશકાળ લુપ કરી શકો છો.

## શા માટે તે મહત્ત્વપૂર્ણ છે

BFS *સૌથી* ટૂંકા પાથ માટેનું એલ્ગોરિધમ છે જ્યારે દરેક ધાર સમાન રીતે ગણાય છે — રૂટિંગ, વેબ ક્રૉલિંગ, સામાજિક-નેટવર્ક અલગતા ડિગ્રી.

તેનું queue-આધારિત, સ્તર-દર-સ્તર માળખું એક મૂળભૂત ટ્રેવર્સલ પેટર્ન છે.

BFS વિરુદ્ધ DFS જાણવું તમને પહોંચાણીયતા, પાથ અને ક્રમ સમસ્યાઓ માટે યોગ્ય સાધન પસંદ કરવા દે છે.

આશયો

ઉદાહરણ

જટિલતા

ક્યારે વાપરવું / નુકસાન

શા માટે તે મહત્ત્વપૂર્ણ છે

સંબંધિત પ્રશ્નો