In diesem Tutorial erfahren Sie, was eine Adjazenzmatrix ist. Außerdem finden Sie Arbeitsbeispiele für die Adjazenzmatrix in C, C ++, Java und Python.
Eine Adjazenzmatrix ist eine Möglichkeit, einen Graphen G = (V, E) als Matrix von Booleschen Werten darzustellen.
Darstellung der Adjazenzmatrix
Die Größe der Matrix gibt an, VxVwo Vsich die Anzahl der Scheitelpunkte im Diagramm befindet und der Wert eines Eintrags Aijentweder 1 oder 0 ist, je nachdem, ob es eine Kante von Scheitelpunkt i zu Scheitelpunkt j gibt.
Beispiel für eine Adjazenzmatrix
Das Bild unten zeigt ein Diagramm und seine äquivalente Adjazenzmatrix.
Adjazenzmatrix aus einem Diagramm
Bei ungerichteten Graphen ist die Matrix wegen jeder Kante symmetrisch zur Diagonale (i,j), es gibt auch eine Kante (j,i).
Vorteile der Adjazenzmatrix
Die grundlegenden Operationen wie das Hinzufügen einer Kante, das Entfernen einer Kante und das Überprüfen, ob es eine Kante von Scheitelpunkt i zu Scheitelpunkt j gibt, sind äußerst zeiteffiziente Operationen mit konstanter Zeit.
Wenn der Graph dicht ist und die Anzahl der Kanten groß ist, sollte die Adjazenzmatrix die erste Wahl sein. Selbst wenn der Graph und die Adjazenzmatrix dünn sind, können wir sie mithilfe von Datenstrukturen für dünn besetzte Matrizen darstellen.
Der größte Vorteil ergibt sich jedoch aus der Verwendung von Matrizen. Die jüngsten Fortschritte bei der Hardware ermöglichen es uns, selbst teure Matrixoperationen auf der GPU durchzuführen.
Durch Ausführen von Operationen an der benachbarten Matrix können wir wichtige Einblicke in die Natur des Graphen und die Beziehung zwischen seinen Eckpunkten erhalten.
Nachteile der Adjazenzmatrix
Der VxVPlatzbedarf der Adjazenzmatrix macht sie zu einem Speicherfresser. Grafiken in freier Wildbahn haben normalerweise nicht zu viele Verbindungen, und dies ist der Hauptgrund, warum Adjazenzlisten für die meisten Aufgaben die bessere Wahl sind.
Während grundlegende Operationen einfach sind, mögen inEdgesund outEdgessind Operationen teuer, wenn die Adjazenzmatrixdarstellung verwendet wird.
Beispiele für Python, Java und C / C ++
Wenn Sie wissen, wie zweidimensionale Arrays erstellt werden, können Sie auch eine Adjazenzmatrix erstellen.
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(); )
Adjacency Matrix-Anwendungen
- Routing-Tabelle in Netzwerken erstellen
- Navigationsaufgaben
