რა არის სიღრმისეული ძიების ალგორითმი?

საზღვრების ძიების ალგორითმი (BFS - Breadth-First Search) — ეს არის ალგორითმი, რომელიც გამოიყენება ხის ან გრაფის გადალახვაში ან ძიებაში. ის იწყება ძირითადი კვანძიდან (ან შემთხვევით კვანძიდან, თუ გრაფი არ არის ხე) და იკვლევს მის ყველა უშუალო მეზობელს, შემდეგ მეზობელების მეზობელებს და ასე შემდეგ, დონე დონეზე. BFS განახორციელებს რიგის გამოყენებით.

სამუშაო პრინციპი:

1. ჩადეთ საწყისი კვანძი რიგში.
2. სანამ რიგი არ არის ცარიელი:
   • ამოიღეთ კვანძი რიგიდან.
   • თუ კვანძი არის სასურველი, შეჩერდით ძიება.
   • წინააღმდეგ შემთხვევაში, ჩადეთ მისი ყველა არასათავისუფლო მეზობელი რიგში და მონიშნეთ ისინი როგორც მონახულებული.

მახასიათებლები:

• სრულყოფილება: გარანტირებულია გადაწყვეტილების პოვნა, თუ ის არსებობს.
• ოპტიმალურობა: პოულობს მოკლე გზას უსწორმასწორო გრაფში (სადაც წონები თანაბარია).
• დროის სირთულე: დამოკიდებულია გრაფის სტრუქტურაზე, E კიდეების და V კვანძების შემთხვევაში — O(V + E).
• მეხსიერების სირთულე: O(V) ყველაზე უარეს შემთხვევაში, რადგან საჭიროა შენახული იყოს მონახულებული კვანძები და რიგი.

გამოყენება QA-ში:

• მოკლე გზის ძიება კვანძებს შორის ტესტის სცენარებში.
• სისტემის ყველა მისაღწევი მდგომარეობის კვლევა ფინალური ავტომატების ტესტირებისას.
• ყველა გვერდის ხელმისაწვდომობის ტესტირება ვებ-გვერდზე კრაულინგის დროს.

მაგალითი (ხის გადალახვა):

from collections import deque

# ხის წარმოდგენა სლოვარით მეზობელობით
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# მაგალითი გამოძახების
# bfs(graph, 'A')
# შედეგი:
# A
# B
# C
# D
# E
# F