Topologischer Sortieralgorithmus: Python, C++ Beispiel

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 gerichteten azyklischen Graphen (DAG) angewendet, sodass jeder Knoten in der sortierten Liste vor allen anderen Knoten erscheint, auf die er verweist. Der Algorithmus befolgt bestimmte Regeln wiederholt, bis die Sortierung abgeschlossen ist.

Betrachten Sie zur Vereinfachung das folgende Beispiel:

Gerichteter Graph

Hier sehen wir, dass Knoten „A“ keinen Eingangsgrad hat. Der Eingangsgrad bezeichnet die Kante, die auf einen Knoten verweist. Knoten „B“ und „C“ benötigen Knoten „A“, und Knoten „E“ benötigt Knoten „D“ und „F“. Einige Knoten sind also voneinander abhängig.

Hier ist eine weitere Darstellung des obigen Graphen:

Abhängigkeit jedes Knotens (lineare Reihenfolge)

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.

Hier sind die Schritte dazu:

Schritt 1) Suchen Sie den Knoten mit null eingehenden Kanten, einen Knoten mit null Grad.

Schritt 2) Speichere den Knoten mit dem Eingangsgrad Null in einer Warteschlange oder einem Stapel und entferne den Knoten aus dem Graphen.

Schritt 3) Löschen Sie anschließend die ausgehende Kante dieses Knotens. Dadurch wird der Eingangsgrad des nächsten Knotens verringert.

Die topologische Ordnung erfordert, dass die Graphdatenstruktur keine Zyklen enthält. Ein Graph gilt als gerichteter azyklischer Graph (DAG), wenn er folgende Anforderungen erfüllt:

• Ein oder mehrere Knoten mit einem Gradwert von Null.
• Der Graph enthält keinen Zyklus.

Solange der Graph Knoten enthält und ein gerichteter azyklischer Graph (DAG) ist, werden die oben genannten drei Schritte ausgeführt. Andernfalls gerät der Algorithmus in eine zyklische Abhängigkeit, und der Kahn-Algorithmus findet keinen Knoten mit Eingangsgrad Null.

So funktioniert die topologische Sortierung

Hier verwenden wir den „Kahn-Algorithmus“ für die topologische Sortierung. Angenommen, wir haben den folgenden Graphen:

Hier sind die Schritte des Kahn-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 sind der Eingangsgrad und der Ausgangsgrad des obigen Graphen:

Schritt 2) Finde den Knoten mit dem Eingangsgrad Null bzw. mit null eingehenden Kanten. Ein Knoten mit dem Eingangsgrad Null hat keine Kanten, die zu diesem Knoten führen. Knoten „A“ hat den Eingangsgrad Null, das heißt, es gibt keine Kante, die auf Knoten „A“ zeigt. Daher führen wir die folgenden Aktionen durch:

• Entferne diesen Knoten und seine ausgehenden Kanten.
• Platzieren Sie den Knoten zur Bestellung in der Warteschlange.
• Aktualisiere den Eingangsgrad des Nachbarknotens von „A“.

Schritt 3) Wir müssen einen Knoten mit Eingangsgrad null finden. In diesem Beispiel haben „B“ und „C“ einen Eingangsgrad von null. Wir können einen der beiden auswählen. Nehmen wir „B“ und entfernen ihn aus dem Graphen. Anschließend aktualisieren wir die Eingangsgrade der übrigen Knoten. Nach diesen Operationen sehen unser Graph und unsere Warteschlange wie folgt aus:

Schritt 4) Knoten „C“ hat keine eingehende Kante. Daher entfernen wir Knoten „C“ aus dem Graphen und fügen ihn der Warteschlange hinzu. Wir können auch die von „C“ ausgehende Kante löschen. Unser Graph sieht nun folgendermaßen aus:

Schritt 5) Wir sehen, dass die Knoten „D“ und „F“ einen Eingangsgrad von null haben. Wir nehmen einen Knoten und fügen ihn der Warteschlange hinzu. Nehmen wir zuerst „D“ heraus. Dann beträgt der Eingangsgrad für Knoten „E“ 1. Nun gibt es keine Verbindung mehr zwischen D und E. Dasselbe machen wir für Knoten „F“, und unser Ergebnis sieht dann wie folgt aus:

Schritt 6) Der Eingangsgrad (eingehende Kanten) und Ausgangsgrad (ausgehende Kanten) des Knotens „E“ sind null. Damit sind alle Voraussetzungen für Knoten „E“ erfüllt. Wir fügen „E“ nun am Ende der Warteschlange ein. Es sind keine Knoten mehr übrig, und der Algorithmus endet hier.

Spitzname Code 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 0 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 die Abhängigkeiten im zyklischen Graphen zyklisch sind. Betrachten Sie beispielsweise diesen Graphen:

Dieser Graph ist kein DAG (gerichteter azyklischer Graph), da A, B und C einen Zyklus bilden. Es gibt keinen Knoten mit Eingangsgrad null. Analysiert man den obigen Graphen gemäß Kahns Algorithmus, ergibt sich Folgendes:

• Suchen Sie einen Knoten mit null Grad (keine eingehenden Kanten).
• Entferne diesen Knoten aus dem Graphen und füge ihn der Warteschlange hinzu. Im obigen Graphen gibt es jedoch keinen Knoten mit Eingangsgrad Null. Jeder Knoten hat einen Eingangsgrad größer als 0.
• Es wird eine leere Warteschlange zurückgegeben, da kein Knoten mit Eingangsgrad Null 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 Knoten entspricht, dann gibt es keinen Zyklus.

Schritt 4) Wenn sie nicht gleich der Anzahl der Knoten ist, dann gibt es mindestens einen Zyklus in der gegebenen Graphdatenstruktur.

Komplexitätsanalyse der topologischen Sortierung

Es gibt zwei Arten von Komplexität bei Algorithmen. Diese sind:

1. Zeitliche Komplexität
2. Raumkomplexität

Diese Komplexitäten werden mit einer Funktion dargestellt, die eine allgemeine Komplexität bereitstellt.

Zeitliche Komplexität: Die Zeitkomplexität des topologischen Sortierens ist immer gleich. Es gibt einen Worst-Case, einen Average und einen Best-Case. Die Zeitkomplexität des topologischen Sortierens beträgt O(E + V), wobei E die Anzahl der Kanten und V die Anzahl der Knoten im Graphen bezeichnet.

Lassen Sie uns diese Komplexität überwinden:

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 bzw. topologischen Ordnung. Die Zeitkomplexität ergibt sich aus der obigen Berechnung zu O(V + E), wobei O die Komplexitätsfunktion bezeichnet.

Raumkomplexität: Für die Ausführung des topologischen Sortieralgorithmus benötigten wir O(V) Speicherplatz. Hier sind die Schritte, für die wir Speicherplatz im 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 trägt den Namen „order“ und speichert die Knoten in topologischer Reihenfolge. Das erforderte auch O (V) Räume.

Dies waren die individuellen Speicherkomplexitäten. Wir müssen diese Speicherkapazitäten also zur Laufzeit maximieren. Die Speicherkomplexität wird mit O(V) bezeichnet, wobei V die Nummer des Knotens im Graphen angibt.

Anwendung der topologischen Sortierung

Topologische Sortierung hat vielfältige Einsatzmöglichkeiten. Hier einige Beispiele:

• Es wird verwendet, wenn ein Betriebssystem muss die Ressourcenzuweisung durchführen.
• Einen Zyklus im Graphen finden. Wir können mithilfe der topologischen Sortierung überprüfen, ob der Graph ein DAG ist oder nicht.
• Satzreihenfolge in den Apps zur automatischen Vervollständigung.
• Es wird zur Erkennung verwendet. Deadlocks.
• Verschiedene Arten der Stundenplanung 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.

Häufig gestellte Fragen