Τι είναι ο αλγόριθμος αναζήτησης σε πλάτος;

Ο αλγόριθμος αναζήτησης σε εύρος (BFS - Breadth-First Search) είναι ένας αλγόριθμος δια traversing ή αναζήτησης σε ένα δέντρο ή γράφο. Ξεκινά από τον ριζικό κόμβο (ή έναν τυχαίο κόμβο αν ο γράφος δεν είναι δέντρο) και εξερευνά όλους τους άμεσους γείτονές του, στη συνέχεια τους γείτονες αυτών των γειτόνων και ούτω καθεξής, επίπεδο προς επίπεδο. Το BFS υλοποιείται με χρήση ουράς.

Αρχή λειτουργίας:

Τοποθετήστε τον αρχικό κόμβο στην ουρά.
Όσο η ουρά δεν είναι άδεια:
- Αφαιρέστε έναν κόμβο από την ουρά.
- Αν ο κόμβος είναι ο ζητούμενος, σταματήστε την αναζήτηση.
- Διαφορετικά, τοποθετήστε στην ουρά όλους τους μη επισκεφθέντες γείτονές του και σημαδέψτε τους ως επισκεφθέντες.

Χαρακτηριστικά:

Πληρότητα: Διασφαλίζει την εύρεση λύσης αν υπάρχει.
Βέλτιστοτητα: Βρίσκει το συντομότερο μονοπάτι σε έναν άβαραιο γράφο (όπου τα βάρη των ακμών είναι ίσα).
Χρονική πολυπλοκότητα: Εξαρτάται από τη δομή του γράφου, για E ακμές και V κορυφές — O(V + E).
Μνήμη: O(V) στην χειρότερη περίπτωση, καθώς πρέπει να αποθηκεύσετε τις επισκεφθείσες κορυφές και την ουρά.

Εφαρμογές σε QA:

Αναζήτηση του συντομότερου μονοπατιού μεταξύ κόμβων σε σενάρια δοκιμών.
Εξερεύνηση όλων των επιτρεπτών καταστάσεων του συστήματος κατά τη δοκιμή πεπερασμένων αυτομάτων.
Δοκιμή της διαθεσιμότητας όλων των σελίδων ενός ιστότοπου κατά το crawling.

Παράδειγμα (περίοδος δέντρου):

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