Orden topológico: Python, C++ Ejemplo de algoritmo

¿Qué es el algoritmo de clasificación topológica?

La clasificación topológica también se conoce como algoritmo de Kahn y es un algoritmo de clasificación popular. Utilizando un gráfico dirigido como entrada, Topological Sort ordena los nodos para que cada uno aparezca antes del que apunta.

Este algoritmo se aplica en un DAG (gráfico acíclico dirigido) para que cada nodo aparezca en la matriz ordenada antes de que todos los demás nodos apunten a él. Este algoritmo sigue algunas reglas repetidamente hasta que se completa la clasificación.

Para simplificar, observe el siguiente ejemplo:

Gráfico dirigido
Gráfico dirigido

Aquí podemos ver que "A" no tiene grado. Significa la arista que apunta a un nodo. "B" y "C" tienen un requisito previo de "A", luego "E" tiene un requisito previo de nodos "D" y "F". Algunos de los nodos dependen de otros nodos.

Aquí hay otra representación del gráfico anterior:

Dependencia de cada Nodo

Dependencia de cada nodo (Ordenamiento lineal)

Entonces, cuando pasamos el DAG (Gráfico acíclico dirigido) al ordenamiento topológico, nos dará una matriz con ordenamiento lineal, donde el primer elemento no tiene dependencia.

Algoritmo de clasificación topológica

Este ejemplo muestra un gráfico con un ciclo:

Estos son los pasos para hacer esto:

Paso 1) Encuentre el nodo con cero aristas entrantes, un nodo con cero grados.

Paso 2) Almacene ese nodo de grado a cero en una cola o pila y elimine el nodo del gráfico.

Paso 3) Luego elimine el borde saliente de ese nodo.

Esto disminuirá el recuento de grados para el siguiente nodo.

El orden topológico requiere que la estructura de datos del gráfico no tenga ningún ciclo.

Un gráfico se considerará DAG si cumple estos requisitos:

  • Uno o más nodos con un valor de grado cero.
  • El gráfico no contiene ningún ciclo.

Mientras haya nodos en el gráfico y el gráfico siga siendo DAG, ejecutaremos los tres pasos anteriores. De lo contrario, el algoritmo caerá en la dependencia cíclica y el algoritmo de Kahn no podrá encontrar un nodo con grado de entrada cero.

Cómo funciona la clasificación topológica

Aquí utilizaremos el “algoritmo de Kahn” para la ordenación topológica. Supongamos que tenemos el siguiente gráfico:

Trabajos de clasificación topológica

Estos son los pasos para el algoritmo de Kahn:

Paso 1) Calcule el grado interno o el borde entrante de todos los nodos en el gráfico.

Nota:

  • Engrado significa los bordes dirigidos que apuntan al nodo.
  • Grado exterior significa los bordes dirigidos que provienen de un nodo.

Aquí está el grado de entrada y salida del gráfico anterior:

Trabajos de clasificación topológica

Paso 2) Encuentre el nodo con cero grados de entrada o cero aristas entrantes.

El nodo con cero grados significa que no hay bordes que se acerquen a ese nodo. El nodo "A" tiene cero grados, lo que significa que no hay ningún borde que apunte al nodo "A".

Entonces, realizaremos las siguientes acciones:

  • Elimine este nodo y sus bordes exteriores (bordes salientes)
  • Coloque el nodo en la cola para realizar pedidos.
  • Actualice el recuento de grados del nodo vecino de "A".

Trabajos de clasificación topológica

Paso 3) Necesitamos encontrar un nodo con un valor de grado cero. En este ejemplo, "B" y "C" tienen un grado de entrada cero.

Aquí podemos tomar cualquiera de estos dos. Tomemos "B" y eliminémoslo del gráfico.

Luego actualice los valores de grado de otros nodos.

Luego de realizar estas operaciones nuestro Gráfico y Cola se verán así:

Trabajos de clasificación topológica

Paso 4) El nodo "C" no tiene borde entrante. Entonces, eliminaremos el nodo "C" del gráfico y lo insertaremos en la cola.

También podemos eliminar el borde que sale de “C”.

Ahora, nuestro gráfico se verá así:

Trabajos de clasificación topológica

Paso 5) Podemos ver que los nodos "D" y "F" tienen el grado de cero. Tomaremos un nodo y lo pondremos en la cola.

Primero eliminemos "D". Entonces el recuento de grados para el nodo "E" será 1. Ahora, no habrá ningún nodo de D a E.

Necesitamos hacer lo mismo para el nodo “F”, nuestro resultado será como el siguiente:

Trabajos de clasificación topológica

Paso 6) El grado de entrada (bordes de entrada) y el grado de salida (bordes de salida) del nodo "E" se volvieron cero. Entonces, hemos cumplido todos los requisitos previos para el nodo "E".

Aquí, pondremos “E” al final de la cola. Entonces, no nos quedan nodos, por lo que el algoritmo termina aquí.

Trabajos de clasificación topológica

Pseudocódigo para clasificación topológica

Aquí está el pseudocódigo para la clasificación topológica utilizando el algoritmo de Kahn.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

La clasificación topológica también se puede implementar utilizando DFS (Primera búsqueda en profundidad) método. Sin embargo, ese enfoque es el método recursivo. El algoritmo de Kahn es más eficiente que el enfoque DFS.

C++ Implementación de clasificación topológica

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

Salida

0       1       2       3       5       4

Python Implementación de clasificación topológica

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

Salida

[0, 1, 2, 3, 5, 4]

Gráficos cíclicos del algoritmo de clasificación topológica

Un gráfico que contiene un ciclo no se puede ordenar topológicamente. Como el gráfico cíclico tiene la dependencia de forma cíclica.

Por ejemplo, consulte este gráfico:

Gráficos cíclicos del algoritmo de clasificación topológica

Este gráfico no es DAG (gráfico acíclico dirigido) porque A, B y C crean un ciclo. Si te fijas, no hay ningún nodo con valor de grado cero.

Según el algoritmo de Kahn, si analizamos el gráfico anterior:

  • Encuentre un nodo con cero grados (sin aristas entrantes).
  • Elimine ese nodo del gráfico y empújelo a la cola.
    Sin embargo, en el gráfico anterior, no hay ningún nodo con cero en grados. Cada nodo tiene un valor de grado de entrada mayor que 0.
  • Devuelve una cola vacía, ya que no pudo encontrar ningún nodo con cero en grados.

Podemos detectar ciclos utilizando el ordenamiento topológico con los siguientes pasos:

Paso 1) Realizar clasificación topológica.

Paso 2) Calcule el número total de elementos en la lista ordenada topológicamente.

Paso 3) Si el número de elementos es igual al número total de vértices, entonces no hay ciclo.

Paso 4) Si no es igual al número de vértices, entonces hay al menos un ciclo en la estructura de datos del gráfico dada.

Análisis de complejidad de la ordenación topológica

Hay dos tipos de complejidad en los algoritmos. Son

  1. Complejidad de tiempo
  2. Complejidad espacial

Estas complejidades se representan con una función que proporciona una complejidad general.

Complejidad del tiempo: La complejidad temporal es la misma para la ordenación topológica. Existen escenarios de complejidad temporal peores, promedio y mejores.

La complejidad temporal para la ordenación topológica es O(E + V), aquí, E significa el número de aristas en el gráfico y V significa el número de vértices en el gráfico.

Vamos a superar esta complejidad:

Paso 1) Al principio calcularemos todos los grados. Para hacer eso, necesitamos pasar por todos los bordes e inicialmente, asignaremos todos los grados de los vértices V a cero. Entonces, los pasos incrementales que completemos serán O (V + E).

Paso 2) Encontraremos el nodo con valor de grado cero. Necesitamos buscar desde el número V del vértice. Entonces, los pasos completados serán O (V).

Paso 3) Para cada nodo con cero grados de entrada, eliminaremos ese nodo y disminuiremos el grado de entrada. Realizar esta operación para todos los nodos llevará O(E).

Paso 4) Finalmente comprobaremos si hay algún ciclo o no. Comprobaremos si el número total de elementos en la matriz ordenada es igual al número total de nodos. Tomará O (1).

Por lo tanto, estas fueron las complejidades temporales individuales para cada paso de la clasificación topológica o el ordenamiento topológico. Podemos decir que la complejidad temporal del cálculo anterior será O( V + E ); aquí, O significa la función de complejidad.

Complejidad espacial: Necesitábamos espacios O(V) para ejecutar el algoritmo de clasificación topológica.

Estos son los pasos donde necesitábamos espacio para el programa:

  • Tuvimos que calcular todos los grados de los nodos presentes en el gráfico. Como el gráfico tiene un total de V nodos, necesitamos crear una matriz de tamaño V. Entonces, el espacio requerido fue O (V).
  • Se utilizó una estructura de datos de cola para almacenar el nodo con grado cero. Eliminamos los nodos con grado cero del gráfico original y los colocamos en la cola. Para ello se preparó el espacio necesario O (V).
  • La matriz se denomina "orden". Eso almacenó los nodos en orden topológico. Eso también requirió O (V) espacios

Éstas eran las complejidades espaciales individuales, por lo que debemos maximizar estos espacios en el tiempo de ejecución.

La complejidad espacial se representa por O(V), donde V significa el número de vértices en el gráfico.

Aplicación de ordenación topológica

La clasificación topológica tiene un gran uso. Éstos son algunos de ellos:

  • Se utiliza cuando Operasistema de ting necesita realizar la asignación de recursos.
  • Encontrar un ciclo en el gráfico. Podemos validar si el Gráfico es DAG o no con ordenación topológica.
  • Orden de oraciones en las aplicaciones de autocompletar.
  • Se utiliza para detectar puntos muertos.
  • Diferentes tipos de programación o programación de cursos utilizan el tipo topológico.
  • Resolviendo dependencias. Por ejemplo, si intenta instalar un paquete, es posible que ese paquete también necesite otros paquetes. El ordenamiento topológico descubre todos los paquetes necesarios para instalar el paquete actual.
  • Linux utiliza la clasificación topológica en "apt" para verificar la dependencia de los paquetes.