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

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

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

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

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

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

ο Οδηγός Khan Academy για την αναπαράσταση γραφημάτων

instagram viewer
είναι μια εξαιρετική πηγή για να μάθετε πώς να αναπαριστάτε ένα γράφημα.

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

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

  1. Κατευθυνόμενο γράφημα: Ένα γράφημα στο οποίο όλες οι ακμές έχουν κατεύθυνση, που αναφέρεται επίσης ως δίφθογγος.
  2. Μη κατευθυνόμενο γράφημα: Ένα μη κατευθυνόμενο γράφημα είναι επίσης γνωστό ως γράφημα διπλής κατεύθυνσης. Στα μη κατευθυνόμενα γραφήματα, η κατεύθυνση των ακμών δεν έχει σημασία και η διέλευση μπορεί να πάει προς οποιαδήποτε κατεύθυνση.
  3. Σταθμισμένο γράφημα: Ένα σταθμισμένο γράφημα είναι ένα γράφημα του οποίου οι κόμβοι και οι ακμές έχουν μια σχετική τιμή. Στις περισσότερες περιπτώσεις, αυτή η τιμή αντιπροσωπεύει το κόστος της εξερεύνησης αυτού του κόμβου ή του άκρου.
  4. Πεπερασμένο γράφημα: Ένα γράφημα που έχει έναν πεπερασμένο αριθμό κόμβων και ακμών.
  5. Άπειρο γράφημα: Ένα γράφημα που έχει άπειρο αριθμό κόμβων και ακμών.
  6. Ασήμαντο γράφημα: Ένα γράφημα που έχει μόνο έναν κόμβο και καμία άκρη.
  7. Απλό γράφημα: Όταν μόνο μια ακμή συνδέει κάθε ζεύγος κόμβων ενός γραφήματος, ονομάζεται απλό γράφημα.
  8. Μηδενικό γράφημα: Ένα μηδενικό γράφημα είναι ένα γράφημα που δεν έχει ακμές που να συνδέουν τους κόμβους του.
  9. Πολυγραφώ στον πολύγραφο: Σε ένα πολύγραφο, τουλάχιστον ένα ζεύγος κόμβων έχει περισσότερες από μία ακμές που τους συνδέουν. Στα πολυγραφήματα, δεν υπάρχουν αυτο-βρόχοι.
  10. Πλήρες γράφημα: Ένα πλήρες γράφημα είναι ένα γράφημα στο οποίο κάθε κόμβος συνδέεται με κάθε άλλο κόμβο του γραφήματος. Είναι επίσης γνωστό ως α πλήρες γράφημα.
  11. Ψευδογραφική παράσταση: Ένα γράφημα που έχει έναν αυτο-βρόχο εκτός από άλλες ακμές γραφήματος ονομάζεται ψευδογράφημα.
  12. Κανονικό γράφημα: Ένα κανονικό γράφημα είναι ένα γράφημα όπου όλοι οι κόμβοι έχουν ίσους βαθμούς. δηλ. κάθε κόμβος έχει τον ίδιο αριθμό γειτόνων.
  13. Συνδεδεμένο γράφημα: Ένα συνδεδεμένο γράφημα είναι απλώς οποιοδήποτε γράφημα στο οποίο συνδέονται δύο κόμβοι. δηλαδή ένα γράφημα με τουλάχιστον ένα μονοπάτι ανάμεσα σε κάθε δύο κόμβους του γραφήματος.
  14. Αποσυνδεδεμένο γράφημα: Ένα αποσυνδεδεμένο γράφημα είναι το ακριβώς αντίθετο ενός συνδεδεμένου γραφήματος. Σε ένα αποσυνδεδεμένο γράφημα, δεν υπάρχουν άκρες που να συνδέουν τους κόμβους του γραφήματος, όπως σε ένα μηδενικό γραφική παράσταση.
  15. Κυκλικό γράφημα: Ένα κυκλικό γράφημα είναι ένα γράφημα που περιέχει τουλάχιστον έναν κύκλο γραφήματος (μια διαδρομή που τελειώνει εκεί που ξεκίνησε).
  16. Ακυκλικό γράφημα: Ένα άκυκλο γράφημα είναι ένα γράφημα χωρίς καθόλου κύκλους. Μπορεί να είναι είτε σκηνοθετημένο είτε μη.
  17. Υπογράφημα: Ένα υπογράφημα είναι ένα παράγωγο γράφημα. Είναι ένα γράφημα που σχηματίζεται από κόμβους και ακμές που είναι υποσύνολα ενός άλλου γραφήματος.

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

Αλγόριθμοι διέλευσης γραφήματος

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

  1. Breadth-First Search (BFS): Η αναζήτηση πρώτα σε πλάτος είναι ένας αλγόριθμος διέλευσης γραφήματος που επισκέπτεται έναν κόμβο γραφήματος και εξερευνά τους γείτονές του πριν προχωρήσει σε οποιονδήποτε από τους θυγατρικούς του κόμβους. Αν και μπορείτε να ξεκινήσετε τη διέλευση ενός γραφήματος από οποιονδήποτε επιλεγμένο κόμβο, το ριζικός κόμβος είναι συνήθως το προτιμώμενο σημείο εκκίνησης.
  2. Αναζήτηση σε βάθος (DFS): Αυτός είναι ο δεύτερος σημαντικός αλγόριθμος διέλευσης γραφήματος. Επισκέπτεται έναν κόμβο γραφήματος και εξερευνά τους θυγατρικούς κόμβους ή τους κλάδους του προτού προχωρήσει στον επόμενο κόμβο—δηλαδή, πηγαίνει βαθιά πρώτα πριν πάει ευρύ.

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

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

Μια απλή απεικόνιση μπορεί να βοηθήσει στην καλύτερη κατανόηση και των δύο αλγορίθμων. Σκεφτείτε τις καταστάσεις μιας χώρας ως γράφημα και προσπαθήστε να ελέγξετε αν δύο καταστάσεις, Χ και Υ, είναι συνδεδεμένα. Μια αναζήτηση σε βάθος μπορεί να προχωρήσει σε μια διαδρομή σχεδόν σε όλη τη χώρα χωρίς να το συνειδητοποιήσετε αρκετά νωρίς Υ απέχει μόλις 2 πολιτείες από Χ.

Το πλεονέκτημα μιας αναζήτησης κατά πλάτος είναι ότι διατηρεί όσο το δυνατόν πιο κοντά στον τρέχοντα κόμβο πριν πάει στον επόμενο. Θα βρει τη σύνδεση μεταξύ Χ και Υ σε σύντομο χρονικό διάστημα χωρίς να χρειαστεί να εξερευνήσετε ολόκληρη τη χώρα.

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

Ακολουθεί κάποιος ψευδοκώδικας που δείχνει την υλοποίηση και των δύο αλγορίθμων.

Πλάτος-Πρώτη Αναζήτηση

bfs (Γράφημα G, ρίζα GraphNode) {
αφήνω q είναι νέος Ουρά
// επισήμανση ρίζας ως επίσκεψης
 ρίζα.επισκέφθηκε = αληθής


// προσθήκη root στην ουρά
q.ουρά(ρίζα)
ενώ (q δεν είναι αδειάζω) {
αφήνω τρέχον είναι q.dequeue() // αφαιρέστε το μπροστινό στοιχείο στην ουρά
 για (γείτονες n του ρεύματος στο G) {
αν (ν είναιδεν ακόμη επισκεφθείτε) {
// προσθήκη στην ουρά - ώστε να μπορείτε να εξερευνήσετε και τους γείτονές του
q.ουρά(n)
 ν.επισκέφθηκε = αληθής
 }
 }
 }
}

Βάθος-Πρώτο Αναζήτηση

dfs (Γράφημα G, ρίζα GraphNode) {
// βασικό σενάριο
αν (ρίζα είναι μηδενικό) ΕΠΙΣΤΡΟΦΗ
// επισήμανση ρίζας ως επίσκεψης
 ρίζα.επισκέφθηκε = αληθής
για (γείτονες n της ρίζας στο G)
αν (ν είναιδεν έχει ακόμη επισκεφθεί)
 dfs (G, n) // αναδρομική κλήση
}

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

  • Αμφίδρομη αναζήτηση: Αυτός ο αλγόριθμος είναι ένας βελτιστοποιημένος τρόπος εύρεσης της συντομότερης διαδρομής μεταξύ δύο κόμβων. Χρησιμοποιεί δύο αναζητήσεις πλάτους που συγκρούονται εάν υπάρχει μονοπάτι.
  • Τοπολογική ταξινόμηση: Αυτό χρησιμοποιείται σε κατευθυνόμενα γραφήματα για να ταξινομήσετε τους κόμβους με την επιθυμητή σειρά. Δεν μπορείτε να εφαρμόσετε μια τοπολογική ταξινόμηση σε μη κατευθυνόμενα γραφήματα ή γραφήματα με κύκλους.
  • Ο αλγόριθμος του Dijkstra: Είναι επίσης ένας τύπος BFS. Χρησιμοποιείται επίσης για την εύρεση της συντομότερης διαδρομής μεταξύ δύο κόμβων στο a σταθμισμένο κατευθυνόμενο γράφημα, που μπορεί να έχει κύκλους ή όχι.

Συνήθεις ερωτήσεις συνέντευξης με βάση γραφήματα

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

Αυτά είναι μόνο μερικά από τα πολλά δημοφιλή προβλήματα συνέντευξης που βασίζονται σε γραφήματα. Μπορείτε να τα δοκιμάσετε LeetCode, HackerRank, ή GeeksforGeeks.

Κατανόηση Δομών Δεδομένων Γραφημάτων και Αλγορίθμων

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

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