Μελέτη αλγορίθμων εύρεσης ελαχίστων ζευγνυόντων δέντρων

Abstract

Tο πρόβλημα εύρεσης ελαχίστων ζευγνυόντων δέντρων αποτελεί ένα από τα πιο βασικά επιστημονικά προβλήματα με σημαντικές εφαρμογές στη σχεδίαση και βελτιστοποίηση δικτύων. Το εν λόγω πρόβλημα έχει αποτελέσει αντικείμενο έρευνας και μελέτης πολλών επιστημόνων με αποτέλεσμα την ανάπτυξη πολλών αποδοτικών αλγορίθμων πολυωνυμικού χρόνου. Στόχος της εν λόγω διπλωματικής εργασίας είναι η παρουσίαση των σημαντικότερων από αυτούς τους αλγορίθμους, δίνοντας γραφικά παραδείγματα για την επεξήγηση τους, αλλά και παρουσίαση ψευδοκώδικα για την εκτέλεση καθένα από αυτούς. Επίσης, γίνεται υλοποίηση των αλγορίθμων Kruskal, Dijkstra και Prim με χρήση της γλώσσας C αλλά και Pascal. Ακόμα αναπτύχθηκαν αλγόριθμοι χειρισμού γράφων στην γλώσσα προγραμματισμού C και εξετάστηκαν γράφοι με 4, 5 και 6 κόμβους.