Introducción a los Grafos

En el ámbito de la informática, un grafo se define como una estructura de datos que modela relaciones muchos a muchos entre entidades. Al integrar algoritmos especializados, los grafos permiten resolver una amplia variedad de problemas computacionales complejos, convirtiéndose en un pilar fundamental para el diseño de algoritmos eficientes.

Estructuras de Datos para Representar Grafos

Para manipular grafos en memoria, se utilizan comúnmente las siguientes representaciones:

• Lista de Aristas (Edge List): Consiste en almacenar directamente el nodo de origen, el nodo de destino y el peso de cada conexión. Es útil cuando el orden de procesamiento de las aristas es prioritario o cuando la memoria es extremadamente limitada.
• Matriz de Adyacencia: Emplea un arreglo bidimensional matriz[n][n]. En grafos ponderados, matriz[u][v] = peso indica una conexión, mientras que un valor nulo o infinito denota su ausencia. En grafos no ponderados, actúa como un indicador booleano. Su principal ventaja es la consulta en tiempo constante $O(1)$, aunque consume $O(N^2)$ de memoria.
• Lista de Adyacencia: Agrupa las aristas por nodo. Utilizando arreglos dinámicos o listas enlazadas, se logra una representación altamente eficiente en memoria, especialmente para grafos dispersos (donde el número de aristas es mucho menor que $N^2$).

A continuación, se muestra una implementación que ilustra la construcción simultánea de una matriz y una lista de adyacencia:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_NODES = 1005;
int adjacencyMatrix[MAX_NODES][MAX_NODES];
vector<int> adjacencyList[MAX_NODES];

int main() {
    int nodeCount, edgeCount;
    if (!(cin >> nodeCount >> edgeCount)) return 0;

    for (int i = 0; i < edgeCount; ++i) {
        int source, destination;
        cin >> source >> destination;
        
        // Construcción de matriz de adyacencia (grafo no dirigido)
        adjacencyMatrix[source][destination] = 1;
        adjacencyMatrix[destination][source] = 1;
        
        // Construcción de lista de adyacencia
        adjacencyList[source].push_back(destination);
        adjacencyList[destination].push_back(source);
    }

    // Impresión de la matriz
    for (int i = 1; i <= nodeCount; ++i) {
        for (int j = 1; j <= nodeCount; ++j) {
            cout << adjacencyMatrix[i][j] << " ";
        }
        cout << "\n";
    }

    // Impresión de la lista ordenada
    for (int i = 1; i <= nodeCount; ++i) {
        sort(adjacencyList[i].begin(), adjacencyList[i].end());
        cout << adjacencyList[i].size() << " ";
        for (int neighbor : adjacencyList[i]) {
            cout << neighbor << " ";
        }
        cout << "\n";
    }

    return 0;
}

Algoritmos de Recorrido

Recorrer un grafo implica visitar todos sus nodos de manera sistemática sin repeticiones. Las dos estrategias fundamentales para explorar la estructura son:

• Búsqueda en Profundidad (DFS - Depth First Search): Explora tan lejos como sea posible a lo largo de cada rama antes de retroceder. Se implementa típicamente mediante recursión, aprovechando la pila de llamadas del sistema.
• Búsqueda en Anchura (BFS - Breadth First Search): Explora los nodos vecinos nivel por nivel. Utiliza una estructura de datos tipo cola (FIFO) para garantizar que los nodos más cercanos al origen se procesen primero.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX_VERTICES = 100005;
vector<int> graph[MAX_VERTICES];
bool visitedNodes[MAX_VERTICES];
int totalNodes, totalEdges;

void depthFirstSearch(int current) {
    visitedNodes[current] = true;
    cout << current << " ";
    for (int neighbor : graph[current]) {
        if (!visitedNodes[neighbor]) {
            depthFirstSearch(neighbor);
        }
    }
}

void breadthFirstSearch(int startNode) {
    queue<int> nodeQueue;
    nodeQueue.push(startNode);
    visitedNodes[startNode] = true;
    
    while (!nodeQueue.empty()) {
        int current = nodeQueue.front();
        nodeQueue.pop();
        cout << current << " ";
        
        for (int neighbor : graph[current]) {
            if (!visitedNodes[neighbor]) {
                visitedNodes[neighbor] = true;
                nodeQueue.push(neighbor);
            }
        }
    }
}

int main() {
    cin >> totalNodes >> totalEdges;
    for (int i = 0; i < totalEdges; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }

    for (int i = 1; i <= totalNodes; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }

    memset(visitedNodes, 0, sizeof(visitedNodes));
    depthFirstSearch(1);
    cout << "\n";

    memset(visitedNodes, 0, sizeof(visitedNodes));
    breadthFirstSearch(1);
    cout << "\n";

    return 0;
}

Aplicaciones Prácticas y Optimizaciones

Optimización mediante Grafos Inversos

Al buscar el nodo de mayor identificador alcanzable desde cada vértice, ejecuatr un DFS individual desde cada nodo resulta en una complejidad temporal inaceptable para grafos grandes. Un enfoque inverso resuelve este problema: se invierte la dirección de todas las aristas y se inicia un recorrido desde los nodos con mayor identificador hacia los menores. De esta manera, el primer nodo origen que logre visitar a otro le asignará automáticamente el valor máximo posible, reduciendo la complejidad a $O(N + M)$.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_VERTICES = 100005;
vector<int> reverseGraph[MAX_VERTICES];
int maxReachable[MAX_VERTICES];
int nodeCount, edgeCount;

void propagateMaxId(int current, int sourceId) {
    if (maxReachable[current] != 0) return; // Ya visitado por un ID mayor o igual
    maxReachable[current] = sourceId;
    for (int neighbor : reverseGraph[current]) {
        propagateMaxId(neighbor, sourceId);
    }
}

int main() {
    cin >> nodeCount >> edgeCount;
    for (int i = 0; i < edgeCount; ++i) {
        int u, v;
        cin >> u >> v;
        reverseGraph[v].push_back(u); // Construcción del grafo inverso
    }

    for (int i = nodeCount; i > 0; --i) {
        propagateMaxId(i, i);
    }

    for (int i = 1; i <= nodeCount; ++i) {
        cout << maxReachable[i] << " ";
    }
    cout << "\n";

    return 0;
}

Gestión de Tareas y Dependencias

Cuando se modelan tareas con prerrequisitos como un Grafo Acíclico Dirigido (DAG), es posible calcular el tiempo total mínimo requerido para completar todos los trabajos. Cada nodo apunta a las tareas que dependen directamente de él. Aplicando DFS con memorización, se calcula la ruta crítica (el camino más largo) en el grafo, asegurando que cada subtarea se resuelva exactamente una vez.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_TASKS = 10005;
vector<int> dependencyGraph[MAX_TASKS];
int taskDuration[MAX_TASKS];
int memoTime[MAX_TASKS];
int totalTasks;

int calculateCriticalPath(int taskId) {
    if (memoTime[taskId] > 0) return memoTime[taskId];
    
    int maxDependencyTime = 0;
    for (int dependentTask : dependencyGraph[taskId]) {
        maxDependencyTime = max(maxDependencyTime, calculateCriticalPath(dependentTask));
    }
    
    memoTime[taskId] = maxDependencyTime + taskDuration[taskId];
    return memoTime[taskId];
}

int main() {
    cin >> totalTasks;
    for (int i = 1; i <= totalTasks; ++i) {
        int taskId, prerequisite;
        cin >> taskId >> taskDuration[taskId];
        while (cin >> prerequisite && prerequisite != 0) {
            dependencyGraph[prerequisite].push_back(taskId);
        }
    }

    int minimumTotalTime = 0;
    for (int i = 1; i <= totalTasks; ++i) {
        minimumTotalTime = max(minimumTotalTime, calculateCriticalPath(i));
    }

    cout << minimumTotalTime << "\n";
    return 0;
}

Conteo de Rutas con Memorización

Para determinar el número de cadenas alimenticias en un ecosistema modelado como un DAG, se utiliza un enfoque combinado de grafos inversos y programación dinámica. Al invertir el grafo, se facilita el cálculo de caminos desde los productores hasta los consumidores. Mediante búsqueda con memorización, se acumulan las rutas posibles aplicando aritmética modular para evitar desbordamientos. El resultado final es la suma de los caminos que terminan estrictamente en nodos sin aristas salientes (consumidores ápice).

#include <iostream>
#include <vector>

using namespace std;

const int MAX_SPECIES = 5005;
const long long MODULO = 80112002;

int inDegree[MAX_SPECIES];
int outDegree[MAX_SPECIES];
vector<int> invertedEcosystem[MAX_SPECIES];
long long pathCount[MAX_SPECIES];
int speciesCount, relationCount;

long long countFoodChains(int currentSpecies) {
    if (pathCount[currentSpecies] != -1) return pathCount[currentSpecies];
    
    long long totalPaths = 0;
    for (int predator : invertedEcosystem[currentSpecies]) {
        totalPaths = (totalPaths + countFoodChains(predator)) % MODULO;
    }
    
    return pathCount[currentSpecies] = totalPaths;
}

int main() {
    cin >> speciesCount >> relationCount;
    
    for (int i = 1; i <= speciesCount; ++i) {
        pathCount[i] = -1; // Inicialización para memorización
    }

    for (int i = 0; i < relationCount; ++i) {
        int prey, predator;
        cin >> prey >> predator;
        outDegree[prey]++;
        inDegree[predator]++;
        invertedEcosystem[predator].push_back(prey); // Grafo invertido
    }

    // Los productores (sin depredadores en el grafo original) inician con 1 camino
    for (int i = 1; i <= speciesCount; ++i) {
        if (inDegree[i] == 0) {
            pathCount[i] = 1;
        }
    }

    // Calcular caminos para todas las especies
    for (int i = 1; i <= speciesCount; ++i) {
        countFoodChains(i);
    }

    // Sumar los caminos de los consumidores ápice (sin presas en el grafo original)
    long long totalFoodChains = 0;
    for (int i = 1; i <= speciesCount; ++i) {
        if (outDegree[i] == 0) {
            totalFoodChains = (totalFoodChains + pathCount[i]) % MODULO;
        }
    }

    cout << totalFoodChains << "\n";
    return 0;
}