⚗️ 👸🏾 🔛 Clasificación topológica 🏳️ 🐍 🧖🏽

Se preparó una traducción del artículo antes del comienzo del curso "Algoritmos para desarrolladores" .

La clasificación topológica para un gráfico acíclico dirigido (Gráficos acíclicos dirigidos, en adelante denominados DAG) es un ordenamiento lineal de vértices para el cual se cumple la siguiente condición: para cada borde dirigido uv, el vértice u precede al vértice v en el ordenamiento. Si el gráfico no es un DAG, entonces no es posible la clasificación topológica.

Por ejemplo, la clasificación topológica del gráfico a continuación es "5 4 2 3 1 0". Puede haber varias clasificaciones topológicas para un gráfico. Por ejemplo, otra clasificación topológica para el mismo gráfico es "4 5 2 3 1 0". El primer vértice en la ordenación topológica es siempre el vértice sin bordes entrantes.

Clasificación topológica vs caminata profunda:

cuando se profundiza(Profundidad del primer recorrido, en adelante denominado DFS ) sacamos el vértice y luego recurrimos recursivamente a DFS para vértices adyacentes. En la ordenación topológica, debemos mostrar el vértice delante de sus vértices adyacentes. Por ejemplo, en este gráfico, el vértice "5" debe mostrarse antes del vértice "0" y, a diferencia de DFS , el vértice "4" también debe mostrarse antes del vértice "0". Esto distingue la clasificación topológica de DFS. Por ejemplo, el DFS de la columna anterior es "5 2 3 1 0 4", pero este no es un tipo topológico.

Recomendación: antes de pasar a la implementación del algoritmo, primero intente comprender la tarea en la práctica .

Algoritmo de búsqueda de clasificación topológica.

Para comenzar, le recomendamos que se familiarice con esta implementación de DFS. Podemos modificar DFS para que se obtenga una clasificación topológica del gráfico. En dfscomenzamos con un vértice adecuado, que primero sacamos, y luego llamamos recursivamente a DFS por sus vértices adyacentes. En la ordenación topológica, utilizamos una pila temporal. Un vértice no se muestra inmediatamente: primero, se llama la clasificación topológica para todos los vértices adyacentes, luego el vértice se empuja a la pila. Solo después de atravesar todos los vértices se muestra el contenido de la pila. Tenga en cuenta que un vértice se empuja a la pila solo cuando todos los vértices adyacentes (y sus vértices adyacentes, etc.) ya están en la pila.

La imagen a continuación es una ilustración del enfoque anterior:

:
(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
Los vértices 0 y 1 ya están visitados. No más llamadas recursivas
Pila 0 1 3 2 4
Paso 5:
Clasificación topológica (5), visitado [5] = verdadero Los
vértices 2 y 0 ya están visitados. No más llamadas recursivas
Pila 0 1 3 2 4 5
Paso 6:
Tire de todos los elementos de la pila de arriba a abajo

Las siguientes son implementaciones de ordenamiento topológico. Consulte la implementación de DFT para ver un gráfico desconectado y observe las diferencias entre el segundo código que se proporciona allí y el siguiente código.

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ón

#  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

Dificultad en el tiempo: el algoritmo anterior es DFS con una pila adicional. Por lo tanto, la complejidad temporal es la misma que la de DFS, que es O (V + E).

Nota: también puede usar un vector en lugar de una pila. Si usa un vector para obtener una ordenación topológica, debe generar los elementos en el orden inverso.

Solicitud:

La clasificación topológica se utiliza principalmente para programar el trabajo a partir de dependencias dadas entre ellos. En informática, se utiliza para planificar comandos, organizar celdas para calcular fórmulas al recalcular valores de fórmulas en hojas de cálculo, síntesis lógica, determinar el orden de las tareas de compilación que se realizarán en archivos MAKE, serialización de datos y resolver dependencias simbólicas en enlazadores [ 2 ].

Referencias

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

Por favor, deje un comentario si encuentra un error, o si desea compartir Información adicional sobre el tema en discusión.

Aprende más sobre el curso.

Clasificación topológica

C ++

Java

Pitón

Artículos relacionados

Referencias

More articles: