🥁 🔳 🤷🏿 Tri topologique ♟️ 🥟 👴🏽

Une traduction de l'article a été préparée avant le début du cours "Algorithmes pour les développeurs" .

Le tri topologique d'un graphe acyclique dirigé (Graphes acycliques dirigés, ci-après dénommé DAG) est un ordre linéaire des sommets pour lequel la condition suivante est remplie: pour chaque arête dirigée uv, le sommet u précède le sommet v dans l'ordre. Si le graphe n'est pas un DAG, le tri topologique n'est pas possible pour lui.

Par exemple, le tri topologique du graphique ci-dessous est «5 4 2 3 1 0». Il peut y avoir plusieurs tri topologiques pour un graphique. Par exemple, un autre tri topologique pour le même graphique est «4 5 2 3 1 0». Le premier sommet du tri topologique est toujours le sommet sans arêtes entrantes.

Tri topologique vs profonde de marche:

Quand aller en profondeur(Depth First Traversal, ci - après dénommé DFS ), nous émettons le sommet puis appelons récursivement DFS pour les sommets adjacents. Dans le tri topologique, nous devons afficher le sommet devant ses sommets adjacents. Par exemple, dans ce graphique, le sommet «5» doit être affiché avant le sommet «0» et, contrairement à DFS , le sommet «4» doit également être affiché avant le sommet «0». Cela distingue le tri topologique de DFS. Par exemple, la DFS du graphique ci-dessus est «5 2 3 1 0 4», mais ce n'est pas un tri topologique.

Recommandation: avant de passer à la mise en œuvre de l'algorithme, essayez d'abord de comprendre la tâche en pratique .

Algorithme de recherche de tri topologique.

Pour commencer, nous vous recommandons de vous familiariser avec cette implémentation DFS. On peut modifier DFS pour obtenir un tri topologique du graphe. En dfsnous commençons par un sommet approprié, que nous émettons d'abord, puis appelons récursivement DFS pour ses sommets adjacents. Dans le tri topologique, nous utilisons une pile temporaire. Un sommet n'est pas affiché immédiatement - d'abord, le tri topologique est appelé pour tous les sommets adjacents, puis le sommet est poussé sur la pile. Ce n'est qu'après avoir parcouru tous les sommets que le contenu de la pile s'affiche. Notez qu'un sommet n'est poussé sur la pile que lorsque tous les sommets adjacents (et leurs sommets adjacents, etc.) sont déjà sur la pile.

L'image ci-dessous est une illustration de l'approche ci-dessus:

:
(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
Les sommets 0 et 1 sont déjà visités. Plus d'appels récursifs
Pile 0 1 3 2 4
Étape 5:
Tri topologique (5), visité [5] = true Les
sommets 2 et 0 sont déjà visités. Plus d'appels récursifs
Pile 0 1 3 2 4 5
Étape 6:
Tirez tous les éléments de la pile de haut en bas

Voici les implémentations de tri topologique. Veuillez consulter l'implémentation DFT pour un graphique déconnecté et notez les différences entre le deuxième code qui y est donné et le code ci-dessous.

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)

Python

#  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

Difficulté dans le temps: l'algorithme ci-dessus est DFS avec une pile supplémentaire. Ainsi, la complexité temporelle est la même que celle de DFS, qui est O (V + E).

Remarque: vous pouvez également utiliser un vecteur au lieu d'une pile. Si vous utilisez un vecteur pour obtenir un tri topologique, vous devez afficher les éléments dans l'ordre inverse.

Application:

Le tri topologique est principalement utilisé pour planifier le travail à partir de dépendances données entre eux. En informatique, il est utilisé pour planifier des commandes, organiser des cellules pour calculer des formules lors du recalcul des valeurs de formule dans des feuilles de calcul, la synthèse logique, la détermination de l'ordre des tâches de compilation à effectuer dans les makefiles, la sérialisation des données et la résolution des dépendances symboliques dans les éditeurs de liens [ 2 ].

Articles Liés

Algorithme de Kahn pour le tri topologique : un autre algorithme O (V + E).
Tous les tri topologiques d'un graphe acyclique orienté

Références

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

Veuillez laisser un commentaire si vous trouvez une erreur ou si vous souhaitez partager des informations supplémentaires sur le sujet en discussion.

En savoir plus sur le cours.

Tri topologique

C ++

Java

Python

Articles Liés

Références

More articles: