Orden topológico

Se da un grafo dirigido con $n$ vértices y $m$ aristas. Hay que encontrar un orden de los vértices de modo que cada arista vaya del vértice con índice menor al vértice con índice mayor.

En otras palabras, se quiere encontrar una permutación de los vértices (orden topológico) que corresponda al orden definido por todas las aristas del grafo.

Aquí hay un grafo dado junto con su orden topológico:

El orden topológico puede no ser único (por ejemplo, si existen tres vértices $a$ , $b$ , $c$ para los cuales existen caminos de $a$ a $b$ y de $a$ a $c$ , pero no caminos de $b$ a $c$ ni de $c$ a $b$ ). El grafo de ejemplo también tiene varios órdenes topológicos; un segundo orden topológico es el siguiente:

Un orden topológico puede no existir en absoluto. Solo existe si el grafo dirigido no contiene ciclos. En caso contrario hay una contradicción: si hay un ciclo que contiene a los vértices $a$ y $b$ , entonces $a$ necesita tener un índice menor que $b$ (porque se puede alcanzar $b$ desde $a$ ) y también uno mayor (porque se puede alcanzar $a$ desde $b$ ). El algoritmo descrito en este artículo también muestra por construcción que todo grafo dirigido acíclico contiene al menos un orden topológico.

Un problema habitual en el que aparece el orden topológico es el siguiente. Hay $n$ variables con valores desconocidos. Para algunas variables sabemos que una es menor que la otra. Hay que comprobar si estas restricciones son contradictorias y, si no lo son, emitir las variables en orden creciente (si hay varias respuestas posibles, emitir cualquiera de ellas). Es fácil notar que esto es exactamente el problema de encontrar el orden topológico de un grafo con $n$ vértices.

El algoritmo

Para resolver este problema, usaremos búsqueda en profundidad (DFS).

Supongamos que el grafo es acíclico. ¿Qué hace la búsqueda en profundidad?

Al empezar desde algún vértice $v$ , DFS intenta recorrer todas las aristas que salen de $v$ . Se detiene en las aristas cuyos extremos ya fueron visitados, y recorre el resto de las aristas y continúa de forma recursiva en sus extremos.

Así, para cuando termina la llamada $\text{dfs}(v)$ , todos los vértices alcanzables desde $v$ ya fueron visitados por la búsqueda, ya sea de forma directa (vía una arista) o indirecta.

Agregamos el vértice $v$ a una lista cuando terminamos $\text{dfs}(v)$ . Como todos los vértices alcanzables ya fueron visitados, ya estarán en la lista cuando agreguemos $v$ . Hacemos esto para cada vértice del grafo, con una o varias corridas de búsqueda en profundidad. Para cada arista dirigida $v \rightarrow u$ del grafo, $u$ aparecerá antes que $v$ en esta lista, porque $u$ es alcanzable desde $v$ . Así que si simplemente etiquetamos los vértices de esta lista con $n-1, n-2, \dots, 1, 0$ , habremos encontrado un orden topológico del grafo. En otras palabras, la lista representa el orden topológico invertido.

Estas explicaciones también se pueden presentar en términos de los tiempos de salida (exit times) del algoritmo DFS. El tiempo de salida del vértice $v$ es el instante en el que termina la llamada $\text{dfs}(v)$ (los tiempos se pueden numerar de $0$ a $n-1$ ). Es fácil entender que el tiempo de salida de cualquier vértice $v$ es siempre mayor que el tiempo de salida de cualquier vértice alcanzable desde él (porque fueron visitados o bien antes de la llamada $\text{dfs}(v)$ , o bien durante ella). Así, el orden topológico deseado son los vértices en orden descendente de sus tiempos de salida.

Implementación

Aquí hay una implementación que supone que el grafo es acíclico, es decir, que existe el orden topológico deseado. Si hace falta, se puede comprobar fácilmente que el grafo es acíclico, como se describe en el artículo sobre búsqueda en profundidad.


int n; // number of vertices
vector<vector<int>> adj; // adjacency list of graph
vector<bool> visited;
vector<int> ans;
 
void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
        }
    }
    ans.push_back(v);
}
 
void topological_sort() {
    visited.assign(n, false);
    ans.clear();
    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i);
        }
    }
    reverse(ans.begin(), ans.end());
}

La función principal de la solución es topological_sort, que inicializa las variables de DFS, lanza DFS y recibe la respuesta en el vector ans. Vale la pena notar que, cuando el grafo no es acíclico, el resultado de topological_sort sigue teniendo cierto sentido: si un vértice $u$ es alcanzable desde el vértice $v$ , pero no al revés, el vértice $v$ siempre aparece primero en el arreglo resultante. Esta propiedad de la implementación dada se usa en el algoritmo de Kosaraju para extraer las componentes fuertemente conexas y su orden topológico en un grafo dirigido con ciclos.

Orden topológico

El algoritmo

Implementación

Problemas de práctica