Topologische Sortierung in Python

1. Topologischer Sortieralgorithmus in Python
2. Implementieren Sie den topologischen Sortieralgorithmus in Python

Dieses Tutorial zeigt die Implementierung des topologischen Sortieralgorithmus in Python.

Topologischer Sortieralgorithmus in Python

Der topologische Sortieralgorithmus sortiert gerichtete azyklische Graphen (DAGs). Ein gerichteter azyklischer Graph (DAG) ist ein Graph mit gerichteten Kanten von einem Knoten zum anderen, aber ohne Zyklen.

Die topologische Sortierung ist ein Algorithmus, der einen DAG als Eingabe akzeptiert und ein Array zurückgibt, in dem jeder Knoten vor den Knoten erscheint, auf die er zeigt.

Es kann nicht auf andere Graphen als DAGs angewendet werden, da die Reihenfolge bei der topologischen Sortierung vollständig von der Richtung der Kanten zwischen den Knoten abhängt, und wenn es Zyklen innerhalb eines Graphen gibt, kann es mehrere Anordnungen dafür geben.

Als Ergebnis können wir sagen, dass eine topologische Sortierung der Knoten eines gerichteten azyklischen Graphen die Aktion ist, die Knoten in der Reihenfolge anzuordnen, dass, wenn eine Kante (i,j) existiert, i vor j kommt in den Listen.

Eine topologische Sortierung liefert im Wesentlichen eine Reihenfolge, in der wir die Aufgabe ausführen sollten, und hilft uns bei der Bestimmung, ob der Graph einen Zyklus hat oder nicht.

Jeder Graph kann mehr als eine topologische Ordnung unterstützen. Der In-Grad des Knotens im Diagramm bestimmt dies.

Außerdem beginnt die topologische Ordnung des Netzwerks mit dem Knoten mit Eingangsgrad 0, d. h. einem Knoten ohne eingehende Kanten.

Schauen wir uns ein Beispiel an, um besser zu verstehen, was beim topologischen Sortieren passiert.

Eingabe DAG:

Erste Iteration: []

Zweite Iteration: [B]

Dritte Iteration: [B, E]

Vierte Iteration: [B, E, A]

Fünfte Iteration: [B, E, A, F]

Endgültige Ausgabe: [B, E, A, F, C, D]

Im obigen Beispiel entfernen wir iterativ den Knoten ohne Eingabekanten aus unserem Diagramm und fügen ihn in unser Array ein. Wir wiederholen diesen Vorgang, bis nur noch ein Knoten in unserem Diagramm übrig ist.

Am Ende hängen wir diesen letzten Knoten am Ende unseres Arrays an.

Implementieren Sie den topologischen Sortieralgorithmus in Python

Wir können dieselbe oben beschriebene Logik implementieren, um ein topologisches Sortierprogramm in Python zu erstellen. Die Schritte zum Implementieren dieses Algorithmus in unserem Code sind unten angegeben.

1. Identifizieren Sie den Knoten, der keine eingehenden Kanten hat.
2. Löschen Sie diesen Knoten und seine entsprechenden Kanten aus dem Diagramm.
3. Aktualisieren Sie den In-Grad der benachbarten Knoten.
4. Wiederholen Sie die Schritte 1 bis 3, bis das Diagramm leer ist.

Aus diesen 4 Schritten geht hervor, dass wir einen Graphen für die topologische Sortierung erstellen müssen. Dies kann auf mehrere Arten erfolgen, aber die bequemste Methode ist die Erstellung einer graph-Klasse, die Methoden zum Einfügen von Knoten und Kanten in unseren Graphen enthält.

Das folgende Code-Snippet zeigt eine graph-Klasse mit einem Konstruktor und einer Methode, um unserem Graphen weitere Kanten hinzuzufügen.

from collections import defaultdict


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

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

Jetzt haben wir eine Klasse namens graph, die einen gerichteten oder ungerichteten Graphen initialisieren kann, und eine Methode addEdge(), mit der wir unserem Graphen weitere Kanten hinzufügen können.

Alles, was wir jetzt brauchen, ist ein Mechanismus, um den topologischen Sortieralgorithmus zu implementieren. Wir müssen eine Funktion erstellen, die einen Knoten besucht, prüft, ob keine eingehenden Kanten vorhanden sind, und diesen Knoten löscht, wenn keine eingehenden Kanten vorhanden sind.

Diese Art von Funktion wird im folgenden Codeausschnitt gezeigt.

def visitNode(self, s, visited, sortlist):
    visited[s] = True
    for i in self.graph[s]:
        if not visited[i]:
            self.visitNode(i, visited, sortlist)
    sortlist.insert(0, s)

Die obige Funktion nimmt den Index des aktuellen Knotens s; eine boolesche Liste visited, die Informationen darüber enthält, ob ein Knoten bereits besucht wurde oder nicht, und eine sortlist, die wir verwenden werden, um die aus dem Diagramm gelöschten Knoten zu speichern.

Wir müssen eine weitere Hilfsfunktion erstellen, die diese visitNode() für alle Knoten in unserem Diagramm inkrementell aufruft und die Werte der sortierten Liste am Ende ausgibt. Das folgende Code-Snippet zeigt eine ähnliche Funktion, die in Python implementiert ist.

def topologicalSort(self):
    visited = {i: False for i in self.graph}
    sortlist = []

    for v in self.graph:
        if not visited[v]:
            self.visitNode(v, visited, sortlist)
    print(sortlist)

Damit ist unsere Implementierung der Klasse graph abgeschlossen. Wir müssen nun einen Graphen erstellen und die Funktion topologicalSort() aufrufen, um unsere Liste zu sortieren.

Dieser Prozess wurde im folgenden Code implementiert.

if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Ausgang:

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

Das Diagramm, das wir in diesem Code erstellt haben, entspricht dem Diagramm in den oben angegebenen Diagrammen. Hier beziehen sich die Indizes 1 bis 6 auf die Knoten A bis F.

Wie wir gesehen haben, war die endgültige sortierte Liste [B, E, A, F, C, D], was mit unserer Ausgabe im Code identisch ist.

Schauen wir uns nun unseren obigen Code in einem Codeblock kombiniert an.

from collections import defaultdict


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

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visitNode(self, s, visited, sortlist):
        visited[s] = True
        for i in self.graph[s]:
            if not visited[i]:
                self.visitNode(i, visited, sortlist)
        sortlist.insert(0, s)

    def topologicalSort(self):
        visited = {i: False for i in self.graph}
        sortlist = []

        for v in self.graph:
            if not visited[v]:
                self.visitNode(v, visited, sortlist)
        print(sortlist)


if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Ausgang:

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

Damit ist unser Tutorial abgeschlossen. Jetzt können Sie die topologische Sortierung mit einem vollständigen Verständnis ihrer Funktionsweise implementieren.