BFS — επίπεδα γράφου και συντομότερη απόσταση σε ακμές

Python 3 reference program

from collections import deque
def bfs(graph, start):
    seen, order, queue = {start}, [], deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, ()):
            if neighbor not in seen:
                seen.add(neighbor); queue.append(neighbor)
    return order
assert bfs({'a':['b','c'], 'b':['d']}, 'a') == ['a','b','c','d']

Ιδιότητα της ουράς

Η αναζήτηση κατά πλάτος αφαιρεί πρώτα την παλαιότερη ανακαλυφθείσα κορυφή. Η deque δίνει γρήγορο append/popleft. Βάζουμε έναν γείτονα στο seen όταν προστίθεται στην ουρά, ώστε δύο γονείς να μη δημιουργούν διπλές εργασίες.

Τι εγγυάται

Σε adjacency list η διάσχιση κοστίζει O(V+E) χρόνο και O(V) χώρο για ουρά/seen. Σε γράφο χωρίς βάρη η BFS βρίσκει αποστάσεις με ελάχιστο αριθμό ακμών. Η λίστα του παραδείγματος περιέχει σειρά επίσκεψης, όχι το ίδιο το shortest path· για ανακατασκευή αποθήκευσε parent όταν πρωτοβρίσκεται ο κόμβος.

Ελεγχόμενα παραδείγματα

1. Για a→b,c και b→d η σειρά αναμένεται a,b,c,d, επειδή b,c περιμένουν στην ουρά πριν το d.
2. Πρόσθεσε ακμή d→a. Το seen εμποδίζει ατέρμονα επανάληψη σε κύκλο.
3. Ξεκίνα από x που δεν είναι κλειδί του dict. Η υλοποίηση δίνει ['x'] επειδή απουσία adjacency σημαίνει κενή ακολουθία.
4. Πρόσθεσε ανεξάρτητο z. Ξεκινώντας από a, η BFS δεν επισκέπτεται αποσυνδεδεμένο κόμβο.
5. Άλλαξε τη σειρά των γειτόνων του a. Μπορεί να αλλάξει σειρά επίσκεψης, όχι οι ελάχιστες αποστάσεις σε ακμές.

Επέκταση

Επέστρεψε πίνακες distance και parent και έλεγξε ότι το μονοπάτι έως d έχει δύο ακμές. Σύγκρινε με Dijkstra μόνο όταν όλα τα βάρη είναι ένα. Δήλωσε αν η σειρά των γειτόνων καθορίζει την επιλογή ανάμεσα σε ισοδύναμα μονοπάτια.

06 bfs — έλεγχος ορίων

Η αναζήτηση BFS επισκέπτεται κόμβους με αύξοντα αριθμό ακμών από την αρχή. Σε μη σταθμισμένο γράφο η πρώτη επίσκεψη δίνει συντομότερη διαδρομή σε ακμές. Σήμανε κόμβο ως seen όταν τον προσθέτεις στην ουρά.

Απομονωμένος κόμβος έξω από το αρχικό συνδεδεμένο τμήμα δεν εμφανίζεται. Δοκίμασε κύκλο a→b→a ώστε να βεβαιωθείς ότι τερματίζει.

<!-- [curated-algorithm-detail:06_bfs.md] -->

BFS πολλών αφετηριών και σήμανση κατά την εισαγωγή

Η BFS μπορεί να ξεκινήσει από πολλές αφετηρίες με απόσταση μηδέν. Η πρώτη ανακάλυψη κορυφής δίνει το ελάχιστο πλήθος ακμών από οποιαδήποτε αφετηρία σε μη σταθμισμένο γράφο. Σημείωσέ την όταν μπαίνει στην ουρά, όχι όταν αφαιρείται, ώστε πολλοί πρόγονοι να μην την προσθέτουν επανειλημμένα.

Η τεχνική μοντελοποιεί κοντινότερες εξόδους, απόσταση από επιλεγμένες υπηρεσίες και διάδοση μετώπου. Δεν χειρίζεται διαφορετικά κόστη ακμών. Απουσία κορυφής από τον χάρτη σημαίνει μη προσβασιμότητα και όχι απόσταση μηδέν.

from collections import deque
graph = {0:[1], 1:[0,2], 2:[1,3], 3:[2], 4:[]}
sources = [0,3]
distance = dict.fromkeys(sources, 0)
queue = deque(distance)
while queue:
    node = queue.popleft()
    for nxt in graph[node]:
        if nxt not in distance:
            distance[nxt] = distance[node] + 1
            queue.append(nxt)
assert distance == {0:0, 3:0, 1:1, 2:1}
assert 4 not in distance
print(distance)

Πρόσθεσε διπλές αφετηρίες, αυτοβρόχο, αποσυνδεδεμένο τμήμα και ίσα συντομότερα μονοπάτια. Η επιλογή γονέα εξαρτάται από τη σειρά διάσχισης· μη διεκδικείς μοναδική διαδρομή χωρίς κανόνα ισοπαλίας.

Τεχνική αναφορά