Python-Implementierung eines topologischen Sortiercodebeispiels für einen gerichteten azyklischen Graphen

Der Inhalt dieses Artikels befasst sich mit dem Codebeispiel für die topologische Sortierung eines gerichteten azyklischen Graphen. Ich hoffe, dass er für Sie hilfreich ist.

Topologische Sortierung von Python-gerichteten azyklischen Graphen

Die offizielle Definition der topologischen Sortierung lautet: Von einer Teilordnung auf einer Menge, um die topologische Ordnung auf der zu erhalten Stellen Sie eine Gesamtreihenfolge ein. Dieser Vorgang wird als topologische Sortierung bezeichnet. Ich persönlich glaube, dass die topologische Sortierung eine Sortiermethode ist, die das Konzept der In-Grade-Methode in die grundlegende Traversierungsmethode von Graphen einführt und sie um die Topologische Sortierung herum implementiert, die der Sortierung von MRO-Regeln in der Python-Mehrfachvererbung ähnelt Wenn Sie die MRO-Regeln des C3-Algorithmus eingehend studieren möchten, können Sie sich auch über die topologische Sortierung von DAG (Directed Asymmetric Graph) informieren.

In-Grad: Bezieht sich auf die Summe der Punkte, die auf einen Knoten im gerichteten Graphen zeigen.
Gerichteter azyklischer Graph: Gerichteter azyklischer Graph, kurz DAG. Wenn Sie mit maschinellem Lernen vertraut sind, Sie werden auf jeden Fall mit DAG vertraut sein, da ANN, DNN, CNN usw. alles typische DAG-Modelle sind. Ich werde hier nicht zu viel auf diese Modelle eingehen. Interessierte können es selbst lernen.

Nehmen Sie einen gerichteten azyklischen Graphen als Beispiel, wie unten gezeigt:

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

Wie in der Abbildung gezeigt,
A zeigt Das Element, auf das C
B zeigt, ist D, das Element, auf das E
C zeigt, ist D, und das Element, auf das E
D zeigt, ist F
Das Element, auf das E zeigt, ist F
Das Element, auf das F zeigt, ist leer
Das heißt, der In-Grad von A ist 0, der In-Grad von B ist 1, der In-Grad von C ist 1, der In-Grad von D ist In 2 beträgt der In-Grad von E 2 und der In-Grad von F 2. In-Grad ist 2
Bei der topologischen Sortierung von DAG wird ein Punkt mit einem In-Grad von 0 ausgewählt und hinzugefügt jedes Mal die topologische Warteschlange, und dann werden alle mit diesem Punkt verbundenen Kanten gelöscht.
Suchen Sie zuerst Punkt A mit einem In-Grad von 0, nehmen Sie A aus der Warteschlange, fügen Sie ihn zum Ergebnis hinzu und entfernen Sie die mit A verbundenen Zeiger, dh reduzieren Sie die In-Grade von B und C um 1 auf 0 und fügen Sie B zum Ergebnis hinzu. C wird zur Warteschlange hinzugefügt, und dann wird der Knoten mit einem Eingangsgrad von 0 aus dem Kopf der Warteschlange entfernt und so weiter, und schließlich wird das Ergebnis ausgegeben, um das zu vervollständigen topologische Sortierung der 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))

Ausgabeergebnisse:

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

Die Code-Ausgabeergebnisse stimmen mit der obigen Analyse überein

Das obige ist der detaillierte Inhalt vonPython-Implementierung eines topologischen Sortiercodebeispiels für einen gerichteten azyklischen Graphen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!