Algoritmo de ordenação topológica: Python, C++ Exemplo

O que é algoritmo de classificação topológica?

A classificação topológica também é conhecida como algoritmo de Kahn e é um algoritmo de classificação popular. Usando um gráfico direcionado como entrada, a classificação topológica classifica os nós para que cada um apareça antes daquele para o qual aponta.

This algorithm is applied on a DAG (Directed Acyclic Graph) so that each node appears in the ordered array before all other nodes that are pointed to by it. This algorithm follows some rules repeatedly until the sort is completed.

Para simplificar, veja o seguinte exemplo:

Gráfico direcionado

Here, we can see that “A” has no indegree. Indegree means the edge that points to a node. “B” and “C” have a pre-requisite of “A”, then “E” has a pre-requisite of “D” and “F” nodes. Some of the nodes are dependent on other nodes.

Here is another representation of the above Graph:

Dependência de cada nó (ordenação linear)

Assim, ao passarmos o DAG (Directed Acíclico Graph) para a ordenação topológica, ele nos dará um array com ordenação linear, onde o primeiro elemento não possui dependência.

Aqui estão as etapas para fazer isso:

Passo 1) Encontre o nó com zero arestas de entrada, um nó com zero graus.

Passo 2) Store that zero in-degree node in a Queue or Stack and remove the node from the Graph.

Passo 3) Then delete the outgoing edge from that node. This will decrement the in-degree count for the next node.

Topological ordering requires that the graph data structure will not have any cycle. A graph will be considered a DAG if it follows these requirements:

• Um ou mais nós com valor de indegree igual a zero.
• The graph does not contain any cycle.

As long as there are nodes in the Graph and the Graph is still a DAG, we will run the above three steps. Otherwise, the algorithm will fall into the cyclic dependency, and Kahn’s Algorithm will not be able to find a node with zero in-degree.

Como funciona a classificação topológica

Here, we will use “Kahn’s Algorithm” for the topological sort. Let us say we have the following Graph:

Here are the steps for Kahn’s Algorithm:

Passo 1) Calcule o grau de entrada ou borda de entrada de todos os nós no gráfico.

Observação:

• Indegree significa as arestas direcionadas apontando para o nó.
• Outdegree significa as arestas direcionadas que vêm de um nó.

Here is the indegree and outdegree of the above Graph:

Passo 2) Find the node with zero indegrees or zero incoming edges. The node with zero indegree means no edges are coming toward that node. Node “A” has zero indegrees, meaning there is no edge pointing to node “A”. So, we will do the following actions:

• Remove this node and its outdegree edges (outgoing edges).
• Coloque o nó na fila para pedido.
• Update the in-degree count of the neighbor node of “A”.

Passo 3) We need to find a node with an indegree value of zero. In this example, “B” and “C” have zero indegree. Here, we can take either of these two. Let us take “B” and delete it from the Graph. Then update the indegree values of other nodes. After performing these operations, our Graph and Queue will look like the following:

Passo 4) Node “C” has no incoming edge. So, we will remove node “C” from the Graph and push it into the Queue. We can also delete the edge that is outgoing from “C”. Now, our Graph will look like this:

Passo 5) We can see that nodes “D” and “F” have the indegree of zero. We will take a node and put it in the Queue. Let us take out “D” first. Then the indegree count for node “E” will be 1. Now, there will be no node from D to E. We need to do the same for node “F”, and our result will be like the following:

Passo 6) The indegree (ingoing edges) and outdegree (outgoing edges) of node “E” became zero. So, we have met all the pre-requisites for node “E”. Here, we will put “E” at the end of the Queue. So, we do not have any nodes left, and the algorithm ends here.

Apelido Code para ordenação topológica

Here is the pseudo-code for the topological sort while using Kahn’s Algorithm.

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 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

A classificação topológica também pode ser implementada usando o DFS (Profundidade primeira pesquisa) método. No entanto, essa abordagem é o método recursivo. O algoritmo de Kahn é mais eficiente que a abordagem DFS.

C++ Implementação de classificação 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();
}

saída

0       1       2       3       5       4

Python Implementação de classificação 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()

saída

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

Gráficos cíclicos do algoritmo de classificação topológica

A graph containing a cycle cannot be topologically ordered, as the cyclic Graph has the dependency in a cyclic manner. For example, check this Graph:

This Graph is not a DAG (Directed Acyclic Graph) because A, B, and C create a cycle. If you notice, there is no node with zero in-degree value. According to Kahn’s Algorithm, if we analyze the above Graph:

• Encontre um nó com zero graus de entrada (sem arestas de entrada).
• Remove that node from the Graph and push it to the Queue. However, in the above Graph, there is no node with zero in-degrees. Every node has an in-degree value greater than 0.
• Return an empty queue, as it could not find any node with zero in-degrees.

Podemos detectar ciclos usando a ordenação topológica com as seguintes etapas:

Passo 1) Execute a classificação topológica.

Passo 2) Calcule o número total de elementos na lista ordenada topologicamente.

Passo 3) If the number of elements equals the total number of vertices, then there is no cycle.

Passo 4) If it is not equal to the number of vertices, then there is at least one cycle in the given graph data structure.

Análise de complexidade de classificação topológica

There are two types of complexity in algorithms. They are:

1. Complexidade de tempo
2. Complexidade do Espaço

Essas complexidades são representadas por uma função que fornece uma complexidade geral.

Complexidade de tempo: All time complexity is the same for Topological Sorting. There are worst, average, and best-case scenarios for time complexity. The time complexity for topological Sorting is O(E + V), where E means the number of Edges in the Graph, and V means the number of vertices in the Graph.

Let us break through this complexity:

Passo 1) No início, calcularemos todos os graus. Para fazer isso, precisamos percorrer todas as arestas e, inicialmente, atribuiremos todos os graus dos vértices V a zero. Portanto, as etapas incrementais que completamos serão O(V+E).

Passo 2) Encontraremos o nó com valor de grau zero. Precisamos pesquisar a partir do número V do vértice. Assim, as etapas concluídas serão O (V).

Passo 3) Para cada nó com zero indegrees, removeremos esse nó e decrementaremos o indegree. Executar esta operação para todos os nós levará O(E).

Passo 4) Por fim, verificaremos se existe algum ciclo ou não. Verificaremos se o número total de elementos na matriz classificada é igual ao número total de nós. Vai levar O (1).

So, these were the individual time complexities for each step of the topological Sorting or topological ordering. We can say that the time complexity from the above calculation will be O(V + E); here, O means the complexity function.

Complexidade do espaço: We needed O(V) spaces for running the topological sorting algorithm. Here are the steps where we needed the space for the program:

• Tivemos que calcular todos os graus de nós presentes no gráfico. Como o Grafo possui um total de V nós, precisamos criar um array de tamanho V. Portanto, o espaço necessário foi O (V).
• Uma estrutura de dados Queue foi usada para armazenar o nó com grau zero. Removemos os nós com grau zero do gráfico original e os colocamos na fila. Para isso, o espaço necessário foi O (V).
• The array is named “order”, which stored the nodes in topological order. That also required O (V) espaços.

These were the individual space complexities. So, we need to maximize these spaces in the run time. Space complexity stands for O(V), where V means the number of the vertex in the Graph.

Aplicação de classificação topológica

There is a huge use for Topological Sorting. Here are some of them:

• It is used when an Operasistema ting precisa realizar a alocação de recursos.
• Finding a cycle in the Graph. We can validate if the Graph is a DAG or not with topological sort.
• Ordenação de frases nos aplicativos de preenchimento automático.
• It is used for detecting impasses.
• Different types of Scheduling or course scheduling use the topological sort.
• Resolvendo dependências. Por exemplo, se você tentar instalar um pacote, esse pacote também poderá precisar de outros pacotes. A ordenação topológica descobre todos os pacotes necessários para instalar o pacote atual.
• Linux usa a classificação topológica no “apt” para verificar a dependência dos pacotes.

Perguntas Frequentes