Λίστα γειτνίασης και αναπαράσταση μήτρας του γραφήματος

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

1. Πίνακας προσαρμογής
2. Λίστα ικανοτήτων

Λίστα ικανοτήτων

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

Ακολουθεί ένα παράδειγμα λίστας γειτνίασης:

Ας υποθέσουμε ότι ένα γράφημα περιέχει V αριθμό κορυφών και E αριθμό ακμών.

Γενικά, η πολυπλοκότητα του χώρου θα είναι O(V + E).

Η χειρότερη περίπτωση πολυπλοκότητας χώρου θα είναι O(V2) αν το δεδομένο Γράφημα είναι το πλήρες Γράφημα

Πίνακας προσαρμογής

Ο πίνακας γειτνίασης αποτελείται από έναν πίνακα 2D. Γράφημα που έχει V αριθμό κορυφών, το μέγεθος του πίνακα θα είναι VxV.

Λένε, matrix[i][j] = 5. Σημαίνει ότι υπάρχει μια άκρη μεταξύ των κόμβων i και j όπου το βάρος είναι 5.

Ας δούμε το παρακάτω γράφημα και τον πίνακα γειτνίασής του:

Δημιουργήσαμε το Τρισδιάστατος πίνακας χρησιμοποιώντας αυτά τα βήματα:

Βήμα 1) Η κορυφή Α έχει άμεση ακμή με το Β και το βάρος είναι 5. Άρα, το κελί στη σειρά Α και στη στήλη Β θα γεμίσει με 5. Τα υπόλοιπα κελιά στη σειρά Α θα γεμίσουν με μηδέν.

Βήμα 2) Οι κορυφές Β έχουν άμεση ακμή με το C και το βάρος τους είναι 4. Έτσι, το κελί στη σειρά Β και στη στήλη Γ θα γεμίσει με 4. Τα υπόλοιπα κελιά στη σειρά Β θα γεμίσουν με μηδέν, καθώς το Β δεν έχει εξερχόμενη ακμή σε κανένα άλλους κόμβους.

Βήμα 3) Οι κορυφές C δεν έχουν άμεσες ακμές με άλλες κορυφές. Έτσι, η σειρά Γ θα γεμίσει με μηδενικά.

Βήμα 4) Η κορυφή Δ έχει κατευθυνόμενη άκρη με τα Α και Γ.

• Εδώ, το κελί της γραμμής D και της στήλης A θα έχει τιμή 7. Τα κελιά στη γραμμή D και τη στήλη C θα έχουν τιμή 2.
• Τα υπόλοιπα κελιά στη σειρά D θα γεμίσουν με μηδενικά.

Βήμα 5) Οι κορυφές Ε έχουν μια κατευθυνόμενη ακμή με το Β και το Δ. Το κελί στη σειρά Ε και τη στήλη Β θα έχουν τιμή 6. Τα κελιά στη σειρά Ε και στη στήλη D θα έχουν τιμή 3. Τα υπόλοιπα κελιά στη σειρά D θα είναι γεμάτο με μηδενικά.

Ακολουθούν ορισμένα σημεία που πρέπει να προσέξετε:

• Το γράφημα δεν έχει αυτο-βρόχους όταν η κύρια διαγώνιος του πίνακα γειτνίασης είναι 0.
• Το γράφημα είναι ένα κατευθυνόμενο γράφημα εάν οι δείκτες (a,b) και (b,a) δεν έχουν την ίδια τιμή. Διαφορετικά, το Γράφημα είναι ένα κατευθυνόμενο γράφημα.
• Το γράφημα θα είναι ένα σταθμισμένο γράφημα εάν η τιμή των κελιών είναι μεγαλύτερη από 1.

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

Για παράδειγμα, εάν έχουμε ένα γράφημα με 100 κόμβους, τότε χρειάζονται 10 χιλιάδες κελιά για να το αποθηκεύσουμε στο RAM. Με λιγότερες ακμές στο γράφημα, η εκχώρηση τόσο μεγάλης μνήμης μπορεί να είναι χαμένη. Έτσι, η πολυπλοκότητα του χώρου χρησιμοποιώντας τον πίνακα γειτνίασης θα είναι O(N2), όπου N σημαίνει τον αριθμό των κόμβων στο γράφημα.