BFS εξερευνά ένα γράφημα επίπεδο προς επίπεδο, επισκεπτόμενη όλους τους γείτονες ενός κόμβου πριν προχωρήσει βαθύτερα. Χρησιμοποιεί μια ουρά και βρίσκει το συντομότερο μονοπάτι (λιγότερες ακμές) σε μη σταθμισμένα γραφήματα.
Ξεκινήστε από μια πηγή, τοποθετήστε την σε ουρά, στη συνέχεια επαναλαμβάνοντας αφαιρέστε έναν κόμβο από την ουρά, επισκεφθείτε τους ανεπίσκεπτους γείτονές του και τοποθετήστε τους σε ουρά. Ένα σύνολο αποτρέπει την επανεπίσκεψη.
visitedfrom 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']
Χρησιμοποιήστε BFS για συντομότερο μονοπάτι σε μη σταθμισμένα γραφήματα, διέλευση επιπέδου και εύρεση συνδεδεμένων συστατικών. Χρησιμοποιεί περισσότερη μνήμη από DFS (ένα ολόκληρο σύνορο ταυτόχρονα). Παρακολουθείτε πάντα visited ή ενδέχεται να εισέλθετε σε άπειρο βρόχο σε κύκλους.
BFS είναι ο αλγόριθμος για τα συντομότερα μονοπάτια όταν κάθε ακμή μετρά εξίσου — δρομολόγηση, web crawling, βαθμοί διαχωρισμού σε κοινωνικά δίκτυα.
Η δομή της βασισμένη σε ουρά, επίπεδο-προς-επίπεδο είναι ένα θεμελιώδες μοτίβο διέλευσης.
Η γνώση BFS έναντι DFS σας επιτρέπει να επιλέξετε το σωστό εργαλείο για προβλήματα δυνατότητας πρόσβασης, μονοπατιών και ταξινόμησης.