Αλγόριθμοι: DFS, BFS, Dijkstra, Prim, Kruskal, Bellman-Ford

Περιεχόμενα: Αλγόριθμοι σε γράφους

Κεφ. 1 · Διάσχιση κατά βάθος (DFS)4 ενότητες

• 3.1 Η ιδέα και ο αλγόριθμος
• 3.2 Τρεξίματα του DFS
• 3.3 Είδη ακμών
• 3.4 Τα ρολογάκια: pre και post

Κεφ. 2 · Διάσχιση κατά πλάτος (BFS)5 ενότητες

• 4.1 Κύματα σε λίμνη: επίπεδο-επίπεδο
• 4.2 Η ουρά και ο αλγόριθμος
• 4.3 Συντομότερα μονοπάτια χωρίς βάρη
• 4.4 Εφαρμογή: εκκεντρότητα και διάμετρος
• 4.5 Εφαρμογή: διμερότητα

Κεφ. 3 · Βεβαρυμένα γραφήματα2 ενότητες

• 5.1 Βάρη και μήκος μονοπατιού
• 5.2 Πώς αποθηκεύω τα βάρη

Κεφ. 4 · Ελάχιστα συνδετικά δέντρα8 ενότητες

• 6.1 Ορισμός και βασικές ιδιότητες
• 6.2 Ο αλγόριθμος του Prim
• 6.3 Ο αλγόριθμος του Kruskal
• 6.4 Παρατηρήσεις
• 6.5 Γιατί δουλεύουν ο Prim και ο Kruskal
• 6.6 Δύο κλασικά παραδείγματα
• 6.7 Ασκήσεις
• 6.8 Ενδεικτικά θέματα

Κεφ. 5 · Ο αλγόριθμος του Dijkstra9 ενότητες

• 7.1 Γιατί θέλω κάτι καλύτερο
• 7.2 Από τον BFS στον Dijkstra: τα ξυπνητήρια
• 7.3 Χαλάρωση ακμής
• 7.4 Η ιδέα: προσωρινές και μόνιμες ετικέτες
• 7.5 Ένα ολόκληρο τρέξιμο
• 7.6 Εντοπισμός των μονοπατιών
• 7.7 Ο αλγόριθμος σε ψευδοκώδικα
• 7.8 Εφαρμογή: κοινός προορισμός
• 7.9 Εξάσκηση

Κεφ. 6 · Ο αλγόριθμος Bellman-Ford10 ενότητες

• 8.1 Η ιδέα: χαλαρώνω όλες τις ακμές, ξανά και ξανά
• 8.2 Ο αλγόριθμος σε ψευδοκώδικα
• 8.3 Τρέξιμο φάση-φάση
• 8.4 Το σημαντικό: μετά τον k-οστό γύρο
• 8.5 Εφαρμογή: εντοπίζω τον αρνητικό κύκλο
• 8.6 Κύκλοι μηδενικού βάρους
• 8.7 Εφαρμογή: νομίσματα και arbitrage
• 8.8 Το πολύ μία αρνητική ακμή
• 8.9 Ενδεικτικά θέματα
• 8.10 Ασκήσεις για λύση