In deze tutorial leer je wat een aangrenzende matrix is. Ook vindt u werkende voorbeelden van aangrenzende matrix in C, C ++, Java en Python.
Een aangrenzende matrix is een manier om een grafiek G = (V, E) weer te geven als een matrix van booleans.
Nabijheid matrix representatie
De grootte van de matrix is VxVwaar Vis het aantal hoekpunten in de grafiek en de waarde van een invoer Aijis 1 of 0, afhankelijk van of er een rand is van hoekpunt i tot hoekpunt j.
Voorbeeld van een aangrenzende matrix
De onderstaande afbeelding toont een grafiek en de equivalente aangrenzende matrix.
Nabijheidsmatrix uit een grafiek
Bij ongerichte grafieken is de matrix symmetrisch om de diagonaal door elke rand (i,j), er is ook een rand (j,i).
Voordelen van aangrenzende matrix
De basisbewerkingen zoals het toevoegen van een rand, het verwijderen van een rand en het controleren of er een rand is van hoekpunt i naar hoekpunt j, zijn uiterst tijdbesparende bewerkingen met constante tijd.
Als de grafiek dicht is en het aantal randen groot is, moet een aangrenzende matrix de eerste keuze zijn. Zelfs als de grafiek en de aangrenzende matrix schaars zijn, kunnen we deze weergeven met behulp van datastructuren voor schaarse matrices.
Het grootste voordeel is echter het gebruik van matrices. Door de recente vooruitgang in hardware kunnen we zelfs dure matrixbewerkingen op de GPU uitvoeren.
Door bewerkingen uit te voeren op de aangrenzende matrix, kunnen we belangrijke inzichten krijgen in de aard van de grafiek en de relatie tussen zijn hoekpunten.
Nadelen van aangrenzende matrix
De VxVbenodigde ruimte van de aangrenzende matrix maakt het een geheugenvarken. Grafieken in het wild hebben meestal niet teveel verbindingen en dit is de belangrijkste reden waarom aangrenzende lijsten de betere keuze zijn voor de meeste taken.
Hoewel basisbewerkingen eenvoudig zijn, zijn bewerkingen zoals inEdgesen outEdgesduur bij gebruik van de aangrenzende matrixweergave.
Python, Java en C / C ++ voorbeelden
Als je weet hoe je tweedimensionale arrays moet maken, weet je ook hoe je een aangrenzende matrix moet maken.
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(); )
Toepassingen van aangrenzende matrix
- Routeringstabel in netwerken maken
- Navigatietaken
