Δομές δεδομένων 101: Γραφήματα - Μια οπτική εισαγωγή για αρχάριους

Γνωρίστε τις δομές δεδομένων που χρησιμοποιείτε κάθε μέρα

? Καλώς ήλθατε! Ας ξεκινήσουμε με κάποιο ζωτικό περιβάλλον. Ασε με να σε ρωτήσω κάτι:

✅ Χρησιμοποιείτε την Αναζήτηση Google;

✅ Χρησιμοποιείτε τους Χάρτες Google;

✅ Χρησιμοποιείτε ιστότοπους κοινωνικών μέσων;

Εάν η απάντησή σας είναι «ναι» σε οποιαδήποτε από αυτές τις ερωτήσεις, τότε έχετε σίγουρα χρησιμοποιήσει γραφήματα και δεν το ήξερα καν! Εκπληκτος? ? Ήμουν κι εγώ! Αυτό το άρθρο θα σας δώσει μια οπτική εισαγωγή στον κόσμο των γραφημάτων, του σκοπού τους, των στοιχείων και των τύπων τους.

Αυτές οι δομές δεδομένων πραγματικά τράβηξαν την προσοχή μου λόγω των εκπληκτικών δυνατοτήτων τους. Είναι τόσο ισχυροί που δεν θα φανταστείτε καν πόσο διαφορετικές είναι οι πραγματικές εφαρμογές τους. Ας ξεκινήσουμε! ?

? Εφαρμογές πραγματικού κόσμου - Η μαγεία ξεκινά!

Τα γραφήματα χρησιμοποιούνται σε διάφορες βιομηχανίες και τομείς:

  • Τα συστήματα GPS και οι Χάρτες Google χρησιμοποιούν γραφήματα για να βρουν τη συντομότερη διαδρομή από τον ένα προορισμό στον άλλο.
  • Τα κοινωνικά δίκτυα χρησιμοποιούν γραφήματα για να αντιπροσωπεύουν συνδέσεις μεταξύ χρηστών.
  • Ο αλγόριθμος Αναζήτησης Google χρησιμοποιεί γραφήματα για να προσδιορίσει τη συνάφεια των αποτελεσμάτων αναζήτησης.
  • Η επιχειρησιακή έρευνα είναι ένα πεδίο που χρησιμοποιεί γραφήματα για να βρει τη βέλτιστη διαδρομή για τη μείωση του κόστους μεταφοράς και παράδοσης αγαθών και υπηρεσιών.
  • Ακόμη και η Χημεία χρησιμοποιεί γραφήματανα αντιπροσωπεύουν μόρια !!! ❤️

Οι εφαρμογές τους είναι καταπληκτικές, έτσι;

Ας ξεκινήσουμε το ταξίδι μας σε αυτόν τον κόσμο! ?

? Γνωρίστε γραφήματα!

Τώρα που έχετε κάποιο πλαίσιο, ας ξεκινήσουμε μιλώντας για τον κύριο σκοπό και τα στοιχεία τους.

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

Αυτό είναι ένα παράδειγμα του γραφήματος:

? Δομικά μπλοκ

Είμαι βέβαιος ότι παρατηρήσατε δύο κύρια στοιχεία στο παραπάνω διάγραμμα: κύκλους και παχιές γραμμές που τα συνδέουν. Καλούνται, αντίστοιχα, κόμβοι και άκρες .

Ας τα δούμε με περισσότερες λεπτομέρειες! ?

  • Κόμβοι: είναι τα στοιχεία που δημιουργούν το δίκτυο. Θα μπορούσαν να αντιπροσωπεύουν σπίτια, τοποθεσίες, αεροδρόμια, λιμάνια, στάσεις λεωφορείων, κτίρια, χρήστες, βασικά οτιδήποτε θα μπορούσατε να αντιπροσωπεύσετε ως συνδεδεμένα με άλλα παρόμοια στοιχεία ενός δικτύου.
  • Άκρες: είναι συνδέσεις μεταξύ των κόμβων. Θα μπορούσαν να αντιπροσωπεύουν δρόμους, πτήσεις, δρομολόγια λεωφορείων, μια σύνδεση μεταξύ δύο χρηστών σε ένα κοινωνικό δίκτυο ή οτιδήποτε θα μπορούσε ενδεχομένως να αντιπροσωπεύει μια σύνδεση μεταξύ των κόμβων στο πλαίσιο με το οποίο εργάζεστε.

? Τι θα συμβεί εάν δεν υπάρχει σύνδεση;

Εάν δύο κόμβοι δεν συνδέονται από ένα άκρο, αυτό σημαίνει ότι δεν υπάρχει άμεση σύνδεση μεταξύ τους. Αλλά μην πανικοβληθείτε! Might Ίσως να μπορείτε να μεταβείτε από τον ένα κόμβο στον άλλο, ακολουθώντας μια ακολουθία άκρων, παρόμοια με την οδήγηση σε αρκετούς δρόμους για να φτάσετε στον τελικό προορισμό σας. ?️ ? ?

Για παράδειγμα, στο παρακάτω διάγραμμα, παρόλο που δεν υπάρχει άμεση σύνδεση ( άκρη ) μεταξύ του μοβ κόμβου (αριστερά) και του κίτρινου κόμβου (δεξιά), μπορείτε να μεταβείτε από τον μωβ κόμβο στον πορτοκαλί κόμβο, στον ροζ κόμβο, στον πράσινο κόμβο και τελικά φτάστε στον κίτρινο κόμβο. ?

Αυτή είναι μια βασική πτυχή των γραφημάτων, όπου μπορείτε να αναζητήσετε το στοιχείο που ψάχνετε ακολουθώντας τις διαθέσιμες διαδρομές.

? Σημειογραφία & Ορολογία

Είναι πολύ σημαντικό να μάθετε την επίσημη «γλώσσα» για να εργαστείτε με γραφήματα:

  • |V|= Συνολικός αριθμός κορυφών ( κόμβοι ) στο γράφημα.
  • |E|= Συνολικός αριθμός συνδέσεων ( άκρα ) στο γράφημα.

Στο παρακάτω παράδειγμα, |V| = 6επειδή υπάρχουν έξι κόμβοι (κύκλοι) και

|E| = 7γιατί υπάρχουν επτά άκρα (γραμμές).

? Τύποι γραφημάτων

Τα γραφήματα ταξινομούνται με βάση τα χαρακτηριστικά των άκρων τους (συνδέσεις). Ας ρίξουμε μια ματιά σε αυτά με λεπτομέρεια! ?

1️⃣ Κατευθυνόμενα γραφήματα

Σε κατευθυνόμενα γραφήματα, τα άκρα έχουν κατεύθυνση. Πηγαίνουν από τον έναν κόμβο στον άλλο και δεν υπάρχει τρόπος να επιστρέψετε στον αρχικό κόμβο μέσω αυτής της άκρης.

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

? Για παράδειγμα, εάν δημιουργήσουμε ένα γράφημα για μια υπηρεσία παράδοσης πίτσας, που αντιπροσωπεύει μια πόλη, δύο σπίτια (κόμβοι) μπορεί να συνδέονται με έναν μονόδρομο (άκρη). Θα μπορούσατε να φτάσετε από το σπίτι Α στο σπίτι Β μέσω αυτού του δρόμου, αλλά δεν θα μπορούσατε να επιστρέψετε, οπότε θα πρέπει να ακολουθήσετε μια εναλλακτική διαδρομή.

? Σημείωση: Σε ένα κατευθυνόμενο γράφημα, ενδέχεται να μην μπορείτε να επιστρέψετε καθόλου στην αρχική σας θέση, εάν δεν υπάρχει διαδρομή με τις κατάλληλες οδηγίες. Below Στο παρακάτω διάγραμμα, μπορείτε να δείτε ότι μπορείτε να μεταβείτε με επιτυχία από τον μωβ κόμβο στον πράσινο κόμβο, αλλά παρατηρήστε ότι δεν υπάρχει τρόπος να επιστρέψετε από τον πράσινο κόμβο στον μωβ κόμβο, επειδή οι άκρες είναι «μονόδρομοι». "

2️⃣ Μη κατευθυνόμενα γραφήματα

Σε αυτόν τον τύπο γραφήματος, τα άκρα είναι μη κατευθυνόμενα (δεν έχουν συγκεκριμένη κατεύθυνση). Σκεφτείτε τα μη κατευθυνόμενα άκρα ως αμφίδρομους δρόμους. Μπορείτε να μεταβείτε από έναν κόμβο στον άλλο και να επιστρέψετε στην ίδια «διαδρομή».

? Σημείωση: Όταν βλέπετε ένα διάγραμμα ενός γραφήματος όπου τα άκρα δεν έχουν βέλη που δείχνουν προς μια συγκεκριμένη κατεύθυνση, μπορείτε να υποθέσετε ότι το γράφημα είναι μη κατευθυνόμενο.

? Για την υπηρεσία παράδοσης πίτσας, αυτό θα σήμαινε ότι η μοτοσικλέτα παράδοσης μπορεί να πάει από την πηγή στον προορισμό μέσω του ίδιου δρόμου ή μονοπατιού (προς ανακούφιση τους! ?).

Στο παρακάτω γράφημα, θα μπορούσατε να μεταβείτε από τον μωβ κόμβο στον πράσινο κόμβο και να επιστρέψετε στην ίδια διαδρομή , ώστε να μην φτάσετε σε σημείο χωρίς επιστροφή. ?

? Βάρη; - Ναι, βάρη!

1️⃣ Σταθμισμένα γραφήματα

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

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

Αυτά τα βάρη χρησιμοποιούνται από τον Αλγόριθμο της Dijkstra για τη βελτιστοποίηση των διαδρομών με την εύρεση των συντομότερων ή λιγότερο δαπανηρών διαδρομών μεταξύ κόμβων σε ένα δίκτυο. (Μείνετε συντονισμένοι για ένα άρθρο σχετικά με τον Αλγόριθμο της Dijkstra! ?).

2️⃣ Μη σταθμισμένα γραφήματα

Αντίθετα, τα μη σταθμισμένα γραφήματα δεν έχουν βάρη που σχετίζονται με τις άκρες τους. Ένα παράδειγμα αυτού του τύπου γραφήματος μπορεί να βρεθεί σε κοινωνικά δίκτυα, όπου τα άκρα αντιπροσωπεύουν τη σύνδεση μεταξύ δύο χρηστών. Δεν είναι δυνατή η ποσοτικοποίηση της σύνδεσης. Επομένως, το άκρο δεν έχει βάρος.

? Σημείωση: Μπορεί να έχετε παρατηρήσει ότι, μέχρι στιγμής, τα γραφήματά μας έχουν μόνο ένα άκρο που συνδέει κάθε ζεύγος κόμβων. Είναι φυσικό να ρωτάς αν θα μπορούσαν να υπάρχουν περισσότερα από ένα άκρα μεταξύ ενός ζεύγους κόμβων. Μια ctually, αυτό είναι εφικτό με Μ ultigraphs! T hey μπορεί να έχει πολλαπλές ακμές που συνδέουν το ίδιο ζεύγος κόμβων.

? Αριθμός άκρων! - Ένας σημαντικός παράγοντας

Είναι πολύ σημαντικό να γνωρίζετε εάν ένα γράφημα έχει πολλές ή λίγες ακμές, διότι αυτός είναι ένας κρίσιμος παράγοντας για να αποφασίσετε πώς θα αντιπροσωπεύσετε αυτήν τη δομή δεδομένων στον κώδικα σας. Ας δούμε τους διαφορετικούς τύπους! ?

1️⃣ Πυκνά γραφήματα

Τα πυκνά γραφήματα έχουν πολλές άκρες. Αλλά περίμενε! ⚠️ Ξέρω τι πρέπει να σκέφτεστε, πώς μπορείτε να προσδιορίσετε τι χαρακτηρίζεται ως "πολλές άκρες"; Αυτό είναι λίγο υποκειμενικό, σωστά; ? Συμφωνώ μαζί σας, οπότε ας το ποσοτικοποιήσουμε λίγο:

? Ας βρούμε τον μέγιστο αριθμό ακμών σε ένα κατευθυνόμενο γράφημα. Εάν υπάρχουν |V|κόμβοι σε κατευθυνόμενο γράφημα (στο παρακάτω παράδειγμα, έξι κόμβοι), αυτό σημαίνει ότι κάθε κόμβος μπορεί να έχει έως και |v|συνδέσεις (στο παρακάτω παράδειγμα, έξι συνδέσεις).

Γιατί; Επειδή κάθε κόμβος θα μπορούσε ενδεχομένως να συνδεθεί με όλους τους άλλους κόμβους και με τον ίδιο (βλ. «Βρόχος» παρακάτω) . Επομένως, ο μέγιστος αριθμός ακμών που μπορεί να έχει το γράφημα|V|*|V| είναι ο συνολικός αριθμός κόμβων πολλαπλασιασμένος με τον μέγιστο αριθμό συνδέσεων που μπορεί να έχει κάθε κόμβος.

Όταν ο αριθμός των άκρων στο γράφημα είναι κοντά στον μέγιστο αριθμό ακμών, το γράφημα είναι πυκνό. ?

? Σημείωση: Οι «βρόχοι» εμφανίζονται όταν ένας κόμβος έχει ένα άκρο που τον συνδέει με τον εαυτό του. Παράξενο και ενδιαφέρον, σωστά; ?

2️⃣ Αραιά γραφήματα

Τα αραιά γραφήματα έχουν λίγα άκρα. Όπως μπορείτε να δείτε στο παρακάτω διάγραμμα, δεν υπάρχουν πολλές συνδέσεις μεταξύ των κόμβων.

Όταν ο αριθμός των άκρων στο γράφημα είναι σημαντικά μικρότερος από τον μέγιστο αριθμό ακμών, το γράφημα είναι αραιό. ?

⭕️ Γνωρίστε τους κύκλους!

Ας δούμε τώρα μια ζωτική ιδέα για την κατανόηση γραφημάτων, κύκλων

Ίσως παρατηρήσατε ότι εάν ακολουθήσετε μια ακολουθία συνδέσεων σε ένα γράφημα, ενδέχεται να βρείτε μια διαδρομή που θα σας οδηγήσει πίσω στον ίδιο κόμβο. Αυτό μοιάζει με «περπάτημα σε κύκλους», ακριβώς σαν να οδηγούσατε γύρω από την πόλη σας και πήρατε ένα μονοπάτι που θα μπορούσε να σας οδηγήσει πίσω στην αρχική σας τοποθεσία.

Στα γραφήματα, αυτές οι "κυκλικές" διαδρομές ονομάζονται "κύκλοι". Είναι έγκυρες διαδρομές που ξεκινούν και τελειώνουν στον ίδιο κόμβο. Για παράδειγμα, στο παρακάτω διάγραμμα, μπορείτε να δείτε ότι εάν ξεκινήσετε σε οποιονδήποτε κόμβο, μπορείτε να επιστρέψετε στον ίδιο κόμβο ακολουθώντας τις άκρες.

Οι κύκλοι δεν είναι πάντα «απομονωμένοι» επειδή μπορούν να είναι μέρος ενός μεγαλύτερου γραφήματος. Μπορείτε να τα εντοπίσετε ξεκινώντας την αναζήτησή σας σε έναν συγκεκριμένο κόμβο και βρείτε μια διαδρομή που θα σας οδηγήσει πίσω στον ίδιο κόμβο.

Summary Συνοπτικά…

  • Τα γραφήματα είναι καταπληκτικές δομές δεδομένων που χρησιμοποιείτε καθημερινά μέσω της Αναζήτησης Google, των Χαρτών Google, του GPS και των κοινωνικών μέσων.
  • Χρησιμοποιούνται για την αναπαράσταση στοιχείων που μοιράζονται συνδέσεις .
  • Τα στοιχεία στο γράφημα ονομάζονται Κόμβοι και οι συνδέσεις μεταξύ τους ονομάζονται Άκρες .
  • Τα γραφήματα μπορούν να κατευθύνονται, όταν τα άκρα τους έχουν συγκεκριμένο προσανατολισμό, παρόμοιο με μονόδρομους ή μη κατευθυνόμενα, όταν τα άκρα τους δεν έχουν συγκεκριμένο προσανατολισμό, παρόμοιο με αμφίδρομο δρόμο.
  • Οι άκρες μπορούν να έχουν μια τιμή που να σχετίζεται με αυτό, που ονομάζεται βάρος .
  • Εάν ένα γράφημα έχει πολλές άκρες, ονομάζεται πυκνό γράφημα. Διαφορετικά, εάν έχει λίγα άκρα, ονομάζεται αραιό γράφημα.
  • Μια σειρά συνδέσεων μπορεί να σχηματίσει έναν κύκλο εάν δημιουργήσει μια διαδρομή που σας επιτρέπει να επιστρέψετε στον ίδιο κόμβο.

Συνεχίστε να μαθαίνετε για αυτές τις καταπληκτικές δομές δεδομένων! Θα αξίζει τον κόπο για το μέλλον σας ως προγραμματιστής. Μαθαίνω για τις δομές δεδομένων αυτή τη στιγμή και τις βρίσκω εντελώς συναρπαστικές. ? ? ❤️

Το σημαντικό είναι να μην σταματήσετε να αναρωτιέστε. Η περιέργεια έχει τον δικό της λόγο για υπάρχουσα. - Albert Einstein

? Ευχαριστώ!

Ελπίζω πραγματικά ότι σας άρεσε το άρθρο μου. ❤️

Ακολουθησε μεΚελάδημα. ?