Introducción a las Matrices Dispersas

En el ámbito de la informática y el procesamiento de datos, las matrices (o arrays multidimensionales) son estructuras fundamentales. Sin embargo, en muchas aplicaciones, estas matrices pueden contener una gran proporción de elementos con un valor idéntico, comúnmente cero. Consideremos una matriz como la siguiente, de 11x11, donde la mayoría de sus celdas son cero:

0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 
0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

Almacenar esta matriz en su forma completa ocuparía espacio innecesario, ya que la información significativa reside solo en unos pocos elementos. Para optimizar el uso de memoria y mejorar la eficiencia, se emplea el concepto de matriz dispersa.

Concepto y Estructura de una Matriz Dispersa

Una matriz dispersa es una representación de una matriz donde la mayoría de sus elementos tienen un valor predeterminado (frecuentemente cero o un valor base). En lugar de almacenar todos los elementos, solo se guardan los elementos que difieren de este valor predeterminado. Para lograr esto, una matriz dispersa típicamente almacena la siguiente información:

1. Las dimensiones de la matriz original (número de filas y columnas).
2. El número total de elementos "significativos" (no cero o no el valor predeterminado).
3. Para cada elemento significativo, su posición (fila y columna) y su valor.

Esta información se ograniza generalmente en una matriz bidimensional más pequeña. La primera fila de esta matriz dispersa se utiliza para almacenar los metadatos (dimensiones y conteo), y las filas subsiguientes contienen los datos de los elementos significativos.

Retomando el ejemplo anterior, la matriz original y su representación dispersa equivalente serían:

Matriz Original (11x11)          Matriz Dispersa (Fila, Columna, Valor)
                                 
0 0 0 0 0 0 0 0 0 0 0         [0] 11  11   2  (Metadatos: Filas, Columnas, Num. de elementos no cero)
0 0 1 0 0 0 0 0 0 0 0         [1]  1   2   1  (Elemento en [1][2] con valor 1)
0 0 0 2 0 0 0 0 0 0 0         [2]  2   3   2  (Elemento en [2][3] con valor 2)
0 0 0 0 0 0 0 0 0 0 0
... (resto de ceros)

Conversión de Matriz Tradicional a Matriz Dispersa

El proceso para convertir una matriz tradicional a su forma dispersa implica dos pasos principales:

1. Primero, se recorre la matriz original para contar cuántos elementos son diferentes de cero (o del valor base). Esto determinará el tamaño de la matriz dispersa resultante.
2. Segundo, se vuelve a recorrer la matriz originla. Por cada elemento significativo, se registra su índice de fila, índice de columna y su valor en la matriz dispersa. La primera fila de la matriz dispersa se reserva para almacenar las dimensiones generales y el conteo de elementos significativos.

A continuación, se presenta un método en Java que realiza esta conversión:

import java.util.Arrays; // Utilizado para la impresión de matrices, si es necesario.

public class GestorMatricesDispersas {

    /**
     * Convierte una matriz bidimensional tradicional a su representación dispersa.
     * Los elementos con valor 0 se consideran no significativos.
     *
     * @param matrizFuente La matriz original de enteros.
     * @return Una matriz bidimensional que representa la versión dispersa de la matriz fuente.
     */
    public static int[][] convertirAMatrizDispersa(int[][] matrizFuente) {
        if (matrizFuente == null || matrizFuente.length == 0 || matrizFuente[0].length == 0) {
            // Manejo de caso para matrices vacías o inválidas, retorna una matriz dispersa mínima
            return new int[1][3]; 
        }

        int numeroFilasOriginal = matrizFuente.length;
        int numeroColumnasOriginal = matrizFuente[0].length;
        int cantidadElementosNoCero = 0;

        // Primera pasada: Contar los elementos que no son cero.
        for (int r = 0; r < numeroFilasOriginal; r++) {
            for (int c = 0; c < numeroColumnasOriginal; c++) {
                if (matrizFuente[r][c] != 0) {
                    cantidadElementosNoCero++;
                }
            }
        }

        // Crear la matriz dispersa. El tamaño es (cantidadElementosNoCero + 1) filas y 3 columnas.
        // La fila 0 almacena metadatos (numFilas, numColumnas, cantidadElementosNoCero).
        // Las filas 1 en adelante almacenan (fila, columna, valor) de los elementos no cero.
        int[][] matrizDispersa = new int[cantidadElementosNoCero + 1][3];

        // Llenar la fila de metadatos de la matriz dispersa.
        matrizDispersa[0][0] = numeroFilasOriginal;
        matrizDispersa[0][1] = numeroColumnasOriginal;
        matrizDispersa[0][2] = cantidadElementosNoCero;

        // Segunda pasada: Llenar las filas de datos de la matriz dispersa.
        int indiceDispersoActual = 1; // Empezamos a almacenar datos desde la segunda fila de matrizDispersa.
        for (int r = 0; r < numeroFilasOriginal; r++) {
            for (int c = 0; c < numeroColumnasOriginal; c++) {
                if (matrizFuente[r][c] != 0) {
                    matrizDispersa[indiceDispersoActual][0] = r; // Índice de fila
                    matrizDispersa[indiceDispersoActual][1] = c; // Índice de columna
                    matrizDispersa[indiceDispersoActual][2] = matrizFuente[r][c]; // Valor del elemento
                    indiceDispersoActual++;
                }
            }
        }

        System.out.println("Matriz Dispersa Generada:");
        for (int k = 0; k < matrizDispersa.length; k++) {
            System.out.println(matrizDispersa[k][0] + " " + matrizDispersa[k][1] + " " + matrizDispersa[k][2]);
        }
        return matrizDispersa;
    }
    // Otros métodos de la clase irían aquí
}

Reconstrucción de Matriz Dispersa a Matriz Tradicional

Para reconstruir la matriz original a partir de su forma dispersa, se siguen estos pasos:

1. Se leen los metadatos de la primera fila de la matriz dispersa para obtener las dimensiones de la matriz original (filas y columnas) y la cantidad de elementos significativos.
2. Se inicializa una nueva matriz tradicional con estas dimensiones, rellenándola automáticamente con ceros (o el valor predeterminado).
3. Se recorren las filas de datos de la matriz dispersa. Para cada entrada (fila, columna, valor), se asigna el valor en la posición correspondiente de la matriz tradicional recién creada.

Aquí se muestra un método en Java para llevar a cabo la reconstrucción:

import java.util.Arrays; // Asegúrate de tener esta importación para usar Arrays.toString()

public class GestorMatricesDispersas {
    // ... (El método convertirAMatrizDispersa estaría aquí)

    /**
     * Reconstruye una matriz bidimensional tradicional a partir de su representación dispersa.
     *
     * @param matrizDispersa La matriz dispersa de la cual reconstruir la matriz original.
     * @return La matriz original reconstruida.
     */
    public static int[][] reconstruirMatrizOriginal(int[][] matrizDispersa) {
        // Extraer los metadatos de la primera fila de la matriz dispersa:
        // matrizDispersa[0][0]: Número de filas de la matriz original.
        // matrizDispersa[0][1]: Número de columnas de la matriz original.
        // matrizDispersa[0][2]: Cantidad de elementos no cero.
        int numFilasOriginal = matrizDispersa[0][0];
        int numColumnasOriginal = matrizDispersa[0][1];
        int totalElementosNoCero = matrizDispersa[0][2];

        // Crear una nueva matriz tradicional con las dimensiones obtenidas.
        // Por defecto, todos sus elementos se inicializan a 0 en Java.
        int[][] matrizReconstruida = new int[numFilasOriginal][numColumnasOriginal];

        // Recorrer la matriz dispersa desde la segunda fila (índice 1)
        // hasta el total de elementos no cero, para rellenar la matriz reconstruida.
        for (int i = 1; i <= totalElementosNoCero; i++) {
            int fila = matrizDispersa[i][0];
            int columna = matrizDispersa[i][1];
            int valor = matrizDispersa[i][2];
            matrizReconstruida[fila][columna] = valor;
        }

        System.out.println("\nMatriz Original Reconstruida:");
        for (int r = 0; r < matrizReconstruida.length; r++) {
            System.out.println(Arrays.toString(matrizReconstruida[r]));
        }
        return matrizReconstruida;
    }
}