Fundamentos y Algoritmos Clave para la Manipulación de Grafos

1. Representación Básica de Grafos

La representación fundamental de un grafo se basa en:

• Vértices y Aristas.
• Grafo dirigido: Las aristas son representadas por flechas (direccionalidad).
• Grafo no dirigido: Las aristas representan una conexión de ida y vuelta.

Estructura típica para el recorrido:

• visitado[] (Array booleano para rastrear nodos).
• cola (para BFS) o recursión/pila (para DFS).

2. BFS – Búsqueda en Anchura (Usando COLA)

Utilice BFS cuando necesite:

• Encontrar el camino más corto en grafos sin pesos.
• Determinar la distancia mínima en términos del número de aristas.
• Verificar alcanzabilidad.
• Identificar grafos bipartidos.
• Encontrar componentes conexas (en grafos no dirigidos).

Esqueleto BFS

Se requiere una queue (cola) y un vector de estado visitado:

queue<int> q;
vector<bool> visitado(n, false);

visitado[origen] = true;
q.push(origen);

while (!q.empty()) {
    v = q.front(); q.pop();
    for (vecino de v)
        if (!visitado[vecino]) {
            visitado[vecino] = true;
            q.push(vecino);
        }
}

Problemas Típicos Resueltos con BFS

3. DFS – Búsqueda en Profundidad (Usando RECURSIÓN/PILA)

Utilice DFS cuando necesite:

• Encontrar componentes conexas.
• Detección de ciclos.
• Calcular la ordenación topológica.
• Identificar componentes fuertemente conexas (CFS).

Esqueleto DFS

La implementación recursiva es la más común:

void dfs(int v) {
    visitado[v] = true;
    for (int vecino : adyacencia[v])
        if (!visitado[vecino])
            dfs(vecino);
}

4. Componentes Conexas (Grafo No Dirigido)

Pregunta típica: ¿Cuántos grupos aislados hay en el grafo?

Idea:

• Ejecutar DFS o BFS desde cada vértice que aún no haya sido visitado.
• Cada vez que se inicia una nueva llamada recursiva/iterativa desde un nodo no visitado, se identifica una nueva componente.

Implementación conceptual:

contador = 0
for cada vertice v:
    si no visitado[v]:
        contador++
        dfs(v) // o bfs(v)

5. Alcanzabilidad (Grafo Dirigido)

6. Conectividad Fuerte (Grafo Dirigido)

Un grafo es fuertemente conexo si:

• Desde cualquier nodo A se puede llegar a todos los demás nodos.
• Desde cualquier nodo se puede llegar al nodo A (es decir, todos pueden llegar a A).

✔ La forma más eficiente de verificar esto o encontrar las componentes es usando el algoritmo de Kosaraju o Tarjan.

7. Componentes Fuertemente Conexas (CFS)

Algoritmo de Kosaraju

Este algoritmo se basa en dos pasadas de DFS:

1. DFS normal: Recorrer el grafo y guardar el orden de terminación de los nodos en una pila.
2. DFS sobre el grafo invertido: Procesar los nodos en el orden de la pila, usando las aristas invertidas.
3. Cada nueva ejecución de DFS en el paso 2 define una CFS.

Paso 1: DFS y Pila de Terminación

void dfs1(int v, vector<bool>& visitado, stack<int>& pila) {
    visitado[v] = true;
    for (int vecino : adj[v])
        if (!visitado[vecino])
            dfs1(vecino, visitado, pila);
    pila.push(v);
}

Paso 2: DFS Invertido

Se utiliza el grafo con las aristas revertidas (adjInvertido):

void dfs2(int v, vector<int>& componente, int color) {
    componente[v] = color;
    for (int vecino : adjInvertido[v])
        if (componente[vecino] == -1)
            dfs2(vecino, componente, color);
}

Paso 3: Algoritmo Completo

vector<int> kosaraju(int n) {
    vector<bool> visitado(n, false);
    vector<int> componente(n, -1);
    stack<int> pila;

    // 1. DFS normal para llenar la pila
    for (int i = 0; i < n; i++)
        if (!visitado[i])
            dfs1(i, visitado, pila);

    // 2. DFS invertido en orden de la pila
    int color = 0;
    while (!pila.empty()) {
        int v = pila.top(); pila.pop();
        if (componente[v] == -1) {
            dfs2(v, componente, ++color);
        }
    }
    return componente;
}

8. Grafos Acíclicos Dirigidos (DAG)

Detección de Ciclos (Usando DFS)

Para detectar ciclos en un DAG, se necesitan dos estados además de visitado[]:

• visitado[]: Indica si el nodo ha sido procesado alguna vez.
• terminado[] (o en recursión): Indica si el nodo está actualmente en la pila de recursión activa.

Condición de ciclo: Si al visitar un vecino, este ya está visitado pero aún no está terminado, se ha encontrado un ciclo.

9. Ordenación Topológica (DAG)

Se utiliza en ejercicios que implican dependencias, como asignaturas o planificación de tareas.

Método 1: Kahn (Basado en BFS y Grado de Entrada)

Idea:

• Comenzar por los nodos que no dependen de nadie (grado de entrada cero).
• Procesarlos, eliminarlos conceptualmente del grafo y actualizar las dependencias de sus vecinos.
• Si al final no se incluyen todos los nodos, el grafo contiene un ciclo.

vector<int> ordenTopologico(int n) {
    vector<int> gradoEntrada(n);
    queue<int> q;
    vector<int> orden;

    // 1. Calcular grados de entrada
    for (int v = 0; v < n; v++)
        for (int vecino : adj[v])
            gradoEntrada[vecino]++;

    // 2. Inicializar la cola con nodos de grado 0
    for (int v = 0; v < n; v++)
        if (gradoEntrada[v] == 0)
            q.push(v);

    // 3. Proceso BFS
    while (!q.empty()) {
        int v = q.front(); q.pop();
        orden.push_back(v);

        for (int vecino : adj[v]) {
            gradoEntrada[vecino]--;
            if (gradoEntrada[vecino] == 0)
                q.push(vecino);
        }
    }

    // 4. Comprobar ciclo
    if (orden.size() != n)
        throw runtime_error("El grafo tiene ciclos");

    return orden;
}

Método 2: DFS

• Realizar un DFS completo.
• Apilar el nodo justo antes de que termine la recursión.
• El orden topológico es el resultado de vaciar la pila.

10. Caminos Mínimos CON Pesos

Dijkstra

Idea:

• El algoritmo siempre explora el camino más barato conocido hasta el momento.
• Requiere que los pesos de las aristas sean no negativos.

Se utiliza una priority_queue para gestionar eficientemente la selección del siguiente nodo a visitar.

vector<int> dijkstra(int origen, int n) {
    vector<float> dist(n, INF);
    vector<int> padre(n, -1);
    // priority_queue almacena {distancia, nodo}
    priority_queue<pair<float,int>, 
                   vector<pair<float,int>>,
                   greater<pair<float,int>>> pq;

    dist[origen] = 0;
    padre[origen] = -2; // Marcador especial para el origen
    pq.push({0, origen});

    while (!pq.empty()) {
        auto [d, v] = pq.top(); pq.pop();

        if (d > dist[v]) continue; // Ya encontramos un camino mejor

        for (auto [vecino, peso] : adj[v]) {
            if (dist[v] + peso < dist[vecino]) {
                dist[vecino] = dist[v] + peso;
                padre[vecino] = v;
                pq.push({dist[vecino], vecino});
            }
        }
    }
    return padre;
}

✔ Aplicaciones de Dijkstra:

• Cálculo del camino mínimo.
• Determinación de energía mínima en ciertas rutas.
• Conteo de caminos mínimos (con modificaciones).

11. Árbol Generador Mínimo (AGM)

Prim

Se aplica a grafos no dirigidos y conexos.

Concepto: Similar a Dijkstra, pero el objetivo es conectar todos los vértices con el coste total de aristas mínimo, no encontrar un camino desde un origen.

La prioridad se basa en el peso de la arista que conecta un nodo fuera del árbol con un nodo ya incluido.

vector<int> prim(int n) {
    vector<float> peso(n, INF); // Peso mínimo para incluir el nodo
    vector<int> padre(n, -1);
    vector<bool> enArbol(n, false);

    priority_queue<pair<float,int>,
                   vector<pair<float,int>>,
                   greater<pair<float,int>>> pq;

    peso[0] = 0;
    padre[0] = -2;
    pq.push({0, 0});

    while (!pq.empty()) {
        int v = pq.top().second;
        pq.pop();

        if (enArbol[v]) continue;
        enArbol[v] = true;

        for (auto [vecino, w] : adj[v]) {
            if (!enArbol[vecino] && w < peso[vecino]) {
                peso[vecino] = w;
                padre[vecino] = v;
                pq.push({peso[vecino], vecino});
            }
        }
    }
    return padre;
}

12. Grafos Bipartidos

Pregunta típica: ¿Se puede dividir el conjunto de vértices en dos grupos disjuntos de tal manera que no haya aristas entre vértices del mismo grupo?

Idea:

• Utilizar colores (ej. 1 y 2) mediante BFS o DFS.
• Asignar un color al nodo inicial. Todos sus vecinos deben tener el color opuesto.
• Si en algún momento un vecino ya coloreado tiene el mismo color que el nodo actual, el grafo no es bipartido (❌).

13. Selección de Algoritmo

🧩 CONSEJO FINAL PARA EXAMEN

Sigue estos pasos metódicos para abordar cualquier problema de grafos:

1. Identifica el tipo de grafo (dirigido, no dirigido, ponderado, DAG).
2. Verifica la presencia de pesos (esto descarta BFS/DFS puros para caminos).
3. Determina el objetivo principal: ¿Buscas camino, grupos, ciclos o dependencias?
4. Elige el algoritmo base: BFS, DFS, Dijkstra, Prim, o Kosaraju.
5. Escribe el esqueleto del algoritmo elegido.
6. Añade la lógica específica requerida por el problema (ej. contador, arreglo padre, distancia, o color).