Necesidad de estructuras eficientes para grafos

El almacenamiento de grafos es fudnamental en algoritmos. Las matrices de adyacencia consumen O(n²) espacio, resultando ineficientes para grafos dispersos. Las listas de adyacencia tradicionales optimizan espacio pero introducen complejidad con punteros. El Forward Star Encadenado resuelve esto usando arreglos para simular enlaces, manteniendo eficiencia espacial O(∣V∣+∣E∣) sin manipulación directa de puntreos.

Diseño de la estructura

struct Arista {
    int destino;   // Nodo destino
    int peso;      // Peso de la arista
    int siguiente; // Índice de la próxima arista
} aristas[10005];  // Almacenamiento de aristas

int cabeza[105];   // cabeza[i]: primera arista del nodo i
int contador = 0;  // Contador de aristas

Inicialización

memset(cabeza, -1, sizeof(cabeza));
contador = 0;

Inserción de aristas

Nuevas aristas se añaden mediante inserción frontal:

void agregar_arista(int origen, int destino, int peso) {
    aristas[contador].destino = destino;
    aristas[contador].peso = peso;
    aristas[contador].siguiente = cabeza[origen];
    cabeza[origen] = contador;
    contador++;
}

Manejo de grafos no dirigidos

agregar_arista(x, y, peso);
agregar_arista(y, x, peso);

Recorrido de la estructura

void recorrer_grafo() {
    for (int nodo = 1; nodo <= n; nodo++) {
        for (int idx = cabeza[nodo]; idx != -1; idx = aristas[idx].siguiente) {
            int vecino = aristas[idx].destino;
            int peso_arista = aristas[idx].peso;
            cout << nodo << " → " << vecino << " (" << peso_arista << ")\t";
        }
        cout << endl;
    }
}

Caso demostrativo

Entrada:

4 5
1 2 5
1 4 3
2 3 8
2 4 12
3 4 9

Salida:

1 → 4 (3)    1 → 2 (5)
2 → 4 (12)   2 → 3 (8)    2 → 1 (5)
3 → 4 (9)    3 → 2 (8)
4 → 3 (9)    4 → 2 (12)   4 → 1 (3)

Implementación completa

#include <iostream>
#include <cstring>
using namespace std;

struct Arista { /* Definición previa */ };
Arista aristas[10005];
int cabeza[105];
int contador, n, m;

void agregar_arista(int x, int y, int w) { /* Definición previa */ }

void recorrer_grafo() { /* Definición previa */ }

int main() {
    cin >> n >> m;
    memset(cabeza, -1, sizeof(cabeza));
    contador = 0;
    
    while (m--) {
        int x, y, w;
        cin >> x >> y >> w;
        agregar_arista(x, y, w);
        agregar_arista(y, x, w);
    }
    recorrer_grafo();
    return 0;
}

Ventajas y limitaciones

Ventajas

• Espacio óptimo: O(∣V∣+∣E∣)
• Elimina riesgos de manejo manual de memoria
• Inserción en tiempo constante O(1)

Limitaciones

• Orden inverso en recorridos
• Asignación estática de memoria