graph implementation c using adjacency list
Αυτό το σεμινάριο εξηγεί την εφαρμογή γραφημάτων στο C ++. Θα μάθετε επίσης για διαφορετικούς τύπους, παραστάσεις και εφαρμογές γραφημάτων:
Ένα γράφημα είναι μια μη γραμμική δομή δεδομένων. Ένα γράφημα μπορεί να οριστεί ως μια συλλογή κόμβων που ονομάζονται επίσης «κορυφές» και «ακμές» που συνδέουν δύο ή περισσότερες κορυφές.
Ένα γράφημα μπορεί επίσης να θεωρηθεί ως ένα κυκλικό δέντρο όπου οι κορυφές δεν έχουν σχέση γονέα-παιδιού αλλά διατηρούν μια περίπλοκη σχέση μεταξύ τους.
πώς να ελέγξετε τη συμβατότητα μεταξύ προγραμμάτων περιήγησης
=> Κάντε κλικ εδώ για την σειρά απόλυτης προπόνησης C ++.
Τι θα μάθετε:
Τι είναι ένα γράφημα στο C ++;
Όπως αναφέρθηκε παραπάνω, ένα γράφημα στο C ++ είναι μια μη γραμμική δομή δεδομένων που ορίζεται ως μια συλλογή κορυφών και ακμών.
Ακολουθεί ένα παράδειγμα δομής δεδομένων γραφήματος.
Δίνεται παραπάνω ένα παράδειγμα γραφήματος G. Το γράφημα G είναι ένα σύνολο κορυφών {A, B, C, D, E} και ένα σύνολο ακμών {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Τύποι γραφημάτων - Κατευθυνόμενο και μη κατευθυνόμενο γράφημα
Ένα γράφημα στο οποίο οι άκρες δεν έχουν κατευθύνσεις ονομάζεται γράφημα undirected. Το γράφημα που φαίνεται παραπάνω είναι ένα μη κατευθυνόμενο γράφημα.
Ένα γράφημα στο οποίο τα άκρα έχουν κατευθύνσεις που σχετίζονται με αυτό ονομάζεται κατευθυνόμενο γράφημα.
Δίνεται παρακάτω ένα παράδειγμα κατευθυνόμενου γραφήματος.
Στο κατευθυνόμενο γράφημα που φαίνεται παραπάνω, τα άκρα σχηματίζουν ένα ταξινομημένο ζεύγος όπου κάθε άκρο αντιπροσωπεύει μια συγκεκριμένη διαδρομή από τη μία κορυφή στην άλλη κορυφή. Η κορυφή από την οποία ξεκινά η διαδρομή ονομάζεται ' Αρχικός κόμβος 'Ενώ η κορυφή στην οποία τερματίζεται η διαδρομή ονομάζεται' Τερματικός κόμβος '.
Έτσι στο παραπάνω γράφημα, το σύνολο κορυφών είναι {A, B, C, D, E} και το σύνολο ακμών είναι {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Θα συζητήσουμε την ορολογία του γραφήματος ή τους κοινούς όρους που χρησιμοποιούνται σε σχέση με το παρακάτω γράφημα.
Ορολογία γραφήματος
- Κορυφή: Κάθε κόμβος του γραφήματος ονομάζεται κορυφή. Στο παραπάνω γράφημα, τα A, B, C και D είναι οι κορυφές του γραφήματος.
- Ακρη: Ο σύνδεσμος ή η διαδρομή μεταξύ δύο κορυφών ονομάζεται άκρη. Συνδέει δύο ή περισσότερες κορυφές. Τα διαφορετικά άκρα στο παραπάνω γράφημα είναι AB, BC, AD και DC.
- Δίπλα στον κόμβο: Σε ένα γράφημα, εάν δύο κόμβοι συνδέονται από ένα άκρο, τότε καλούνται γειτονικοί κόμβοι ή γείτονες. Στο παραπάνω γράφημα, οι κορυφές Α και Β συνδέονται από την άκρη ΑΒ. Έτσι τα Α και Β είναι γειτονικοί κόμβοι.
- Βαθμός του κόμβου: Ο αριθμός των άκρων που συνδέονται με έναν συγκεκριμένο κόμβο ονομάζεται βαθμός του κόμβου. Στο παραπάνω γράφημα, ο κόμβος Α έχει βαθμό 2.
- Μονοπάτι: Η ακολουθία των κόμβων που πρέπει να ακολουθήσουμε όταν πρέπει να ταξιδέψουμε από τη μία κορυφή στην άλλη σε ένα γράφημα ονομάζεται διαδρομή. Στο παράδειγμά μας, αν χρειαστεί να πάμε από τον κόμβο A έως C, τότε η διαδρομή θα ήταν A-> B-> C.
- Κλειστή διαδρομή: Εάν ο αρχικός κόμβος είναι ο ίδιος με έναν τερματικό κόμβο, τότε αυτή η διαδρομή ονομάζεται κλειστή διαδρομή.
- Απλή διαδρομή: Μια κλειστή διαδρομή στην οποία διακρίνονται όλοι οι άλλοι κόμβοι ονομάζεται απλή διαδρομή.
- Κύκλος: Μια διαδρομή στην οποία δεν υπάρχουν επαναλαμβανόμενες ακμές ή κορυφές και οι πρώτες και τελευταίες κορυφές είναι ίδιες ονομάζεται κύκλος. Στο παραπάνω γράφημα, A-> B-> C-> D-> A είναι ένας κύκλος.
- Συνδεδεμένο γράφημα: Ένα συνδεδεμένο γράφημα είναι αυτό στο οποίο υπάρχει μια διαδρομή μεταξύ καθεμίας από τις κορυφές. Αυτό σημαίνει ότι δεν υπάρχει ούτε μία κορυφή που να είναι απομονωμένη ή χωρίς συνδετικό άκρο. Το γράφημα που φαίνεται παραπάνω είναι ένα συνδεδεμένο γράφημα.
- Πλήρες γράφημα: Ένα γράφημα στο οποίο κάθε κόμβος συνδέεται με έναν άλλο ονομάζεται πλήρες γράφημα. Εάν N είναι ο συνολικός αριθμός κόμβων σε ένα γράφημα, τότε το πλήρες γράφημα περιέχει N (N-1) / 2 αριθμό ακμών.
- Σταθμισμένο γράφημα: Μια θετική τιμή που αποδίδεται σε κάθε άκρη που δείχνει το μήκος της (απόσταση μεταξύ των κορυφών που συνδέονται με ένα άκρο) ονομάζεται βάρος. Το γράφημα που περιέχει σταθμισμένες άκρες ονομάζεται σταθμισμένο γράφημα. Το βάρος ενός άκρου e δηλώνεται με το w (e) και υποδηλώνει το κόστος της διέλευσης ενός άκρου.
- Διάγραμμα: Ένα διάγραμμα είναι ένα γράφημα στο οποίο κάθε άκρο σχετίζεται με μια συγκεκριμένη κατεύθυνση και η διέλευση μπορεί να γίνει μόνο σε καθορισμένη κατεύθυνση.
Αναπαράσταση γραφήματος
Ο τρόπος με τον οποίο αποθηκεύεται η δομή δεδομένων γραφημάτων στη μνήμη ονομάζεται «αναπαράσταση». Το γράφημα μπορεί να αποθηκευτεί ως διαδοχική αναπαράσταση ή ως συνδεδεμένη αναπαράσταση.
Και οι δύο αυτοί τύποι περιγράφονται παρακάτω.
Διαδοχική αναπαράσταση
Στη διαδοχική αναπαράσταση γραφημάτων, χρησιμοποιούμε τον πίνακα γειτνίασης. Ένας πίνακας γειτνίασης είναι ένας πίνακας μεγέθους n x n όπου n είναι ο αριθμός κορυφών στο γράφημα.
Οι σειρές και οι στήλες της μήτρας γειτνίασης αντιπροσωπεύουν τις κορυφές σε ένα γράφημα. Το στοιχείο μήτρας ρυθμίζεται στο 1 όταν υπάρχει ένα άκρο μεταξύ των κορυφών. Εάν το άκρο δεν υπάρχει, τότε το στοιχείο είναι 0.
Δίνεται παρακάτω ένα παράδειγμα γραφήματος που δείχνει τον πίνακα γειτνίασης.
Έχουμε δει τον πίνακα γειτνίασης με το παραπάνω γράφημα. Σημειώστε ότι επειδή πρόκειται για ένα μη κατευθυνόμενο γράφημα, και μπορούμε να πούμε ότι το άκρο υπάρχει και στις δύο κατευθύνσεις. Για παράδειγμα, Καθώς υπάρχει το άκρο ΑΒ, μπορούμε να συμπεράνουμε ότι το άκρο ΒΑ είναι επίσης παρόν.
Στη μήτρα γειτνίασης, μπορούμε να δούμε τις αλληλεπιδράσεις των κορυφών που είναι στοιχεία μήτρας που τίθενται στο 1 όποτε υπάρχει το άκρο και στο 0 όταν το άκρο απουσιάζει.
Τώρα ας δούμε τη μήτρα γειτονίας ενός κατευθυνόμενου γραφήματος.
Όπως φαίνεται παραπάνω, το στοιχείο τομής στη μήτρα γειτονίας θα είναι 1 εάν και μόνο εάν υπάρχει ένα άκρο που κατευθύνεται από τη μία κορυφή στην άλλη.
Στο παραπάνω γράφημα, έχουμε δύο άκρα από την κορυφή Α. Το ένα άκρο καταλήγει στην κορυφή Β, ενώ το δεύτερο τερματίζει στην κορυφή Γ. Έτσι, στη μήτρα γειτονίας, η τομή του Α & Β ορίζεται στο 1 ως η τομή του Α & C.
Στη συνέχεια, θα δούμε τη διαδοχική αναπαράσταση για το σταθμισμένο γράφημα.
Δίνεται παρακάτω το σταθμισμένο γράφημα και ο αντίστοιχος πίνακας γειτνίασης.
Μπορούμε να δούμε ότι η διαδοχική αναπαράσταση ενός σταθμισμένου γραφήματος είναι διαφορετική από τους άλλους τύπους γραφημάτων. Εδώ, οι μη μηδενικές τιμές στη μήτρα γειτονίας αντικαθίστανται από το πραγματικό βάρος της ακμής.
Το άκρο AB έχει βάρος = 4, επομένως στη μήτρα γειτνίασης, ρυθμίζουμε τη διασταύρωση των Α και Β σε 4. Ομοίως, όλες οι άλλες μη μηδενικές τιμές αλλάζουν στα αντίστοιχα βάρη τους.
Η λίστα γειτνίασης είναι πιο εύκολο να εφαρμοστεί και να ακολουθηθεί. Η διέλευση δηλ. Για να ελέγξετε αν υπάρχει άκρη από τη μία κορυφή στην άλλη χρειάζεται χρόνο O (1) και για την αφαίρεση της άκρης απαιτείται επίσης O (1).
Είτε το γράφημα είναι αραιό (λιγότερα άκρα) είτε πυκνό, χρειάζεται πάντα περισσότερο χώρο.
Συνδεδεμένη αναπαράσταση
Χρησιμοποιούμε τη λίστα γειτνίασης για τη συνδεδεμένη αναπαράσταση του γραφήματος. Η αναπαράσταση λίστας γειτνίασης διατηρεί κάθε κόμβο του γραφήματος και έναν σύνδεσμο προς τους κόμβους που γειτνιάζουν με αυτόν τον κόμβο. Όταν διασχίζουμε όλους τους γειτονικούς κόμβους, ορίζουμε τον επόμενο δείκτη στο μηδέν στο τέλος της λίστας.
Ας εξετάσουμε πρώτα ένα μη κατευθυνόμενο γράφημα και τον κατάλογό του.
Όπως φαίνεται παραπάνω, έχουμε μια συνδεδεμένη λίστα (λίστα γειτνίασης) για κάθε κόμβο. Από την κορυφή Α, έχουμε άκρα στις κορυφές B, C και D. Έτσι, αυτοί οι κόμβοι συνδέονται με τον κόμβο A στην αντίστοιχη λίστα γειτνίασης.
Στη συνέχεια, κατασκευάζουμε μια λίστα γειτνίασης με το κατευθυνόμενο γράφημα.
Στο παραπάνω γράφημα, βλέπουμε ότι δεν υπάρχουν άκρα που προέρχονται από την κορυφή Ε. Ως εκ τούτου, η λίστα γειτνίασης με την κορυφή Ε είναι κενή.
Τώρα ας κατασκευάσουμε τη λίστα γειτνίασης με το σταθμισμένο γράφημα.
ποιο πρόγραμμα θα ανοίξει ένα αρχείο eps
Για ένα σταθμισμένο γράφημα, προσθέτουμε ένα επιπλέον πεδίο στον κόμβο λίστας γειτνίασης για να δηλώσουμε το βάρος της άκρης όπως φαίνεται παραπάνω.
Η προσθήκη κορυφής στη λίστα γειτνίασης είναι ευκολότερη. Εξοικονομεί επίσης χώρο λόγω της υλοποίησης της συνδεδεμένης λίστας. Όταν πρέπει να μάθουμε εάν υπάρχει ένα άκρο μεταξύ μιας κορυφής στην άλλη, η λειτουργία δεν είναι αποτελεσματική.
Βασικές λειτουργίες για γραφήματα
Ακολουθούν οι βασικές λειτουργίες που μπορούμε να εκτελέσουμε στη δομή δεδομένων γραφημάτων:
- Προσθήκη κορυφής: Προσθέτει κορυφή στο γράφημα.
- Προσθέστε ένα άκρο: Προσθέτει ένα άκρο μεταξύ των δύο κορυφών ενός γραφήματος.
- Εμφάνιση των κορυφών γραφήματος: Εμφάνιση των κορυφών ενός γραφήματος.
Υλοποίηση γραφήματος C ++ με χρήση λίστας προσαρμογής
Τώρα παρουσιάζουμε μια εφαρμογή C ++ για να δείξουμε ένα απλό γράφημα χρησιμοποιώντας τη λίστα γειτνίασης.
Εδώ πρόκειται να εμφανίσουμε τη λίστα γειτνίασης με ένα σταθμισμένο γράφημα. Έχουμε χρησιμοποιήσει δύο δομές για να κρατήσουμε τη λίστα γειτνίασης και τα άκρα του γραφήματος. Η λίστα γειτνίασης εμφανίζεται ως (start_vertex, end_vertex, weight).
Το πρόγραμμα C ++ έχει ως εξής:
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i Παραγωγή:
Παραγωγή:
Λίστα γειτνίασης γραφήματος
(start_vertex, end_vertex, βάρος):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Εφαρμογές γραφημάτων
Ας συζητήσουμε μερικές από τις εφαρμογές των γραφημάτων.
- Τα γραφήματα χρησιμοποιούνται εκτενώς στην επιστήμη των υπολογιστών για να απεικονίσουν γραφήματα δικτύου, ή σημασιολογικά γραφήματα ή ακόμη και για να απεικονίσουν τη ροή του υπολογισμού.
- Τα γραφήματα χρησιμοποιούνται ευρέως στους μεταγλωττιστές για να απεικονίσουν την κατανομή πόρων σε διεργασίες ή για να δείξουν ανάλυση ροής δεδομένων κ.λπ.
- Τα γραφήματα χρησιμοποιούνται επίσης για βελτιστοποίηση ερωτημάτων σε γλώσσες βάσεων δεδομένων σε ορισμένους εξειδικευμένους μεταγλωττιστές.
- Σε ιστότοπους κοινωνικής δικτύωσης, τα γραφήματα είναι οι κύριες δομές για την απεικόνιση του δικτύου ανθρώπων.
- Τα γραφήματα χρησιμοποιούνται εκτενώς για την κατασκευή του συστήματος μεταφοράς, ιδίως του οδικού δικτύου. Ένα δημοφιλές παράδειγμα είναι οι χάρτες Google που χρησιμοποιούν εκτενώς γραφήματα για να υποδείξουν οδηγίες σε όλο τον κόσμο.
συμπέρασμα
Ένα γράφημα είναι μια δημοφιλής και ευρέως χρησιμοποιούμενη δομή δεδομένων που έχει πολλές εφαρμογές στον ίδιο τον τομέα της επιστήμης των υπολογιστών εκτός από άλλα πεδία. Τα γραφήματα αποτελούνται από κορυφές και άκρα που συνδέουν δύο ή περισσότερες κορυφές.
Ένα γράφημα μπορεί να κατευθύνεται ή να μη κατευθύνεται. Μπορούμε να αντιπροσωπεύσουμε γραφήματα χρησιμοποιώντας πίνακας παρακέντησης που είναι μια γραμμική αναπαράσταση καθώς και χρησιμοποιώντας μια λίστα συνδεδεμένων με γειτνίαση. Συζητήσαμε επίσης την εφαρμογή του γραφήματος σε αυτό το σεμινάριο.
=> Δείτε εδώ για να εξερευνήσετε την πλήρη λίστα μαθημάτων C ++.
Συνιστώμενη ανάγνωση
- Εκμάθηση Python Advanced List (Ταξινόμηση λίστας, Αντίστροφη, Ευρετήριο, Αντιγραφή, Συμμετοχή, Άθροισμα)
- Λίστα Python - Δημιουργία, πρόσβαση, φέτα, προσθήκη ή διαγραφή στοιχείων
- Προεπιλεγμένη λίστα διευθύνσεων IP δρομολογητή για κοινές μάρκες ασύρματου δρομολογητή
- 12 καλύτερα εργαλεία δημιουργίας γραφημάτων γραμμών για τη δημιουργία εκπληκτικών γραφημάτων γραμμών (2021 RANKINGS)
- Προεπιλεγμένος κωδικός πρόσβασης σύνδεσης δρομολογητή για κορυφαία μοντέλα δρομολογητών (λίστα 2021)
- Δομή δεδομένων συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Δομή δεδομένων κυκλικής συνδεδεμένης λίστας σε C ++ με απεικόνιση
- Διπλά συνδεδεμένη δομή δεδομένων λίστας σε C ++ με απεικόνιση
