Γράφημα (αφηρημένος τύπος δεδομένων)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

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

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

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