Algorithme de tri topologique : Python, C++ Exemple

Qu’est-ce que l’algorithme de tri topologique ?

Le tri topologique est également connu sous le nom d'algorithme de Kahn et est un algorithme de tri populaire. En utilisant un graphe orienté comme entrée, Topological Sort trie les nœuds afin que chacun apparaisse avant celui vers lequel il pointe.

Cet algorithme est appliqué à un DAG (graphe acyclique orienté) de sorte que chaque nœud apparaisse dans le tableau trié avant tous les autres nœuds qu'il référence. Cet algorithme suit certaines règles de manière itérative jusqu'à ce que le tri soit terminé.

Pour simplifier, regardez l'exemple suivant :

Graphique dirigé

Ici, on constate que « A » n'a pas de degré entrant. Le degré entrant correspond au nombre d'arêtes pointant vers un nœud. « B » et « C » dépendent de « A », et « E » dépend de « D » et « F ». Certains nœuds sont dépendants d'autres.

Voici une autre représentation du graphique ci-dessus :

Dépendance de chaque nœud (Ordre Linéaire)

Ainsi, lorsque nous passons le DAG (Directed Acyclic Graph) au tri topologique, cela nous donnera un tableau avec un ordre linéaire, où le premier élément n'a aucune dépendance.

Voici les étapes pour ce faire:

Étape 1) Trouvez le nœud avec zéro arête entrante, un nœud avec zéro degré.

Étape 2) Stockez ce nœud de degré entrant nul dans une file d'attente ou une pile et supprimez-le du graphe.

Étape 3) Supprimez ensuite l'arête sortante de ce nœud. Cela décrémentera le degré entrant du nœud suivant.

L'ordre topologique exige que la structure de données du graphe ne contienne aucun cycle. Un graphe est considéré comme un DAG s'il remplit les conditions suivantes :

• Un ou plusieurs nœuds avec une valeur indegree de zéro.
• Le graphique ne contient aucun cycle.

Tant que le graphe contient des nœuds et reste un graphe acyclique orienté (DAG), nous exécuterons les trois étapes précédentes. Dans le cas contraire, l'algorithme rencontrera une dépendance cyclique et l'algorithme de Kahn ne pourra pas trouver de nœud de degré entrant nul.

Comment fonctionne le tri topologique

Nous utiliserons ici l'algorithme de Kahn pour le tri topologique. Supposons que nous ayons le graphe suivant :

Voici les étapes de l'algorithme de Kahn :

Étape 1) Calculez le degré entrant ou le bord entrant de tous les nœuds du graphique.

À noter:

• Indegree signifie les bords dirigés pointant vers le nœud.
• Outdegree désigne les arêtes dirigées provenant d’un nœud.

Voici le degré entrant et le degré sortant du graphique ci-dessus :

Étape 2) Trouvez le nœud dont le degré entrant est nul (ou qui ne reçoit aucune arête entrante). Un nœud de degré entrant nul ne reçoit aucune arête. Le nœud « A » a un degré entrant nul, ce qui signifie qu'aucune arête ne pointe vers lui. Nous allons donc effectuer les actions suivantes :

• Supprimez ce nœud et ses arêtes sortantes.
• Placez le nœud dans la file d'attente pour la commande.
• Mettre à jour le nombre de degrés entrants du nœud voisin de « A ».

Étape 3) Nous devons trouver un nœud dont le degré entrant est nul. Dans cet exemple, « B » et « C » ont un degré entrant nul. Nous pouvons donc choisir l'un ou l'autre. Prenons « B » et supprimons-le du graphe. Mettons ensuite à jour les degrés entrants des autres nœuds. Après ces opérations, notre graphe et notre file d'attente ressembleront à ceci :

Étape 4) Le nœud « C » n'a pas d'arête entrante. Nous allons donc le supprimer du graphe et l'ajouter à la file d'attente. Nous pouvons également supprimer l'arête sortante de « C ». Notre graphe ressemblera alors à ceci :

Étape 5) On constate que les nœuds « D » et « F » ont un degré entrant nul. On va ajouter un nœud à la file d'attente. Commençons par retirer « D ». Le degré entrant du nœud « E » sera alors de 1. Il n'y aura donc aucun nœud de D vers E. On doit procéder de la même manière pour le nœud « F », et le résultat sera le suivant :

Étape 6) Le degré entrant (arêtes entrantes) et le degré sortant (arêtes sortantes) du nœud « E » sont désormais nuls. Nous avons donc satisfait à toutes les conditions préalables pour le nœud « E ». Nous allons maintenant placer « E » à la fin de la file d'attente. Il ne reste donc plus aucun nœud et l'algorithme se termine.

Faux Code pour le tri topologique

Voici le pseudo-code du tri topologique utilisant l'algorithme 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 0 indegree present:
    topological_list.append(node)
    G.remove(node)
    // Update indegree of present nodes
  return topological_list

Le tri topologique peut également être implémenté à l'aide du DFS (Première recherche en profondeur) méthode. Cependant, cette approche est la méthode récursive. L'algorithme de Kahn est plus efficace que l'approche DFS.

C++ Implémentation du tri topologique

#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();
}

Sortie

0       1       2       3       5       4

Python Implémentation du tri topologique

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()

Sortie

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

Graphiques cycliques de l'algorithme de tri topologique

Un graphe contenant un cycle ne peut pas être topologiquement ordonné, car les dépendances dans un graphe cyclique sont cycliques. Par exemple, examinez ce graphe :

Ce graphe n'est pas un DAG (graphe acyclique orienté) car A, B et C forment un cycle. On remarque qu'il n'y a pas de nœud de degré entrant nul. Selon l'algorithme de Kahn, si l'on analyse le graphe ci-dessus :

• Trouvez un nœud avec zéro degré (pas de bords entrants).
• Supprimez ce nœud du graphe et ajoutez-le à la file d'attente. Cependant, dans le graphe ci-dessus, aucun nœud n'a un degré entrant nul. Chaque nœud a un degré entrant supérieur à 0.
• Renvoie une file d'attente vide, car aucun nœud avec un degré entrant nul n'a été trouvé.

Nous pouvons détecter les cycles en utilisant l'ordre topologique avec les étapes suivantes :

Étape 1) Effectuez un tri topologique.

Étape 2) Calculez le nombre total d’éléments dans la liste triée topologiquement.

Étape 3) Si le nombre d'éléments est égal au nombre total de sommets, alors il n'y a pas de cycle.

Étape 4) Si ce nombre n'est pas égal au nombre de sommets, alors il existe au moins un cycle dans la structure de données du graphe donné.

Analyse de complexité du tri topologique

Il existe deux types de complexité dans les algorithmes. Ce sont :

1. Complexité temporelle
2. Complexité spatiale

Ces complexités sont représentées par une fonction qui fournit une complexité générale.

Complexité temporelle: La complexité temporelle du tri topologique est identique dans tous les cas. On distingue trois scénarios : le pire, le moyen et le meilleur. La complexité temporelle du tri topologique est O(E + V), où E représente le nombre d'arêtes du graphe et V le nombre de sommets.

Essayons de surmonter cette complexité :

Étape 1) Au début, nous calculerons tous les degrés. Pour ce faire, nous devons parcourir toutes les arêtes et, dans un premier temps, nous attribuerons à zéro tous les degrés du sommet V. Ainsi, les étapes progressives que nous accomplirons seront O(V+T).

Étape 2) Nous trouverons le nœud avec une valeur de degré nulle. Nous devons rechercher à partir du numéro V du sommet. Ainsi, les étapes complétées seront O (V).

Étape 3) Pour chaque nœud avec zéro degré, nous supprimerons ce nœud et décrémenterons le degré. Effectuer cette opération pour tous les nœuds prendra O(E).

Étape 4) Enfin, nous vérifierons s'il y a un cycle ou non. Nous vérifierons si le nombre total d'éléments dans le tableau trié est égal au nombre total de nœuds. Ça prendra O (1).

Voici donc les complexités temporelles individuelles pour chaque étape du tri topologique. On peut dire que la complexité temporelle du calcul ci-dessus est O(V + E), où O représente la fonction de complexité.

Complexité de l'espace: Nous avions besoin d'un espace mémoire O(V) pour exécuter l'algorithme de tri topologique. Voici les étapes du programme qui nécessitaient cet espace :

• Nous avons dû calculer tous les degrés de nœuds présents dans le graphique. Comme le graphique a un total de nœuds V, nous devons créer un tableau de taille V. Ainsi, l'espace requis était O (V).
• Une structure de données Queue a été utilisée pour stocker le nœud avec un degré nul. Nous avons supprimé les nœuds avec un degré nul du graphique d'origine et les avons placés dans la file d'attente. Pour cela, l'espace requis était O (V).
• Le tableau est nommé « order », et il stocke les nœuds dans l'ordre topologique. Cela nécessitait également O (V) les espaces.

Il s'agissait des complexités spatiales individuelles. Il faut donc maximiser ces espaces lors de l'exécution. La complexité spatiale est notée O(V), où V représente le nombre de sommets du graphe.

Application du tri topologique

Le tri topologique a de nombreuses applications. En voici quelques-unes :

• Il est utilisé lorsqu'un Système exploitation doit effectuer l’allocation des ressources.
• Recherche d'un cycle dans le graphe. On peut vérifier si le graphe est un DAG ou non grâce au tri topologique.
• Ordre des phrases dans les applications de saisie semi-automatique.
• Il est utilisé pour détecter impasses.
• Différents types de planification ou d'ordonnancement de cours utilisent le tri topologique.
• Résoudre les dépendances. Par exemple, si vous essayez d'installer un package, ce package peut également nécessiter d'autres packages. L'ordre topologique découvre tous les packages nécessaires pour installer le package actuel.
• Linux utilise le tri topologique dans « apt » pour vérifier la dépendance des packages.

FAQ