Διάσχιση γράφων — αναζήτηση κατά πλάτος χωρίς ατέρμονους κύκλους

Συμβόλαιο

Ένας μικρός τοπικός γράφος εξαρτήσεων αποθηκεύει για κάθε κόμβο τους γείτονές του. Ζητάμε μία συντομότερη διαδρομή ως προς το πλήθος ακμών ανάμεσα σε δύο υπαρκτούς κόμβους. Όταν δεν υπάρχει διαδρομή επιστρέφεται None. Άγνωστοι κόμβοι ή αναφορές σε ανύπαρκτους γείτονες θεωρούνται λάθη. Η αναζήτηση κατά πλάτος επεξεργάζεται επίπεδα απόστασης και βρίσκει ελάχιστο πλήθος ακμών όταν δεν υπάρχουν βάρη. Για διαφορετικά βάρη χρειάζεται κατάλληλος αλγόριθμος, όπως ο Dijkstra.

Εκτελέσιμο εργαστήριο Python 3

Αποθήκευσε ως bfs_lab.py και εκτέλεσε python3 bfs_lab.py. Ο δοκιμαστικός γράφος περιλαμβάνει κύκλο, δύο ισομήκεις επιλογές και έναν απομονωμένο κόμβο. Η ταξινόμηση γειτόνων παρέχει σταθερή σειρά επιλογών.

from collections import deque

def shortest(graph, start, goal):
    if start not in graph or goal not in graph:
        raise ValueError("unknown node")
    pending = deque([(start, [start])])
    visited = {start}
    while pending:
        node, path = pending.popleft()
        if node == goal:
            return path
        for neighbor in sorted(graph[node]):
            if neighbor not in graph:
                raise ValueError("dangling neighbor")
            if neighbor not in visited:
                visited.add(neighbor)
                pending.append((neighbor, path + [neighbor]))
    return None

g = {"a":["c","b"],"b":["a","d"],"c":["a","d"],
     "d":["b","c"],"island":[]}
assert shortest(g,"a","d") == ["a","b","d"]
assert shortest(g,"a","island") is None
assert shortest(g,"a","a") == ["a"]
try:
    shortest(g,"ghost","a")
except ValueError:
    pass
else:
    raise AssertionError("unknown start accepted")
print("PASS: BFS shortest edges, cycles, no path")

Γιατί τερματίζει

Βάζουμε έναν κόμβο στο σύνολο visited όταν μπει στην ουρά, όχι όταν βγει. Έτσι αποφεύγουμε να προσθέτουμε τον ίδιο κόμβο ξανά από διαφορετικούς γονείς. Η ουρά FIFO επεξεργάζεται όλες τις διαδρομές k ακμών πριν από τις k+1. Μία κανονική διάσχιση κοστίζει O(V+E), αν η πρόσβαση στους γείτονες είναι ήδη έτοιμη. Στο συγκεκριμένο πρόγραμμα η ταξινόμηση των γειτόνων προσθέτει κόστος και η αντιγραφή ολόκληρης διαδρομής σε κάθε βήμα είναι ακριβή για μεγάλους γράφους. Σε μεγαλύτερο έργο αποθήκευσε μόνο τον προηγούμενο κόμβο και κατασκεύασε τη διαδρομή στο τέλος.

Ασκήσεις και διάγνωση

1. Πρόσθεσε ακμή από κόμβο προς τον εαυτό του και επαναλαμβανόμενους γείτονες. Η αναζήτηση πρέπει να τερματίζει.
2. Σύγκρινε απομονωμένο στόχο με ανύπαρκτο στόχο. Η πρώτη περίπτωση δίνει None και η δεύτερη ValueError.
3. Χρησιμοποίησε προσωρινά στοίβα LIFO αντί για ουρά και κατασκεύασε παράδειγμα όπου η πρώτη διαδρομή δεν είναι η συντομότερη.
4. Σε μη κατευθυνόμενο γράφο κάθε ακμή πρέπει να εμφανίζεται και αντίστροφα· εξήγησε γιατί δεν ισχύει αυτό σε κατευθυνόμενο γράφο.

Παραδοτέα: PASS, ίχνος ουράς και επισκέψεων, μία μη προσβάσιμη περιοχή και εξήγηση για βάρη και ισοπαλίες.