Algoritmos y Estructura de Datos

Las matrices poco densas dinámicas son aquellas en las que la mayoría de los elementos son cero y que pueden cambiar durante la ejecución de un programa, agregando o eliminando entradas. Al igual que con las matrices poco densas estáticas, las matrices poco densas dinámicas son comunes en aplicaciones que representan grafos o redes, ya que muchos grafos tienen un número mucho mayor de vértices que de aristas.

Una forma eficiente de representar matrices poco densas dinámicas es mediante listas de adyacencia. En lugar de almacenar todos los elementos de la matriz, las listas de adyacencia solo almacenan las entradas no nulas. Esto permite ahorrar espacio y hacer que algunas operaciones sean más rápidas en comparación con las matrices de adyacencia.

A continuación se presenta un ejemplo de código en C++ que muestra cómo se puede crear y utilizar una lista de adyacencia para representar un grafo dinámico poco denso:

                    #include 
                    #include 
                    
                    using namespace std;
                    
                    // Clase que representa un elemento de la matriz
                    class MatrixElement {
                     public:
                      int value;  // Valor del elemento
                      int row;  // Fila del elemento
                      int col;  // Columna del elemento
                    
                      MatrixElement(int value, int row, int col) : value(value), row(row), col(col) {}
                    };
                    
                    // Clase que representa la matriz poco densa y dinámica
                    class SparseDynamicMatrix {
                     private:
                      int numRows;  // Número de filas de la matriz
                      int numCols;  // Número de columnas de la matriz
                      list> matrix;  // Lista ligada de listas que representa la matriz
                    
                     public:
                      SparseDynamicMatrix(int numRows, int numCols) : numRows(numRows), numCols(numCols) {
                        // Inicializamos la matriz con tantas listas vacías como filas tenga la matriz
                        for (int i = 0; i < numRows; i++) {
                          matrix.push_back(list());
                        }
                      }
                    
                      // Función para establecer el valor de un elemento de la matriz
                      void set(int value, int row, int col) {
                        // Comprobamos si el elemento existe en la matriz
                        list &rowList = matrix.at(row);
                        for (MatrixElement &elem : rowList) {
                          if (elem.col == col) {
                            // Si existe, actualizamos su valor
                            elem.value = value;
                            return;
                          }
                        }
                    
                        // Si no existe, añadimos un nuevo elemento a la fila correspondiente
                        rowList.push_back(MatrixElement(value, row, col));
                      }
                    
                      // Función para obtener el valor de un elemento de la matriz
                      int get(int row, int col) {
                        // Buscamos el elemento en la fila correspondiente
                        list &rowList = matrix.at(row);
                        for (MatrixElement &elem : rowList) {
                          if (elem.col == col) {
                            // Si lo encontramos, devolvemos su valor
                            return elem.value;
                          }
                        }
                    
                        // Si no lo encontramos, devolvemos cero
                        return 0;
                      }
                    };

                    int main() {
                        SparseDynamicMatrix matrix(3, 4);
                      
                        // Establecemos algunos valores de la matriz
                        matrix.set(1, 0, 0);
                        matrix.set(2, 0, 3);
                        matrix.set(3, 2, 1);
                      
                        // Mostramos el contenido de la matriz
                        for (int i = 0; i < 3; i++) {
                          for (int j = 0; j < 4; j++) {
                            cout << matrix.get(i, j) << " ";
                          }
                          cout << endl;
                        }
                      
                        return 0;
                      }
            

Link de apoyo