Σε αυτό το σεμινάριο, θα μάθετε τι είναι ένας πίνακας γειτνίασης. Επίσης, θα βρείτε λειτουργικά παραδείγματα πλέγματος γειτνίασης σε C, C ++, Java και Python.
Ένας πίνακας γειτνίασης είναι ένας τρόπος αναπαράστασης ενός γραφήματος G = (V, E) ως μήτρα booleans.
Αναπαράσταση μήτρας προσαρμογής
Το μέγεθος της μήτρας είναι VxVπού Vείναι ο αριθμός κορυφών στο γράφημα και η τιμή μιας καταχώρησης Aijείναι είτε 1 είτε 0 ανάλογα με το αν υπάρχει ένα άκρο από την κορυφή i έως την κορυφή j.
Παράδειγμα Matjacency Matrix
Η παρακάτω εικόνα δείχνει ένα γράφημα και την αντίστοιχη μήτρα γειτνίασής του.
Πίνακας προσαρμογής από γράφημα
Σε περίπτωση μη κατευθυνόμενων γραφημάτων, η μήτρα είναι συμμετρική γύρω από τη διαγώνια, επειδή κάθε άκρη (i,j), υπάρχει επίσης ένα άκρο (j,i).
Πλεονεκτήματα της μήτρας γειτνίασης
Οι βασικές λειτουργίες όπως η προσθήκη ενός άκρου, η αφαίρεση ενός άκρου και ο έλεγχος εάν υπάρχει ένα άκρο από την κορυφή i έως την κορυφή j είναι εξαιρετικά αποδοτικές ως προς το χρόνο, συνεχείς λειτουργίες χρόνου.
Εάν το γράφημα είναι πυκνό και ο αριθμός των άκρων είναι μεγάλος, ο πίνακας γειτνίασης πρέπει να είναι η πρώτη επιλογή. Ακόμα κι αν το γράφημα και ο πίνακας γειτνίασης είναι αραιοί, μπορούμε να το αντιπροσωπεύσουμε χρησιμοποιώντας δομές δεδομένων για αραιές μήτρες.
Το μεγαλύτερο πλεονέκτημα, ωστόσο, προέρχεται από τη χρήση πινάκων. Οι πρόσφατες εξελίξεις στο υλικό μας επιτρέπουν να εκτελέσουμε ακόμη και ακριβές λειτουργίες matrix στην GPU.
Με την εκτέλεση λειτουργιών στον παρακείμενο πίνακα, μπορούμε να πάρουμε σημαντικές πληροφορίες για τη φύση του γραφήματος και τη σχέση μεταξύ των κορυφών του.
Μειονεκτήματα της μήτρας ερεθισμού
Η VxVαπαίτηση χώρου της μήτρας γειτνίασης το καθιστά γουρούνι μνήμης. Τα γραφήματα στο φυσικό περιβάλλον συνήθως δεν έχουν πάρα πολλές συνδέσεις και αυτός είναι ο κύριος λόγος για τον οποίο οι λίστες γειτνίασης είναι η καλύτερη επιλογή για τις περισσότερες εργασίες.
Ενώ οι βασικές λειτουργίες είναι εύκολες, οι λειτουργίες αρέσουν inEdgesκαι outEdgesείναι δαπανηρές κατά τη χρήση της αναπαράστασης μήτρας γειτνίασης.
Παραδείγματα Python, Java και C / C ++
Εάν ξέρετε πώς να δημιουργήσετε δισδιάστατους πίνακες, γνωρίζετε επίσης πώς να δημιουργήσετε έναν πίνακα προσάρτησης.
Python Java C C + # Adjacency Matrix representation in Python class Graph(object): # Initialize the matrix def __init__(self, size): self.adjMatrix = () for i in range(size): self.adjMatrix.append((0 for i in range(size))) self.size = size # Add edges def add_edge(self, v1, v2): if v1 == v2: print("Same vertex %d and %d" % (v1, v2)) self.adjMatrix(v1)(v2) = 1 self.adjMatrix(v2)(v1) = 1 # Remove edges def remove_edge(self, v1, v2): if self.adjMatrix(v1)(v2) == 0: print("No edge between %d and %d" % (v1, v2)) return self.adjMatrix(v1)(v2) = 0 self.adjMatrix(v2)(v1) = 0 def __len__(self): return self.size # Print the matrix def print_matrix(self): for row in self.adjMatrix: for val in row: print('(:4)'.format(val)), print def main(): g = Graph(5) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.print_matrix() if __name__ == '__main__': main()
// Adjacency Matrix representation in Java public class Graph ( private boolean adjMatrix()(); private int numVertices; // Initialize the matrix public Graph(int numVertices) ( this.numVertices = numVertices; adjMatrix = new boolean(numVertices)(numVertices); ) // Add edges public void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges public void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the matrix public String toString() ( StringBuilder s = new StringBuilder(); for (int i = 0; i < numVertices; i++) ( s.append(i + ": "); for (boolean j : adjMatrix(i)) ( s.append((j ? 1 : 0) + " "); ) s.append(""); ) return s.toString(); ) public static void main(String args()) ( Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); System.out.print(g.toString()); ) )
// Adjacency Matrix representation in C #include #define V 4 // Initialize the matrix to zero void init(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) for (j = 0; j < V; j++) arr(i)(j) = 0; ) // Add edges void addEdge(int arr()(V), int i, int j) ( arr(i)(j) = 1; arr(j)(i) = 1; ) // Print the matrix void printAdjMatrix(int arr()(V)) ( int i, j; for (i = 0; i < V; i++) ( printf("%d: ", i); for (j = 0; j < V; j++) ( printf("%d ", arr(i)(j)); ) printf(""); ) ) int main() ( int adjMatrix(V)(V); init(adjMatrix); addEdge(adjMatrix, 0, 1); addEdge(adjMatrix, 0, 2); addEdge(adjMatrix, 1, 2); addEdge(adjMatrix, 2, 0); addEdge(adjMatrix, 2, 3); printAdjMatrix(adjMatrix); return 0; )
// Adjacency Matrix representation in C++ #include using namespace std; class Graph ( private: bool** adjMatrix; int numVertices; public: // Initialize the matrix to zero Graph(int numVertices) ( this->numVertices = numVertices; adjMatrix = new bool*(numVertices); for (int i = 0; i < numVertices; i++) ( adjMatrix(i) = new bool(numVertices); for (int j = 0; j < numVertices; j++) adjMatrix(i)(j) = false; ) ) // Add edges void addEdge(int i, int j) ( adjMatrix(i)(j) = true; adjMatrix(j)(i) = true; ) // Remove edges void removeEdge(int i, int j) ( adjMatrix(i)(j) = false; adjMatrix(j)(i) = false; ) // Print the martix void toString() ( for (int i = 0; i < numVertices; i++) ( cout << i << " : "; for (int j = 0; j < numVertices; j++) cout << adjMatrix(i)(j) << " "; cout << ""; ) ) ~Graph() ( for (int i = 0; i < numVertices; i++) delete() adjMatrix(i); delete() adjMatrix; ) ); int main() ( Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.toString(); )
Εφαρμογές Matrix Adjacency
- Δημιουργία πίνακα δρομολόγησης σε δίκτυα
- Εργασίες πλοήγησης
