L07 · Γραφήματα ΙΙ — Διάσχιση (BFS & DFS)

Τι θα δούμε

Από το L06 ξέρουμε τι είναι ένα γράφημα και πώς το αποθηκεύουμε (λίστα γειτνίασης). Ξέρουμε όμως μόνο να το περιγράφουμε — όχι να απαντάμε ερωτήσεις πάνω του:

• s-t συνεκτικότητα: υπάρχει διαδρομή από την κορυφή $s$ στην κορυφή $t$;
• s-t απόσταση: ποιο είναι το μήκος της συντομότερης διαδρομής από την $s$ στην $t$;

Αυτές οι δύο ερωτήσεις κρύβονται παντού: λύσιμο λαβυρίνθου, «έξι βαθμοί του Kevin Bacon», ελάχιστος αριθμός ενδιάμεσων κόμβων σε ένα δίκτυο. Για να τις απαντήσουμε χρειαζόμαστε διάσχιση — έναν συστηματικό τρόπο να επισκεφθούμε κάθε κορυφή. Θα δούμε τις δύο θεμελιώδεις τεχνικές:

1. DFS (Depth-First Search) — αναζήτηση κατά βάθος. Πας όσο πιο μακριά μπορείς, μετά γυρνάς πίσω και δοκιμάζεις άλλο δρόμο.
2. BFS (Breadth-First Search) — αναζήτηση κατά πλάτος. Εξερευνείς επίπεδα: πρώτα όλους τους γείτονες, μετά τους γείτονες των γειτόνων, κ.ο.κ.

Και οι δύο τρέχουν σε χρόνο $O(n+m)$ με λίστα γειτνίασης. Λύνουν την s-t συνεκτικότητα· επιπλέον ο BFS λύνει και την s-t απόσταση σε γραφήματα χωρίς βάρη.

Σε όλη τη διάλεξη δουλεύουμε πάνω στο ίδιο γράφημα — αυτό από το L06:

DFS — Αναζήτηση κατά βάθος

Η ιδέα

Φαντάσου ότι στέκεσαι στην κορυφή $s$ ενός λαβύρινθου. Διαλέγεις μία κατεύθυνση και προχωράς. Φτάνεις σε νέα κορυφή, διαλέγεις πάλι μία κατεύθυνση που δεν έχεις δοκιμάσει, προχωράς. Συνεχίζεις μέχρι να βρεθείς σε αδιέξοδο — μια κορυφή χωρίς νέους δρόμους. Τότε γυρνάς πίσω (backtrack) στην προηγούμενη κορυφή και δοκιμάζεις άλλη κατεύθυνση.

Ο αλγόριθμος

Μια πιο γενική ματιά. Στις σημειώσεις, ο DFS εμφανίζεται πρώτα σε μια ακόμη πιο απλή, γενική μορφή — τον λεγόμενο R-set algorithm. Κρατάμε ένα σύνολο $R$ από κορυφές που έχουμε «πιάσει», και όσο υπάρχει ακμή που βγαίνει έξω από το $R$, τραβάμε τη νέα κορυφή μέσα:

Τώρα γίνε εσύ ο αλγόριθμος. Σε κάθε βήμα διάλεξε όποιον μη-εξερευνημένο γείτονα θέλεις — ο DFS δουλεύει με κάθε επιλογή. Η στοίβα αναδρομής ενημερώνεται ζωντανά και κάνει backtrack μόνη της στα αδιέξοδα. (Με «Παρακολούθησε» τρέχει μόνο του.)

Το «κρυφό» αποτέλεσμα — το DFS-δέντρο

Όσο τρέχει η αναδρομή, σχηματίζει σιωπηλά ένα δέντρο. Κάθε φορά που κατεβαίνουμε από την $u$ σε νέα κορυφή $v$, η ακμή $\{u,v\}$ γίνεται ακμή του δέντρου. Οι υπόλοιπες ακμές του γραφήματος ονομάζονται οπίσθιες ακμές — και (στο μη-κατευθυνόμενο DFS) η καθεμιά τους κλείνει κύκλο πίσω σε πρόγονο της τρέχουσας κορυφής στο δέντρο.

Πάτα βήμα-βήμα κι άσε το DFS να ζωγραφίσει μόνο του τις δύο πλευρές — αριστερά η σάρωση πάνω στο G, δεξιά το δέντρο που γεννιέται· και δίπλα τους η ζωντανή στοίβα αναδρομής.

Γιατί μας ενδιαφέρει αυτή η διάκριση «δεντρική ακμή vs οπίσθια ακμή»; Στο L08 το ίδιο εργαλείο γίνεται ορισμός των strongly connected components σε κατευθυνόμενα γραφήματα, και στο L09 πιάνει τα ελάχιστα συνδετικά δέντρα. Μην κουραστείς να την αποστηθίζεις τώρα — απλώς πρόσεξε πως ο DFS γεννά δομή, δεν επισκέπτεται μόνο.

Κλείδωσέ το στο μυαλό σου

Πρώτα η συμπύκνωση — δεν αποστηθίζεις σελίδα, αποστηθίζεις μια κάρτα:

Τώρα η ανάκληση. Μην προχωρήσεις αν δεν τα κάνεις χωρίς να κοιτάς πίσω:

Πότε σκέφτεσαι DFS;

BFS — Αναζήτηση κατά πλάτος

Η ιδέα

Φαντάσου τώρα ότι ρίχνεις μια πέτρα στην κορυφή $s$ μιας λίμνης. Ένα κύμα εξαπλώνεται προς όλες τις κατευθύνσεις ταυτόχρονα. Σε χρόνο 1 το κύμα φτάνει στους άμεσους γείτονες της $s$. Σε χρόνο 2 στους γείτονες των γειτόνων. Και ούτω καθεξής.

Ο αλγόριθμος

Επίσημα, από την $s$ φτιάχνουμε επίπεδα:

• $L_0=\{s\}$ — μόνο η αφετηρία.
• $L_1$ = όλοι οι γείτονες του $L_0$.
• $L_{i+1}$ = όλες οι κορυφές που δεν ανήκουν σε προηγούμενο επίπεδο και έχουν ακμή προς κάποια κορυφή του $L_i$.

Πριν πάρεις το θεώρημα στα πιστά, διάλεξε εσύ μια κορυφή-στόχο και δες το να συμβαίνει. Στα αριστερά το BFS-«κύμα» απλώνεται επίπεδο-ανά-επίπεδο· στα δεξιά υπολογίζουμε αυτόνομα τη συντομότερη διαδρομή προς τον στόχο σου. Όταν το κύμα τον αγκαλιάσει, οι δύο αριθμοί συμπίπτουν: το επίπεδο εμφάνισης = η απόσταση. Δοκίμασε διαφορετικούς στόχους — η εξίσωση κρατάει.

Δες τα ίδια επίπεδα ως ενιαία εικόνα στο γράφημά μας — αυτή τη φορά με τις 7 ακμές του BFS-δέντρου ξεχωρισμένες:

Γίνε ο αλγόριθμος. Σε κάθε βήμα κάνε κλικ στην κορυφή που βρίσκεται στην αρχή της ουράς — η ουρά ενημερώνεται ζωντανά. (Σύμβαση: τους νέους γείτονες τους βάζουμε στην ουρά με αύξουσα σειρά, ώστε η σειρά να είναι προβλέψιμη.)

Από το παράδειγμα προκύπτουν τα επίπεδα $L_0=\{1\}$, $L_1=\{2,3\}$, $L_2=\{4,5,7,8\}$, $L_3=\{6\}$ — άρα οι αποστάσεις από την 1:

Δοκίμασέ τη με τα ίδια σου τα χέρια. Στην πρώτη καρτέλα σαρώνεις και τις 11 ακμές μία-μία — η μετρητής Δlevel ανεβαίνει σε δύο στήλες (Δ=1 για δεντρικές, Δ=0 για ίδιο-επίπεδο) και ΠΟΤΕ στη στήλη Δ≥2. Στη δεύτερη καρτέλα είσαι ο «αντίπαλος»: διαλέγεις δύο κορυφές και βλέπεις γιατί καμιά πραγματική ακμή δεν μπορεί να έχει Δ≥2 — αν υπήρχε, το BFS θα είχε χτυπήσει την πιο μακρινή κορυφή ένα επίπεδο νωρίτερα.

Κλείδωσέ το στο μυαλό σου

Πότε σκέφτεσαι BFS;

BFS vs DFS — δύο όψεις του ίδιου αλγορίθμου

Ο πίνακας δείχνει τις διαφορές. Αλλά το πιο σημαντικό είναι η ομοιότητα:

Δες το με τα μάτια σου: τρέξε τον ίδιο αλγόριθμο στο ίδιο γράφημα, και άλλαξε μόνο τη δομή δεδομένων. Στην FIFO καρτέλα η σειρά ανακάλυψης είναι $1,2,3,4,5,7,8,6$ (BFS). Στη LIFO γίνεται $1,2,3,5,4,6,7,8$ (DFS) — μακρύ μονοπάτι με backtracks. Στην «Ελεύθερη» καρτέλα εσύ διαλέγεις ποια κορυφή από το frontier θα τραβήξεις, σε όποια σειρά θες· κι όμως, στο τέλος, η ίδια οκτάδα κορυφών είναι μέσα.

Πολυπλοκότητα — γιατί O(n + m), όχι O(n²)

Και ο BFS και ο DFS τρέχουν σε χρόνο $O(n+m)$ με λίστα γειτνίασης — όταν μετράμε σωστά. Με τον λάθος τρόπο μέτρησης βγαίνει $O(n^2)$, που είναι μεν σωστός φραγμός, αλλά για αραιά γραφήματα είναι τάξη μεγέθους χειρότερος από την πραγματικότητα. Αξίζει να δούμε γιατί.

Πόση δουλειά κάνουμε ανά κορυφή; Ο αλγόριθμος, στον κύκλο του, βγάζει την κορυφή $u$ από τη δομή (FIFO ή LIFO) και σαρώνει τους γείτονές της για να διακρίνει ποιους έχει ήδη δει. Άρα η δουλειά για κάθε $u$ είναι:

Πόσοι είναι «οι γείτονες»; — δύο απαντήσεις:

• Χαλαρά: «το πολύ $n-1$» (δεν μπορεί να έχει περισσότερους από όλο το V). Συνολικά ${\sum }_u(1+n)=n+n^2=O(n^2)$. Σωστό φραγμός — αλλά κάθε κορυφή σπάνια ακουμπά σχεδόν όλο το γράφημα.
• Σφιχτά: οι γείτονες της $u$ είναι ακριβώς $\mathrm{deg}(u)$, ούτε μία παραπάνω. Συνολικά ${\sum }_u(1+\mathrm{deg}(u))=n+{\sum }_u\mathrm{deg}(u)$.

Και τώρα η κίνηση που σε γλιτώνει: το handshaking lemma του L06 λέει ${\sum }_u\mathrm{deg}(u)=2m$. Άρα η συνολική δουλειά είναι $n+2m$.

Σύρε τον κέρσορα στο πεδίο $m$ και δες τους δύο φραγμούς να τρέχουν παράλληλα. Για αραιό γράφημα το «αφελές» bar είναι ψηλό σαν τοίχος ενώ το «σφιχτό» μένει χαμηλό· για πυκνό σχεδόν συμπίπτουν. Η εμπειρία του «$\times 20$ καλύτερο» είναι το κίνητρο της σφιχτής ανάλυσης.

Πού κουμπώνει αυτή η διάλεξη

Με BFS και DFS στο χέρι, οι ερωτήσεις του L06 έχουν πλέον αλγοριθμικές απαντήσεις:

Και αυτά είναι μόνο η αρχή. Στο L08 ο DFS γίνεται τοπολογική ταξινόμηση και SCC, ενώ η ιδιότητα του BFS-δέντρου γίνεται έλεγχος διμερότητας. Στο L09 προσθέτουμε βάρη στις ακμές και το BFS εξελίσσεται σε Dijkstra.