Comprobar aciclicidad de un grafo y encontrar un ciclo en $O(M)$

Consideremos un grafo dirigido o no dirigido sin bucles ni aristas múltiples. Hay que comprobar si es acíclico y, si no lo es, encontrar algún ciclo.

Podemos resolver este problema usando Búsqueda en Profundidad en $O(M)$ , donde $M$ es el número de aristas.

Algoritmo

Ejecutaremos una serie de DFS en el grafo. Inicialmente todos los vértices están coloreados de blanco (0). Desde cada vértice no visitado (blanco), se arranca el DFS, se marca de gris (1) al entrar y de negro (2) al salir. Si el DFS se mueve a un vértice gris, entonces hemos encontrado un ciclo (si el grafo es no dirigido, no se considera la arista al padre). El ciclo en sí se puede reconstruir usando el arreglo de padres.

Implementación

Aquí hay una implementación para grafo dirigido.


int n;
vector<vector<int>> adj;
vector<char> color;
vector<int> parent;
int cycle_start, cycle_end;
 
bool dfs(int v) {
    color[v] = 1;
    for (int u : adj[v]) {
        if (color[u] == 0) {
            parent[u] = v;
            if (dfs(u))
                return true;
        } else if (color[u] == 1) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
    }
    color[v] = 2;
    return false;
}
 
void find_cycle() {
    color.assign(n, 0);
    parent.assign(n, -1);
    cycle_start = -1;
 
    for (int v = 0; v < n; v++) {
        if (color[v] == 0 && dfs(v))
            break;
    }
 
    if (cycle_start == -1) {
        cout << "Acyclic" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
        reverse(cycle.begin(), cycle.end());
 
        cout << "Cycle found: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}

Aquí hay una implementación para grafo no dirigido. Nótese que en la versión no dirigida, si un vértice v se colorea de negro, el DFS no lo volverá a visitar nunca. Esto se debe a que ya exploramos todas las aristas conectadas de v cuando lo visitamos por primera vez. La componente conexa que contiene a v (después de eliminar la arista entre v y su padre) debe ser un árbol, si el DFS terminó de procesar v sin encontrar un ciclo. Así que ni siquiera hace falta distinguir entre los estados gris y negro. Por lo tanto, podemos convertir el vector de char color en un vector booleano visited.


int n;
vector<vector<int>> adj;
vector<bool> visited;
vector<int> parent;
int cycle_start, cycle_end;
 
bool dfs(int v, int par) { // se pasa el vértice y su vértice padre
    visited[v] = true;
    for (int u : adj[v]) {
        if(u == par) continue; // se omite la arista al vértice padre
        if (visited[u]) {
            cycle_end = v;
            cycle_start = u;
            return true;
        }
        parent[u] = v;
        if (dfs(u, parent[u]))
            return true;
    }
    return false;
}
 
void find_cycle() {
    visited.assign(n, false);
    parent.assign(n, -1);
    cycle_start = -1;
 
    for (int v = 0; v < n; v++) {
        if (!visited[v] && dfs(v, parent[v]))
            break;
    }
 
    if (cycle_start == -1) {
        cout << "Acyclic" << endl;
    } else {
        vector<int> cycle;
        cycle.push_back(cycle_start);
        for (int v = cycle_end; v != cycle_start; v = parent[v])
            cycle.push_back(v);
        cycle.push_back(cycle_start);
 
        cout << "Cycle found: ";
        for (int v : cycle)
            cout << v << " ";
        cout << endl;
    }
}

Comprobar aciclicidad de un grafo y encontrar un ciclo en O(M)O(M)O(M)

Algoritmo

Implementación

Problemas de práctica:

Comprobar aciclicidad de un grafo y encontrar un ciclo en $O(M)$