Una matriz de adyacencia representa todas las parejas posibles de vértices mediante una tabla cuadrada. Cada celda indica si existe una conexión entre su fila y su columna.
Una lista de adyacencia almacena únicamente los vecinos existentes. Una matriz de adyacencia, en cambio, reserva una posición para cada par posible de vértices.
Esta representación utiliza una matriz cuadrada de tamaño n × n. Las filas y columnas corresponden a los mismos vértices, y el valor de cada celda informa si existe una arista o arco.
Si los vértices son A, B, C y D, la matriz tendrá cuatro filas y cuatro columnas.
La celda de la fila A y columna B vale 1 porque A y B son adyacentes. La celda A,D vale 0 porque no existe esa conexión.
Para un grafo simple, la matriz utiliza normalmente ceros y unos.
En un grafo dirigido, el orden importa: la fila representa el origen y la columna representa el destino.
| Propiedad | No dirigido | Dirigido |
|---|---|---|
| Interpretación | La fila y columna son extremos | Fila = origen, columna = destino |
| Simetría | matriz[i][j] = matriz[j][i] | No necesariamente simétrica |
| Agregar A—B | Se modifican A,B y B,A | No corresponde |
| Agregar A→B | No corresponde | Solo se modifica A,B |
Pulsa dos nodos del grafo o selecciona una celda de la matriz. Ambas representaciones se actualizan al mismo tiempo. Las celdas de la diagonal permanecen en cero porque trabajamos con grafos simples sin bucles.
Matriz de adyacencia
Fila = origen · Columna = destino
En modo no dirigido, pulsa A,B y observa que B,A cambia también: la matriz conserva su simetría. En modo dirigido, cada celda funciona de manera independiente.
Las celdas matriz[i][i] representan conexiones de un vértice consigo mismo. En un grafo simple sin bucles, toda la diagonal principal contiene ceros.
Si el modelo admite bucles, esas posiciones pueden tener valores distintos de cero.
Podemos crear una matriz n × n con arreglos anidados e inicializar todas sus celdas en cero.
function crearMatriz(cantidadVertices) {
return Array.from(
{ length: cantidadVertices },
() => Array(cantidadVertices).fill(0)
);
}
const matriz = crearMatriz(4);
console.log(matriz);En un grafo no dirigido debemos actualizar dos posiciones simétricas.
const matriz = Array.from({ length: 4 }, () => Array(4).fill(0));
function agregarArista(a, b) {
matriz[a][b] = 1;
matriz[b][a] = 1;
}
agregarArista(0, 2);
console.log(matriz[0]);
console.log(matriz[2]);Para un arco dirigido de a hacia b solo asignaríamos matriz[a][b] = 1.
Comprobar si dos vértices son adyacentes requiere consultar una única celda.
La consulta constante es una ventaja importante, pero el costo cuadrático de memoria puede ser excesivo para grafos grandes y dispersos.
En un grafo no dirigido, el grado de un vértice es la suma de su fila. En un grafo dirigido, la suma de la fila produce el grado de salida y la suma de la columna, el grado de entrada.
| Operación | No dirigido | Dirigido |
|---|---|---|
| Suma de fila i | Grado de i | Grado de salida de i |
| Suma de columna i | El mismo grado | Grado de entrada de i |
En un grafo ponderado, la celda puede guardar el peso de la conexión en lugar de un 1.
Debemos elegir cuidadosamente el valor que representa ausencia de arista, porque un peso cero puede ser válido.
La matriz de adyacencia ofrece consultas directas y una representación regular, especialmente útil para grafos densos y algoritmos matriciales. Su principal costo es reservar espacio para todas las parejas, incluso cuando muchas no están conectadas.
En el próximo tema estudiaremos las matrices de incidencia, que relacionan vértices con aristas en lugar de relacionar vértices entre sí.