Comment implémenter un algorithme de tri topologique en utilisant Python ?

Comment implémenter un algorithme de tri topologique en utilisant Python ?

Le tri topologique est un algorithme de tri en théorie des graphes utilisé pour trier les graphiques acycliques orientés (DAG). Dans le tri topologique, les nœuds du graphique représentent des tâches ou des événements, et les arêtes dirigées représentent les dépendances entre les tâches ou les événements. Dans le résultat trié, toutes les dépendances sont satisfaites et chaque nœud est classé après tous ses nœuds prédécesseurs.

L'implémentation de l'algorithme de tri topologique en Python peut être résolue en utilisant l'idée de recherche en profondeur d'abord (DFS). Voici un exemple de code spécifique :

from collections import defaultdict

class Graph:
    def __init__(self, num_vertices):
        self.graph = defaultdict(list)
        self.num_vertices = num_vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True

        for i in self.graph[v]:
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        stack.append(v)

    def topological_sort(self):
        visited = [False] * self.num_vertices
        stack = []

        for i in range(self.num_vertices):
            if visited[i] == False:
                self.topological_sort_util(i, visited, stack)

        sorted_list = []
        while stack:
            sorted_list.append(stack.pop())

        return sorted_list

# 测试代码
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

sorted_list = g.topological_sort()
print("拓扑排序结果：", sorted_list)

Le code ci-dessus définit d'abord une classe Graph, qui inclut des méthodes telles que l'ajout d'arêtes et le tri topologique. Lors du tri topologique, une recherche en profondeur d'abord est utilisée pour parcourir les nœuds du graphique. En utilisant une pile pour stocker les nœuds visités, vous pouvez enfin obtenir une liste de nœuds classés selon des règles d'ordre topologique.

Le code ci-dessus contient également un cas de test simple pour vérifier l'exactitude de l'algorithme de tri topologique. Dans ce cas de test, un graphe de taille 6 est défini et quelques nœuds et arêtes sont ajoutés. Enfin, imprimez la liste des nœuds triés topologiquement.

L'utilisation de Python pour implémenter l'algorithme de tri topologique peut facilement gérer les dépendances dans le graphique, ce qui est très utile pour des problèmes tels que la planification des tâches. En comprenant et en appliquant cet algorithme, les problèmes pratiques peuvent être mieux résolus. J'espère que cet article vous sera utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!