Graph Data Structure Demystified – Μοναδική Ανάπτυξη Λογισμικού

Χρησιμοποιούμε τακτικά την αναζήτηση Google, τους χάρτες google και τα κοινωνικά δίκτυα στις μέρες μας. Ένα από τα κοινά πράγματα που έχουν όλοι είναι το γεγονός ότι χρησιμοποιούν μια αξιοσημείωτη δομή δεδομένων – γραφήματα κάτω από την κουκούλα για την οργάνωση και τον χειρισμό δεδομένων. Μπορεί να έχετε δει αυτή τη δομή δεδομένων στο κολέγιο, αλλά δεν θυμάστε πολλά για αυτήν. Ή ίσως είναι ένα τρομακτικό θέμα που αποφεύγετε όλη την ώρα. Είτε έτσι είτε αλλιώς, τώρα είναι μια εξαιρετική στιγμή για να το εξοικειωθείτε. Σε αυτό το ιστολόγιο, θα καλύψουμε τις περισσότερες από τις έννοιες και θα πρέπει να είστε άνετοι να προχωρήσετε στην εργασία με αλγόριθμους που σχετίζονται με γραφήματα.

Περίγραμμα

1. Ορισμός
2. Ορολογία
3. Παραστάσεις
4. Αλγόριθμοι γραφημάτων

Ορισμός

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

Αγνοήστε την κόκκινη πινελιά γύρω από το πλαίσιο Δέντρα. Υποτίθεται ότι ήταν γύρω από το πλαίσιο Graphs. 😅

Τυχαίο γράφημα

Υπάρχουν δύο κύρια στοιχεία οποιουδήποτε γραφήματος: Κόμβοι και Ακρα.

Οι κόμβοι συνήθως καλούνται Κορυφές (ενικός: κορυφή), και μπορούν να αντιπροσωπεύουν οποιαδήποτε δεδομένα: ακέραιους αριθμούς, συμβολοσειρές, άτομα, τοποθεσίες, κτίρια κ.λπ.

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

Γραφική ορολογία

Υπάρχει πολύ λεξιλόγιο που πρέπει να θυμάστε σχετικά με γραφήματα. Θα απαριθμήσουμε τα πιο συνηθισμένα.

Μη κατευθυνόμενα και κατευθυνόμενα γραφήματα

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

Σταθμισμένα και μη σταθμισμένα γραφήματα

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

Κυκλικά και άκυκλα γραφήματα

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

Αναπαράσταση γραφημάτων στη μνήμη

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

Λίστα άκρων

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

const graph = [['A', 'B'], ['A', 'E'], ['C', 'B'], ['C', 'E'], ['C', 'D']];

Οι άκρες αναφέρονται μόνο μία φορά στη λίστα. Δεν χρειάζεται να δηλώνουμε Α και Βκαι επίσης Β και Α. Επιπλέον, η σειρά των άκρων στη λίστα δεν έχει σημασία.

Παρόμοια με τη λίστα των ακμών, θα μπορούσαμε επίσης να αποθηκεύσουμε τους κόμβους ως λίστα. Αλλά αυτό δεν είναι αυτό που είναι η αναπαράσταση της Λίστας άκρων.

Λίστα γειτνίασης

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

const graph = [
	['B', 'E'],
	['A', 'C'],
	['B', 'D', 'E'],
	['C'],
	['A', 'C']
]

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

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

const graph = {
	'A': ['B', 'E'],
	'B': ['A', 'C'],
	'C': ['B', 'D', 'E'],
	'D': ['C'],
	'E': ['A', 'C']
}

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

Πίνακας γειτνίασης

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

const graph = [
	[0, 1, 0, 0, 1],
	[1, 0, 1, 0, 1],
	[0, 1, 0, 1, 1],
	[0, 0, 1, 0, 0],
	[1, 0, 1, 0, 0]
]

Σε αυτήν την περίπτωση, η σειρά των κόμβων στη λίστα έχει σημασία.

Αλγόριθμοι γραφημάτων

BFS και DFS

Υπάρχουν δύο κύριοι αλγόριθμοι γραφημάτων που πρέπει οπωσδήποτε να γνωρίζουμε όταν πρόκειται για γραφήματα:

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

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

Breadth-First Traversal
Ο αλγόριθμος BFS διασχίζει ένα γράφημα επισκεπτόμενος τους γειτονικούς κόμβους αντί να κατέβει στους θυγατρικούς κόμβους. Και χρησιμοποιεί α δομή δεδομένων ουράς για να παρακολουθείτε τις επισκέψεις κορυφές.

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

Υπάρχουν τρία βασικά βήματα που ακολουθούν αυτοί οι αλγόριθμοι:

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

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

Το DFS ακολουθεί αυτά τα βήματα για να διασχίσει ένα γράφημα:

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

Στην υγειά σας!