DFS en Grafos

DFS en grafos: repaso y extensiones

DFS en grafos es idéntico al concepto general, pero aquí exploramos aplicaciones más avanzadas.

Clasificación de aristas (grafos dirigidos)

Durante un DFS, cada arista se clasifica en uno de 4 tipos:

enum Estado { BLANCO, GRIS, NEGRO };
Estado estado[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;

void dfs(int u) {
    estado[u] = GRIS;
    tin[u] = timer++;

    for (int v : adj[u]) {
        if (estado[v] == BLANCO) {
            // Arista de árbol (tree edge)
            dfs(v);
        } else if (estado[v] == GRIS) {
            // Arista de retroceso (back edge) → ¡CICLO!
        } else {
            // Arista de avance o cruce
            if (tin[u] < tin[v]) {
                // Arista de avance (forward edge)
            } else {
                // Arista de cruce (cross edge)
            }
        }
    }

    estado[u] = NEGRO;
    tout[u] = timer++;
}

• BLANCO: No visitado
• GRIS: En el stack de DFS (siendo procesado)
• NEGRO: Completamente procesado

Detectar ciclos en grafo dirigido

Hay ciclo si encontramos una arista de retroceso (back edge):

bool tieneCiclo = false;

void dfs(int u) {
    estado[u] = GRIS;

    for (int v : adj[u]) {
        if (estado[v] == GRIS) {
            tieneCiclo = true;
            return;
        }
        if (estado[v] == BLANCO) {
            dfs(v);
        }
    }

    estado[u] = NEGRO;
}

bool hayCiclo(int n) {
    fill(estado, estado + n + 1, BLANCO);
    tieneCiclo = false;

    for (int i = 1; i <= n; i++) {
        if (estado[i] == BLANCO) {
            dfs(i);
            if (tieneCiclo) return true;
        }
    }
    return false;
}

Tiempos de entrada y salida

Los tiempos tin y tout son muy útiles:

void dfs(int u, int p) {
    tin[u] = timer++;

    for (int v : adj[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }

    tout[u] = timer++;
}

Propiedad: u es ancestro de v si y solo si tin[u] < tin[v] y tout[u] > tout[v].

bool esAncestro(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

DFS para encontrar puentes y puntos de articulación

Un puente es una arista cuya eliminación desconecta el grafo. Un punto de articulación es un nodo cuya eliminación desconecta el grafo.

int low[MAXN], tin[MAXN], timer = 0;
bool vis[MAXN];
vector<pair<int,int>> puentes;

void dfsPuentes(int u, int padre) {
    vis[u] = true;
    tin[u] = low[u] = timer++;

    for (int v : adj[u]) {
        if (v == padre) continue;

        if (vis[v]) {
            low[u] = min(low[u], tin[v]);
        } else {
            dfsPuentes(v, u);
            low[u] = min(low[u], low[v]);

            if (low[v] > tin[u]) {
                puentes.push_back({u, v});
            }
        }
    }
}

low[u] = el menor tin alcanzable desde el subárbol de u usando aristas de retroceso.

Si low[v] > tin[u], la arista (u, v) es un puente.

Ejercicio de práctica

Dado un grafo dirigido, determina si tiene un ciclo.

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

const int MAXN = 100005;
vector<int> adj[MAXN];
int estado[MAXN];  // 0=blanco, 1=gris, 2=negro
bool ciclo = false;

void dfs(int u) {
    estado[u] = 1;
    for (int v : adj[u]) {
        if (estado[v] == 1) { ciclo = true; return; }
        if (estado[v] == 0) dfs(v);
        if (ciclo) return;
    }
    estado[u] = 2;
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (estado[i] == 0) dfs(i);
    }

    cout << (ciclo ? "Tiene ciclo" : "No tiene ciclo") << endl;
    return 0;
}