Οδηγός για τη δομή δεδομένων γραφήματος

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

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

ΚΑΤΑΣΚΕΥΗ ΒΙΝΤΕΟ ΤΗΣ ΗΜΕΡΑΣ

Τι είναι ένα γράφημα και τι πρέπει να γνωρίζετε για αυτό;

Τι είναι ένα γράφημα;

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

Αν και μπορείς δημιουργία δομών δεδομένων σε JavaScript και άλλες γλώσσες, μπορείτε να εφαρμόσετε ένα γράφημα με διάφορους τρόπους. Οι πιο δημοφιλείς προσεγγίσεις είναι λίστες άκρων , λίστες γειτνίασης , και πίνακες γειτνίασης .

ο Οδηγός Khan Academy για την αναπαράσταση γραφημάτων είναι μια εξαιρετική πηγή για να μάθετε πώς να αναπαριστάτε ένα γράφημα.

Υπάρχουν πολλοί διαφορετικοί τύποι γραφημάτων. Μια κοινή διάκριση είναι μεταξύ σκηνοθετημένος και χωρίς διεύθυνσιν γραφικές παραστάσεις; αυτά εμφανίζονται πολύ σε προκλήσεις κωδικοποίησης και πραγματικές χρήσεις.

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

Κατευθυνόμενο γράφημα: Ένα γράφημα στο οποίο όλες οι ακμές έχουν κατεύθυνση, που αναφέρεται επίσης ως δίφθογγος.
Μη κατευθυνόμενο γράφημα: Ένα μη κατευθυνόμενο γράφημα είναι επίσης γνωστό ως γράφημα διπλής κατεύθυνσης. Στα μη κατευθυνόμενα γραφήματα, η κατεύθυνση των ακμών δεν έχει σημασία και η διέλευση μπορεί να πάει προς οποιαδήποτε κατεύθυνση.
Σταθμισμένο γράφημα: Ένα σταθμισμένο γράφημα είναι ένα γράφημα του οποίου οι κόμβοι και οι ακμές έχουν μια σχετική τιμή. Στις περισσότερες περιπτώσεις, αυτή η τιμή αντιπροσωπεύει το κόστος της εξερεύνησης αυτού του κόμβου ή του άκρου.
Πεπερασμένο γράφημα: Ένα γράφημα που έχει έναν πεπερασμένο αριθμό κόμβων και ακμών.
Άπειρο γράφημα: Ένα γράφημα που έχει άπειρο αριθμό κόμβων και ακμών.
Ασήμαντο γράφημα: Ένα γράφημα που έχει μόνο έναν κόμβο και καμία άκρη.
Απλό γράφημα: Όταν μόνο μια ακμή συνδέει κάθε ζεύγος κόμβων ενός γραφήματος, ονομάζεται απλό γράφημα.
Μηδενικό γράφημα: Ένα μηδενικό γράφημα είναι ένα γράφημα που δεν έχει ακμές που να συνδέουν τους κόμβους του.
Πολυγραφώ στον πολύγραφο: Σε ένα πολύγραφο, τουλάχιστον ένα ζεύγος κόμβων έχει περισσότερες από μία ακμές που τους συνδέουν. Στα πολυγραφήματα, δεν υπάρχουν αυτο-βρόχοι.
Πλήρες γράφημα: Ένα πλήρες γράφημα είναι ένα γράφημα στο οποίο κάθε κόμβος συνδέεται με κάθε άλλο κόμβο του γραφήματος. Είναι επίσης γνωστό ως α πλήρες γράφημα .
Ψευδογραφική παράσταση: Ένα γράφημα που έχει έναν αυτο-βρόχο εκτός από άλλες ακμές γραφήματος ονομάζεται ψευδογράφημα.
Κανονικό γράφημα: Ένα κανονικό γράφημα είναι ένα γράφημα όπου όλοι οι κόμβοι έχουν ίσους βαθμούς. δηλ. κάθε κόμβος έχει τον ίδιο αριθμό γειτόνων.
Συνδεδεμένο γράφημα: Ένα συνδεδεμένο γράφημα είναι απλώς οποιοδήποτε γράφημα στο οποίο συνδέονται δύο κόμβοι. δηλαδή ένα γράφημα με τουλάχιστον ένα μονοπάτι ανάμεσα σε κάθε δύο κόμβους του γραφήματος.
Αποσυνδεδεμένο γράφημα: Ένα αποσυνδεδεμένο γράφημα είναι το ακριβώς αντίθετο ενός συνδεδεμένου γραφήματος. Σε ένα αποσυνδεδεμένο γράφημα, δεν υπάρχουν άκρες που να συνδέουν τους κόμβους του γραφήματος, όπως σε ένα μηδενικό γραφική παράσταση.
Κυκλικό γράφημα: Ένα κυκλικό γράφημα είναι ένα γράφημα που περιέχει τουλάχιστον έναν κύκλο γραφήματος (μια διαδρομή που τελειώνει εκεί που ξεκίνησε).
Ακυκλικό γράφημα: Ένα άκυκλο γράφημα είναι ένα γράφημα χωρίς καθόλου κύκλους. Μπορεί να είναι είτε σκηνοθετημένο είτε μη.
Υπογράφημα: Ένα υπογράφημα είναι ένα παράγωγο γράφημα. Είναι ένα γράφημα που σχηματίζεται από κόμβους και ακμές που είναι υποσύνολα ενός άλλου γραφήματος.