Implémentation Python d'un exemple de code de tri topologique d'un graphe acyclique dirigé

Le contenu de cet article concerne l'exemple de code de tri topologique d'un graphe acyclique dirigé en Python. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Tri topologique d'un graphe acyclique dirigé Python

La définition officielle du tri topologique est la suivante : à partir d'un ordre partiel sur un certain ensemble pour obtenir l'ordre le plus élevé sur L'ensembleUn ordre total de,Cette opération est appelée tri topologique. Personnellement, je pense que le tri topologique est une méthode de tri qui introduit le concept de degré dans la méthode de traversée de base des graphiques et l'implémente autour du degré. Le tri topologique est similaire au tri des règles mro dans l'héritage multiple Python. Si vous souhaitez étudier en profondeur les règles mro de l'algorithme C3, autant vous renseigner sur le tri topologique des DAG (Directed Acyclic Graph).

En degré : fait référence à la somme du nombre de points pointés vers un nœud dans le graphe orienté.
Graphique acyclique dirigé : DAG en abrégé Si vous êtes familier avec l'apprentissage automatique, vous le serez certainement. Les familiers avec DAG, tels que ANN, DNN, CNN, etc. sont tous des modèles DAG typiques. Je ne développerai pas trop ces modèles ici. Ceux qui sont intéressés peuvent apprendre par eux-mêmes.

Prenons un graphe acyclique orienté comme exemple, comme indiqué ci-dessous :

# 定义图结构graph = {
    "A": ["B","C"],
    "B": ["D","E"],
    "C": ["D","E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],}

Comme indiqué dans
A L'élément pointé par C
B est D, l'élément pointé par E
C est D, l'élément pointé par E
D est F
E, et l'élément pointé par E est F
L'élément pointé par F est vide
, c'est-à-dire que le degré d'entrée de A est 0, le degré d'entrée de B est de 1, le degré d'entrée de C est de 1, le degré d'entrée de D est 2 et le degré entrant de E est 2. Le degré entrant de F est 2
Dans le tri topologique du DAG, un point avec un degré entrant de 0 est sélectionné et ajouté à la file d'attente topologique à chaque fois , puis toutes les arêtes connectées à ce point sont supprimées.
Trouvez d'abord le point A avec un degré entrant de 0, retirez A de la file d'attente, ajoutez-le au résultat et supprimez les pointeurs liés à A. Autrement dit, les degrés entrants de B et C sont réduits de 1 à 0 et B, C est ajouté à la file d'attente, puis le nœud avec un degré d'entrée de 0 est retiré de la tête de la file d'attente, et ainsi de suite, et enfin le résultat est sorti pour terminer le tri topologique de le DAG.

def TopologicalSort(G):
    # 创建入度字典
    in_degrees = dict((u, 0) for u in G)
    # 获取每个节点的入度
    for u in G:
        for v in G[u]:
            in_degrees[v] += 1
    # 使用列表作为队列并将入度为0的添加到队列中
    Q = [u for u in G if in_degrees[u] == 0]
    res = []
    # 当队列中有元素时执行
    while Q:
        # 从队列首部取出元素
        u = Q.pop()
        # 将取出的元素存入结果中
        res.append(u)
        # 移除与取出元素相关的指向，即将所有与取出元素相关的元素的入度减少1
        for v in G[u]:
            in_degrees[v] -= 1
            # 若被移除指向的元素入度为0，则添加到队列中
            if in_degrees[v] == 0:
                Q.append(v)
    return resprint(TopologicalSort(graph))

Résultats de sortie :

['A', 'C', 'B', 'E', 'D', 'F']

Les résultats de sortie du code sont cohérents avec l'analyse ci-dessus

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!