Algoritmos y Estructura de Datos

Temas

Matrices poco densas Estáticas


Las matrices poco densas son aquellas en las que la mayoría de los elementos son cero. Es decir, hay pocas entradas no nulas en la matriz en comparación con el número total de entradas. Las matrices poco densas son comunes en aplicaciones en las que se representan grafos o redes, ya que muchos grafos tienen un número mucho mayor de vértices que de aristas.


Las matrices estáticas son aquellas que no cambian después de su creación. Es decir, una vez que se ha definido una matriz estática, no se pueden agregar ni eliminar entradas de ella. En cambio, las matrices dinámicas son aquellas que pueden cambiar durante la ejecución de un programa, agregando o eliminando entradas.


Para matrices poco densas estáticas, una forma eficiente de representarlas es mediante una matriz de adyacencia, en la que cada entrada representa una arista en el grafo. Esto permite un acceso rápido a cualquier entrada de la matriz mediante índices y es adecuado para grafos de tamaño mediano o pequeño. Sin embargo, para grafos muy grandes o con muchas aristas, puede ser más eficiente utilizar otras estructuras de datos, como listas de adyacencia.


A continuacion el codigo para c++:

                    
    
                        
  1. #include <iostream>
    2. 
                        
  2. 
                        
  3. using namespace std;
    4. 
                        
  4. 
                        
  5. const int MAX_V = 100;  // Número máximo de vértices
    6. 
                        
  6. 
                        
  7. // Estructura para almacenar una matriz de adyacencia
    8. 
                        
  8. struct MatrizAdyacencia {
    9. 
                        
  9.   int V;  // Número de vértices
    10. 
                        
  10.   int E;  // Número de aristas
    11. 
                        
  11.   int matriz[MAX_V][MAX_V];  // Matriz de adyacencia
    12. 
                        
  12. 
                        
  13.   // Constructor para inicializar la matriz
    14. 
                        
  14.   MatrizAdyacencia(int V) {
    15. 
                        
  15.     this->V = V;
    16. 
                        
  16.     this->E = 0;
    17. 
                        
  17.     for (int i = 0; i < V; i++) {
    18. 
                        
  18.       for (int j = 0; j < V; j++) {
    19. 
                        
  19.         matriz[i][j] = 0;
    20. 
                        
  20.       }
    21. 
                        
  21.     }
    22. 
                        
  22.   }
    23. 
                        
  23. 
                        
  24.   // Método para agregar una arista entre los vértices u y v con peso w
    25. 
                        
  25.   void agregarArista(int u, int v, int w) {
    26. 
                        
  26.     matriz[u][v] = w;
    27. 
                        
  27.     E++;
    28. 
                        
  28.   }
    29. 
                        
  29. 
                        
  30.   // Método para obtener el peso de la arista entre los vértices u y v
    31. 
                        
  31.   int obtenerPesoArista(int u, int v) {
    32. 
                        
  32.     return matriz[u][v];
    33. 
                        
  33.   }
    34. 
                        
  34. 
                        
  35.   // Método para verificar si hay una arista entre los vértices u y v
    36. 
                        
  36.   bool hayArista(int u, int v) {
    37. 
                        
  37.     return matriz[u][v] != 0;
    38. 
                        
  38.   }
    39. 
                        
  39. 
                        
  40.   // Método para eliminar la arista entre los vértices u y v
    41. 
                        
  41.   void eliminarArista(int u, int v) {
    42. 
                        
  42.     matriz[u][v] = 0;
    43. 
                        
  43.     E--;
    44. 
                        
  44.   }
    45. 
                        
  45. 
                        
  46.   // Método para obtener el grado de un vértice (es decir, el número de aristas que tienen
    47. 
                        
  47. un vértice como extremo)
    48. 
                        
  48.   int obtenerGradoVertice(int v) {
    49. 
                        
  49.     int grado = 0;
    50. 
                        
  50.     for (int i = 0; i < V; i++) {
    51. 
                        
  51.       if (matriz[v][i] != 0) grado++;
    52. 
                        
  52.       if (matriz[i][v] != 0) grado++;
    53. 
                        
  53.     }
    54. 
                        
  54.     return grado;
    55. 
                        
  55.   }
    56. 
                        
  56. };
    57. 
                        
  57. 
                        
  58. int main() {
    59. 
                        
  59.   // Crear una matriz de adyacencia 4x4 para representar un grafo con 4 vértices
    60. 
                        
  60.   MatrizAdyacencia matriz(4);
    61. 
                        
  61. 
                        
  62.   // Agregar algunas aristas
    63. 
                        
  63.   matriz.agregarArista(0, 1, 10);
    64. 
                        
  64.   matriz.agregarArista(1, 2, 20);
    65.

Link de apoyo

  • Matriz poco densa regular
  • MATRICES POCO DENSAS - Metodos de Programación
  • MATRICES POCO DENSAS