En este tutorial, aprenderá qué es una matriz de adyacencia. Además, encontrará ejemplos prácticos de matriz de adyacencia en C, C ++, Java y Python.
Una matriz de adyacencia es una forma de representar un gráfico G = (V, E) como una matriz de valores booleanos.
Representación de la matriz de adyacencia
El tamaño de la matriz es VxVdonde Vestá el número de vértices en el gráfico y el valor de una entrada Aijes 1 o 0 dependiendo de si hay un borde desde el vértice i al vértice j.
Ejemplo de matriz de adyacencia
La siguiente imagen muestra un gráfico y su matriz de adyacencia equivalente.
Matriz de adyacencia de un gráfico
En el caso de gráficos no dirigidos, la matriz es simétrica con respecto a la diagonal porque en cada borde (i,j), también hay un borde (j,i).
Ventajas de la matriz de adyacencia
Las operaciones básicas como agregar una arista, eliminar una arista y verificar si hay una arista desde el vértice i al vértice j son operaciones de tiempo constante y extremadamente eficientes en el tiempo.
Si el gráfico es denso y el número de aristas es grande, la matriz de adyacencia debe ser la primera opción. Incluso si el gráfico y la matriz de adyacencia son escasos, podemos representarlos utilizando estructuras de datos para matrices escasas.
Sin embargo, la mayor ventaja proviene del uso de matrices. Los recientes avances en hardware nos permiten realizar incluso costosas operaciones matriciales en la GPU.
Al realizar operaciones en la matriz adyacente, podemos obtener información importante sobre la naturaleza del gráfico y la relación entre sus vértices.
Contras de la matriz de adyacencia
El VxVrequisito de espacio de la matriz de adyacencia la convierte en un acaparador de memoria. Los gráficos en la naturaleza generalmente no tienen demasiadas conexiones y esta es la razón principal por la que las listas de adyacencia son la mejor opción para la mayoría de las tareas.
Si bien las operaciones básicas son fáciles, las operaciones similares inEdgesy outEdgescostosas cuando se usa la representación de matriz de adyacencia.
Ejemplos de Python, Java y C / C ++
Si sabe cómo crear matrices bidimensionales, también sabe cómo crear una matriz de adyacencia.
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(); )
Aplicaciones de matriz de adyacencia
- Creando tabla de enrutamiento en redes
- Tareas de navegación
