Topologische Sortierung: Python, C++ Algorithmusbeispiel
Sarah Chen
Was ist ein topologischer Sortieralgorithmus?
Die topologische Sortierung wird auch als Kahn-Algorithmus bezeichnet und ist ein beliebter Sortieralgorithmus. Unter Verwendung eines gerichteten Graphen als Eingabe sortiert Topological Sort die Knoten so, dass jeder vor dem Knoten erscheint, auf den er zeigt.
Dieser Algorithmus wird auf einen DAG (Directed Asymmetric Graph) angewendet, sodass jeder Knoten im geordneten Array erscheint, bevor alle anderen Knoten auf ihn verweisen. Dieser Algorithmus folgt einigen Regeln wiederholt, bis die Sortierung abgeschlossen ist.
Betrachten Sie zur Vereinfachung das folgende Beispiel:
Hier können wir sehen, dass „A“ keinen Grad hat. Damit ist die Kante gemeint, die auf einen Knoten zeigt. „B“ und „C“ haben die Voraussetzung „A“, dann hat „E“ die Voraussetzung „D“- und „F“-Knoten. Einige der Knoten sind von anderen Knoten abhängig.
Hier ist eine weitere Darstellung der obigen Grafik:
Wenn wir also den DAG (Directed Asymmetric Graph) an die topologische Sortierung übergeben, erhalten wir ein Array mit linearer Reihenfolge, bei dem das erste Element keine Abhängigkeit hat.
Dieses Beispiel zeigt ein Diagramm mit einem Zyklus:
Hier sind die Schritte dazu:
Schritt 1) Suchen Sie den Knoten mit null eingehenden Kanten, einen Knoten mit null Grad.
Schritt 2) Speicher, der In-Grad-Knoten in einer Warteschlange oder einem Stapel auf Null setzt und den Knoten aus dem Diagramm entfernt.
Schritt 3) Löschen Sie dann die ausgehende Kante von diesem Knoten.
Dadurch wird die In-Grad-Zählung für den nächsten Knoten verringert.
Die topologische Reihenfolge erfordert, dass die Diagrammdatenstruktur keinen Zyklus aufweist.
Ein Diagramm gilt als DAG, wenn es die folgenden Anforderungen erfüllt:
- Ein oder mehrere Knoten mit einem Gradwert von Null.
- Diagramm enthält keinen Zyklus
Solange es Knoten im Graphen gibt und der Graph noch DAG ist, führen wir die obigen drei Schritte aus. Andernfalls fällt der Algorithmus in die zyklische Abhängigkeit und Kahns Algorithmus kann keinen Knoten mit einem Eingangsgrad von Null finden.
So funktioniert die topologische Sortierung
Hier verwenden wir „Kahns Algorithmus“ für die topologische Sortierung. Nehmen wir an, wir haben den folgenden Graphen:
Hier sind die Schritte für Kahns Algorithmus:
Schritt 1) Berechnen Sie den Eingangsgrad oder die Eingangskante aller Knoten im Diagramm.
Hinweis:
- Ingrad bezeichnet die gerichteten Kanten, die auf den Knoten zeigen.
- Unter Grad versteht man die gerichteten Kanten, die von einem Knoten ausgehen.
Hier ist der In-Grad und Out-Grad des obigen Diagramms:
Schritt 2) Suchen Sie den Knoten mit null Grad oder eingehenden Kanten.
Der Knoten mit dem Grad Null bedeutet, dass keine Kanten auf diesen Knoten zukommen. Knoten „A“ hat null Grad, was bedeutet, dass es keine Kante gibt, die auf Knoten „A“ zeigt.
Wir werden also die folgenden Aktionen durchführen:
- Entfernen Sie diesen Knoten und seine Außenkanten (ausgehende Kanten).
- Platzieren Sie den Knoten zur Bestellung in der Warteschlange.
- Aktualisieren Sie die In-Grad-Anzahl des Nachbarknotens von „A“.
Schritt 3) Wir müssen einen Knoten mit einem Gradwert von Null finden. In diesem Beispiel haben „B“ und „C“ einen Grad von Null.
Hier können wir eines dieser beiden nehmen. Nehmen wir „B“ und löschen Sie es aus dem Diagramm.
Aktualisieren Sie dann die Indegree-Werte anderer Knoten.
Nach der Durchführung dieser Vorgänge sehen unser Diagramm und unsere Warteschlange wie folgt aus:
Schritt 4) Knoten „C“ hat keine eingehende Kante. Wir entfernen also den Knoten „C“ aus dem Diagramm und verschieben ihn in die Warteschlange.
Wir können auch die von „C“ ausgehende Kante löschen.
Nun sieht unser Diagramm so aus:
Schritt 5) Wir können sehen, dass die Knoten „D“ und „F“ den Grad Null haben. Wir nehmen einen Knoten und stellen ihn in die Warteschlange.
Nehmen wir zuerst „D“ heraus. Dann ist die Ingradzahl für Knoten „E“ 1. Jetzt gibt es keinen Knoten von D nach E.
Das Gleiche müssen wir für den Knoten „F“ tun. Unser Ergebnis wird dann wie folgt aussehen:
Schritt 6) Der Indegree (eingehende Kanten) und Outdegree (ausgehende Kanten) des Knotens „E“ wurden Null. Wir haben also alle Voraussetzungen für Knoten „E“ erfüllt.
Hier setzen wir „E“ an das Ende der Warteschlange. Da wir keine Knoten mehr haben, endet der Algorithmus hier.
Pseudocode für topologische Sortierung
Hier ist der Pseudocode für die topologische Sortierung unter Verwendung des Kahn-Algorithmus.
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 O indegree present:
topological_list.append(node)
G.remove(node)
Update Indegree of present nodes
Return topological_list
Die topologische Sortierung kann auch mit dem DFS implementiert werden (Tiefe Erste Suche) Methode. Dieser Ansatz ist jedoch die rekursive Methode. Kahns Algorithmus ist effizienter als der DFS-Ansatz.
C++ Implementierung der topologischen Sortierung
#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();
}
Ausgang
0 1 2 3 5 4
Python Implementierung der topologischen Sortierung
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()
Ausgang
[0, 1, 2, 3, 5, 4]
Zyklische Graphen des topologischen Sortieralgorithmus
Ein Graph, der einen Zyklus enthält, kann nicht topologisch geordnet werden. Da der zyklische Graph die Abhängigkeit zyklisch hat.
Sehen Sie sich zum Beispiel diese Grafik an:
Dieser Graph ist kein DAG (Directed Asymmetric Graph), da A, B und C einen Zyklus erzeugen. Wie Sie bemerken, gibt es keinen Knoten mit einem In-Grad-Wert von Null.
Wenn wir gemäß Kahns Algorithmus die obige Grafik analysieren:
- Suchen Sie einen Knoten mit null Grad (keine eingehenden Kanten).
- Entfernen Sie diesen Knoten aus dem Diagramm und verschieben Sie ihn in die Warteschlange.
Im obigen Diagramm gibt es jedoch keinen Knoten mit Null in Grad. Jeder Knoten hat einen In-Grad-Wert größer als 0. - Gibt eine leere Warteschlange zurück, da kein Knoten mit Null in Grad gefunden werden konnte.
Wir können Zyklen mithilfe der topologischen Ordnung mit den folgenden Schritten erkennen:
Schritt 1) Führen Sie eine topologische Sortierung durch.
Schritt 2) Berechnen Sie die Gesamtzahl der Elemente in der topologisch sortierten Liste.
Schritt 3) Wenn die Anzahl der Elemente der Gesamtzahl der Scheitelpunkte entspricht, gibt es keinen Zyklus.
Schritt 4) Wenn sie nicht der Anzahl der Scheitelpunkte entspricht, gibt es mindestens einen Zyklus in der gegebenen Diagrammdatenstruktur.
Komplexitätsanalyse der topologischen Sortierung
Es gibt zwei Arten von Komplexität in Algorithmen. Sie sind
- Zeitliche Komplexität
- Raumkomplexität
Diese Komplexitäten werden mit einer Funktion dargestellt, die eine allgemeine Komplexität bereitstellt.
Zeitliche Komplexität: Die Zeitkomplexität ist bei der topologischen Sortierung immer gleich. Es gibt Worst-Case-, Durchschnitts- und Best-Case-Szenarien für die Zeitkomplexität.
Die Zeitkomplexität für die topologische Sortierung beträgt O(E + V), wobei E die Anzahl der Kanten im Graphen und V die Anzahl der Eckpunkte im Graphen bezeichnet.
Lassen Sie uns diese Komplexität durchbrechen:
Schritt 1) Zu Beginn berechnen wir alle Ingrade. Dazu müssen wir alle Kanten durchgehen und zunächst allen V-Scheitelpunkten den Wert Null zuweisen. Die inkrementellen Schritte, die wir durchführen, werden also sein O(V+E).
Schritt 2) Wir werden den Knoten mit dem Gradwert Null finden. Wir müssen anhand der V-Nummer des Scheitelpunkts suchen. Damit sind die Schritte abgeschlossen O (V).
Schritt 3) Für jeden Knoten mit null Eingangsgraden entfernen wir diesen Knoten und verringern den Eingangsgrad. Die Durchführung dieser Operation für alle Knoten dauert O(E).
Schritt 4) Abschließend prüfen wir, ob es einen Zyklus gibt oder nicht. Wir prüfen, ob die Gesamtzahl der Elemente im sortierten Array gleich der Gesamtzahl der Knoten ist. Es wird dauern O (1).
Dies waren also die einzelnen Zeitkomplexitäten für jeden Schritt der topologischen Sortierung oder topologischen Ordnung. Wir können sagen, dass die Zeitkomplexität aus der obigen Berechnung O(V + E) beträgt; hier steht O für die Komplexitätsfunktion.
Raumkomplexität: Wir brauchten O(V) Räume, um den topologischen Sortieralgorithmus auszuführen.
Hier sind die Schritte, bei denen wir den Platz für das Programm benötigten:
- Wir mussten alle Ingrade der im Diagramm vorhandenen Knoten berechnen. Da der Graph insgesamt V Knoten hat, müssen wir ein Array der Größe V erstellen. Der benötigte Platz war also O (V).
- Eine Queue-Datenstruktur wurde verwendet, um den Knoten mit einem Grad von Null zu speichern. Wir haben die Knoten mit dem Grad Null aus dem ursprünglichen Diagramm entfernt und sie in die Warteschlange gestellt. Dafür war der erforderliche Platz vorhanden O (V).
- Das Array heißt „order“. Dadurch wurden die Knoten in topologischer Reihenfolge gespeichert. Das war auch erforderlich O (V) Räume.
Dies war die individuelle Raumkomplexität. Daher müssen wir diese Räume während der Laufzeit maximieren.
Die räumliche Komplexität steht für O(V), wobei V die Nummer der Scheitelpunkte im Graphen bezeichnet.
Anwendung der topologischen Sortierung
Die topologische Sortierung bietet vielfältige Einsatzmöglichkeiten. Hier sind einige davon:
- Es wird verwendet, wenn Betriebssystem muss die Ressourcenzuweisung durchführen.
- Einen Zyklus im Diagramm finden. Mit der topologischen Sortierung können wir überprüfen, ob der Graph DAG ist oder nicht.
- Satzreihenfolge in den Apps zur automatischen Vervollständigung.
- Es dient der Erkennung Deadlocks.
- Verschiedene Arten der Terminplanung oder Kursplanung nutzen die topologische Sortierung.
- Abhängigkeiten auflösen. Wenn Sie beispielsweise versuchen, ein Paket zu installieren, benötigt dieses Paket möglicherweise auch andere Pakete. Durch die topologische Reihenfolge werden alle erforderlichen Pakete ermittelt, um das aktuelle Paket zu installieren.
- Linux verwendet die topologische Sortierung in „apt“, um die Abhängigkeit der Pakete zu überprüfen.
