அகல-முதல் தேடல் (BFS) என்றால் என்ன?

Question

Accepted Answer

**BFS** ஒரு வரையறையை மட்ட-பட்ட-மட்ட வைப்பாக ஆராய்கிறது, ஒரு முனையின் அனைத்து அண்டை முனைகளை பார்வையிட்ட பின் ஆழமாக நகர்கிறது. இது **வரிசை** பயன்படுத்தி **குறுகிய பாதை** (குறைந்த விளிம்புகள்) எடைபோடப்படாத வரையறைகளில் கண்டுபிடிக்கிறது.

## கருத்து

ஒரு மூல முனையிலிருந்து தொடங்கி, அதை வரிசையில் வைக்கவும், பின் மீண்டும் முனையை அகற்றி, அதன் பார்வையிடப்படாத அண்டை முனைகளைப் பார்வையிட்டு வரிசையில் வைக்கவும். `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) வரிசை மற்றும் பார்வையிடப்பட்ட தொகுப்பிற்கு.

## பயன்படுத்த வேண்டிய போது / பிழைகள்

**எடையில்லாத வரையறைகளில் குறுகிய பாதை**, மட்டம்-வரிசை விலக்குதல், மற்றும் இணைக்கப்பட்ட கூறுகளைக் கண்டுபிடிப்பதற்கு BFS ஐப் பயன்படுத்தவும். இது DFS ஐ விட அதிக நினைவகத்தைப் பயன்படுத்துகிறது (ஒரு முழு எல்லையை ஒரே நேரத்தில்). எப்போதும் `visited` ஐ ட்র்যாக் செய்யவும் அல்லது சுழற்சிகளில் சுற்றிக்கொண்டு இருக்க பாடுபடலாம்.

## ஏன் இது முக்கியமாக உள்ளது

BFS என்பது குறுகிய பாதைக்கான *அல்கோரிதம்* ஆகும், ஒவ்வொரு விளிம்பும் சমানாக கணிக்கும் போது — திசைவள, வலை ஊர்வளம், சামூஹிக-வலை பிரிப்பு அளவுகள்.

இதன் வரிசை-அடிப்படைய, மட்ட-பட்ட-மட்ட கட்டமைப்பு ஒரு அடிப்படைய ஆயக்கட்ட முறை ஆகும்.

BFS மற்றும் DFS ஜ்ஞானம் உங்களை பயணம், பாதைகள் மற்றும் வரிசைமுறைப்பு சிக்கல்களுக்கு சரியான கருவியைத் தேர்வுசெய்யும்.