⚰️ 🙋🏼 🗝️ Classificação topológica 🗂️ ☣️ 👨🏼

Uma tradução do artigo foi preparada antes do início do curso "Algoritmos para desenvolvedores" .

A classificação topológica para um gráfico acíclico direcionado (Gráficos Acíclicos Direcionados, doravante referido como DAG) é uma ordenação linear de vértices para os quais a seguinte condição é válida: para cada aresta direcionada uv, o vértice u precede o vértice v na ordenação. Se o gráfico não for um DAG, a classificação topológica não será possível.

Por exemplo, a classificação topológica do gráfico abaixo é "5 4 2 3 1 0". Pode haver várias classificações topológicas para um gráfico. Por exemplo, outra classificação topológica para o mesmo gráfico é "4 5 2 3 1 0". O primeiro vértice na classificação topológica é sempre o vértice sem arestas recebidas.

Classificação topológica versus caminhada profunda:

ao ir fundo(Profundidade Primeiro Traversal, daqui em diante referido como DFS ), produzimos o vértice e depois chamamos recursivamente DFS para vértices adjacentes. Na classificação topológica, precisamos exibir o vértice na frente de seus vértices adjacentes. Por exemplo, neste gráfico, o vértice "5" deve ser exibido antes do vértice "0" e, ao contrário do DFS , o vértice "4" também deve ser exibido antes do vértice "0". Isso distingue a classificação topológica do DFS. Por exemplo, o DFS da coluna acima é "5 2 3 1 0 4", mas essa não é uma classificação topológica.

Recomendação: antes de prosseguir para a implementação do algoritmo, primeiro tente entender a tarefa na prática .

Algoritmo de pesquisa de classificação topológica.

Para começar, recomendamos que você se familiarize com esta implementação do DFS. Podemos modificar o DFS para obter uma classificação topológica do gráfico. Em dfscomeçamos com um vértice adequado, que primeiro produzimos e depois chamamos recursivamente DFS para seus vértices adjacentes. Na classificação topológica, usamos uma pilha temporária. Um vértice não é exibido imediatamente - primeiro, a classificação topológica é chamada para todos os vértices adjacentes, depois o vértice é empurrado para a pilha. Somente depois de percorrer todos os vértices é que o conteúdo da pilha é exibido. Observe que um vértice é empurrado para a pilha somente quando todos os vértices adjacentes (e seus vértices adjacentes, etc.) já estão na pilha.

A imagem abaixo é uma ilustração da abordagem acima:

:
(G)
0 →
1→
2 → 3
3 → 1
4 → 0, 1
5 → 2, 0

1:
(0), visited[0] = true
. .
0
2:
(1), visited[1] = true
. .
0 1
3:
(2),, visited[2] = true
(3),, visited[3] = true
1 .
0 1 3 2
4:
(4),, visited[4] = true
Os vértices 0 e 1 já estão visitados. Não há mais chamadas recursivas
Pilha 0 1 3 2 4
Etapa 5: Classificação
topológica (5), visitada [5] = true
Os vértices 2 e 0 já foram visitados. Não há mais chamadas recursivas
Pilha 0 1 3 2 4 5
Etapa 6:
Puxe todos os itens da pilha de cima para baixo

A seguir estão implementações de classificação topológica. Verifique a implementação da DFT para obter um gráfico desconectado e observe as diferenças entre o segundo código fornecido lá e o código abaixo.

C ++

//   C++     DAG
 
#include<iostream>
#include <list>
#include <stack>
using namespace std;
  
//    
class Graph
{
    int V;	//  
  
    //    ,   
    list<int> *adj;
  
    // ,  topologicalSort
    void topologicalSortUtil(int v, bool visited[], stack<int> &Stack);
public:
    Graph(int V);   // 
  
     //      
    void addEdge(int v, int w);
  
    //    
    void topologicalSort();
};
  
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
  
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
  
//  ,  topologicalSort
void Graph::topologicalSortUtil(int v, bool visited[], 
                                stack<int> &Stack)
{
    //     
    visited[v] = true;
  
    //       
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSortUtil(*i, visited, Stack);
  
    //       
    Stack.push(v);
}
  
//     . 
//   topologicalSortUtil()
void Graph::topologicalSort()
{
    stack<int> Stack;
  
    //     
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
  
    //     
    //       
    for (int i = 0; i < V; i++)
      if (visited[i] == false)
        topologicalSortUtil(i, visited, Stack);
  
    //   
    while (Stack.empty() == false)
    {
        cout << Stack.top() << " ";
        Stack.pop();
    }
}
  
//    
int main()
{
    //  ,    
    Graph g(6);
    g.addEdge(5, 2);
    g.addEdge(5, 0);
    g.addEdge(4, 0);
    g.addEdge(4, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
  
    cout << "Following is a Topological Sort of the given graph \n";
    g.topologicalSort();
  
    return 0;
}

Java

//   Java    
import java.io.*;
import java.util.*;
  
//          
class Graph
{
    private int V;   //  
    private LinkedList<Integer> adj[]; //  
  
    // 
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
  
    //      
    void addEdge(int v,int w) { adj[v].add(w); }
  
    //  ,  topologicalSort
    void topologicalSortUtil(int v, boolean visited[],
                             Stack stack)
    {
        //      
        visited[v] = true;
        Integer i;
  
        //       
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }
  
        //       
        stack.push(new Integer(v));
    }
  
    //     .
    //   topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();
  
        //     
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;
  
        //    
        //       
        for (int i = 0; i < V; i++)
            if (visited[i] == false)
                topologicalSortUtil(i, visited, stack);
  
        //   
        while (stack.empty()==false)
            System.out.print(stack.pop() + " ");
    }
  
    //   
    public static void main(String args[])
    {
        //  ,    
        Graph g = new Graph(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);
  
        System.out.println("Following is a Topological " +
                           "sort of the given graph");
        g.topologicalSort();
    }
}
//      (Aakash Hasija)

Pitão

#  Python       DAG   import defaultdict
  
#   
class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list) #dictionary containing adjacency List
        self.V = vertices #No. of vertices
  
    #      
    def addEdge(self,u,v):
        self.graph[u].append(v)
  
    #  ,  topologicalSort
    def topologicalSortUtil(self,v,visited,stack):
  
        #     
        visited[v] = True
  
        #       
        for i in self.graph[v]:
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #       
        stack.insert(0,v)
  
    #     . 
    #   topologicalSortUtil()
    def topologicalSort(self):
        #     
        visited = [False]*self.V
        stack =[]
  
        #    
        #       
        for i in range(self.V):
            if visited[i] == False:
                self.topologicalSortUtil(i,visited,stack)
  
        #   
        print stack
  
g= Graph(6)
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
  
print "Following is a Topological Sort of the given graph"
g.topologicalSort()
#     (Neelam Yadav)

<b>:</b>
Following is a Topological Sort of the given graph
5 4 2 3 1 0

Dificuldade no tempo: o algoritmo acima é DFS com uma pilha adicional. Assim, a complexidade do tempo é a mesma do DFS, que é O (V + E).

Nota: você também pode usar um vetor em vez de uma pilha. Se você usar um vetor para obter a classificação topológica, precisará gerar os elementos na ordem inversa.

Inscrição:

A classificação topológica é usada principalmente para programar o trabalho a partir de determinadas dependências entre eles. Na ciência da computação, é usado para planejar comandos, organizar células para calcular fórmulas ao recalcular os valores das fórmulas em planilhas, síntese lógica, determinar a ordem das tarefas de compilação a serem executadas em makefiles, serialização de dados e resolver dependências simbólicas nos vinculadores [ 2 ].

Referências

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/topoSort.htm
http://en.wikipedia.org/wiki/Topological_sorting

Por favor, deixe um comentário se encontrar algum erro ou se quiser compartilhar informações adicionais sobre o tópico em discussão.

Saiba mais sobre o curso.

Classificação topológica

C ++

Java

Pitão

Artigos relacionados

Referências

More articles: