OIA-Wiki

En este post, trataremos el problema de, dado un grafo dirigido, ubicar todos los nodos en una lista de manera que no exista una arista que vaya desde un nodo que está más atrás en la lista a uno de más adelante. Por ejemplo, si tenemos el siguiente grafo:

Un orden posible podría ser $\{1,0,2,4,5,3\}$.

Se ve que en este grafo no hay ningún ciclo, y en general, puede demostrarse fácilmente que si hay un ciclo en el grafo, la lista ordenada será imposible de crear.

La situación típica relacionada a este problema es la situación de las correlatividades en las materias de la facultad, donde por ejemplo no se puede rendir “Análisis 2” antes de “Análisis 1”, entonces pondríamos una arista de “Análisis 1” a “Análisis 2”; las correlatividades en tareas, como por ejemplo vestirse. No se puede poner las zapatillas antes de las medias, o el pantalón antes del calzoncillo (excepto Superman). Entonces ponemos una arista desde una prenda hacia otra prenda que sí o sí debe ser puesta después, y un ordenamiento topológico nos dirá cómo vestirnos.

Otra situación es en un código, donde si una función necesita de otra, esta otra debe ser programada antes.

En fin, hay muchas situaciones en las que este ordenamiento es importante, y vamos a ver cómo podemos encontrar un posible ordenamiento.

En estos casos, la arista $u \rightarrow v$ indica “$u$ debe ir antes que $v$”, y entonces armaremos la lista ordenada de manera de no contradecir a ninguna arista.

Nuestro grafo debe ser dirigido, y además no debe tener ciclo. Este tipo de grafos se conoce como DAG, “directed acyclic graph”.

En general, el ordenamiento no va a ser único. Por ejemplo, en el grafo de arriba otro posible sería $\{0, 2, 1, 4, 5, 3\}$.

Pensemos cuándo va a ser único.

Si hay una arista de $u$ a $w$, y otra de $v$ a $w$, sabemos que $u$ y $v$ van antes que $w$, pero todavía no sabemos nada del orden entre $u$ y $v$. Entonces, o bien debe haber una arista entre ellas que indique quién debe ir antes, o bien debe haber algún camino que conecte $u$ con $v$, con el cual sabremos quién debe ir antes. Entonces el ordenamiento será único siempre y cuando, para cada par de nodos, exista al menos un camino entre ellos.

Lo que haremos, será guardar información de cuántas aristas llegan a cada nodo. Si un nodo no tiene ninguna arista que le llega, entonces puedo agregarlo al final de la lista, ya que no importa a quién ponga después, no habrá una arista que llegue a él de alguien de más adelante. Al poner un nodo en la lista, miro a sus vecinos, y le bajo uno a la cantidad de aristas que le llegan, ya que la restricción que me indicaba esa arista ya está cumplida y deja de importar una vez puesto el nodo. Si al disminuir la cantidad de aristas entrantes a un nodo, este nodo queda con $0$ aristas entrantes, significa que ya cumplí todas las restricciones que involucraban a este nodo, entonces puede agregarlo a la lista.

toposort.cpp

int main(){
    vector< vector<int> > grafo;
    vector<int> entrantes;
    // entrada del grafo, donde las aristas son dirigidas (importa el orden). Digamos que hay n nodos
    // entrantes[i] me dice cuántas aristas entran al nodo i
    queue<int> q;
    vector<int> toposort;
    for(int i=0; i<n; i++){
        if(entrantes[i]==0){ //no tengo ninguna restricción, puede ir al principio
            q.push(i);
        }
    }
    while(!q.empty()){
        int nodoActual = q.front();
        q.pop();
        toposort.push_back(nodoActual); //si lo agregue es porque no tenia mas restricciones
        for(int i=0; i<grafo[nodoActual].size(); i++){
            int vecino=grafo[nodoActual][i];
            entrantes[vecino]--;
            if(entrantes[vecino]==0){
                q.push(vecino);
            }
        }
    }
    if(toposort.size()<n){ // si hay un ciclo, nunca voy a agregar a los nodos del ciclo porque ninguno va a ser el primero en quedarse sin aristas entrantes
        cout<<"ERROR, EL GRAFO TIENE UN CICLO"<<endl;
    }else{
        for(int i=0; i<n; i++){
            cout<<toposort[i]<<" ";
        }
    }
}

Cada nodo lo agrego una vez en la queue, y cada arista de cada nodo la miro una vez, entonces la complejidad es $\large O(V+E)$.

Toposort, simplemente para practicar codear desde cero el algoritmo, sin nada raro.

Que queden ordenados alfabéticamente

Ranking