🌐 Γράφοι (Graphs)

Ένας γράφος (graph) είναι μία δυναμική δομή δεδομένων που αποτελείται από έναν σύνολο κόμβων και ένα σύνολο ακμών που συνδέουν τους κόμβους μεταξύ τους. Οι γράφοι είναι μία πιο γενική μορφή δεδομένων από τα δέντρα, αφού επιτρέπουν πιο πολύπλοκες συνδέσεις μεταξύ των στοιχείων.

Τι κάνει ένα δέντρο διαφορετικό από έναν γράφο; 🌳 vs 🌐

Ένα δέντρο έχει συγκεκριμένους περιορισμούς:

• Υπάρχει πάντα μία ρίζα από όπου ξεκινούν όλες οι ακμές.
• Κάθε κόμβος έχει μόνο έναν γονέα και συνδέεται προς μία κατεύθυνση (δηλ., από τη ρίζα προς τα φύλλα).
• Ένα δέντρο δεν έχει κυκλικές διαδρομές.

Από την άλλη, ένας γράφος είναι πιο ελεύθερος στη δομή του:

• Οι κόμβοι μπορούν να συνδέονται μεταξύ τους με πολλούς διαφορετικούς τρόπους, και δεν υπάρχει υποχρεωτικά μία ρίζα.
• Ένας κόμβος μπορεί να συνδεθεί με πολλούς άλλους, όπως φαίνεται στην Εικόνα 1.3.27.β, όπου ένας κόμβος έχει συνδέσεις με άλλους πέντε κόμβους ταυτόχρονα.

🛤️ Τύποι Γράφων

Υπάρχουν δύο βασικοί τύποι γράφων:

1. Κατευθυνόμενοι γράφοι (Directed Graphs): Οι ακμές έχουν μία κατεύθυνση, δηλαδή οι συνδέσεις μεταξύ των κόμβων έχουν αρχή και τέλος. Στην Εικόνα 1.3.28.α, ο κόμβος A συνδέεται μόνο με τον B και όχι το αντίστροφο.
2. Μη κατευθυνόμενοι γράφοι (Undirected Graphs): Οι ακμές δεν έχουν κατεύθυνση. Η σύνδεση μεταξύ δύο κόμβων είναι αμφίδρομη, όπως στην Εικόνα 1.3.28.β, όπου οι κόμβοι A και B συνδέονται και προς τις δύο κατευθύνσεις.

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