10.1 Definition der Topologischen Sortierung
Topologische Sortierung — ist eine lineare Anordnung der Knoten eines gerichteten azyklischen Graphen (DAG), sodass für jede Kante (u, v) der Knoten u dem Knoten v vorausgeht. Diese Anordnung ist nur für DAGs möglich und kann nicht auf Graphen mit Zyklen durchgeführt werden.
Wie findest du die Definition? Wenn du sie auf Anhieb verstanden hast, dann hast du wahrscheinlich viel Erfahrung mit Algorithmen.
Einfach gesagt, du hast eine Liste von Aufgaben (Knoten des Graphen) und eine Liste von Abhängigkeiten zwischen ihnen (Pfeile im Graph). Ordne die Aufgaben (Knoten) so, dass alle Aufgaben, von denen "Aufgabe A" abhängt, vor ihr erledigt werden. Und schon ist alles klar, anstatt "lineare Anordnung der Knoten eines gerichteten azyklischen Graphen" ...
Topologische Sortierung ist ein sehr wichtiger Algorithmus in der Praxis, daher hat er einen eigenen Namen und nicht einfach nur den Namen des Autors. Lass uns anschauen, wo er gebraucht wird:
Anwendungen:
1. Aufgabenplanung (Task Scheduling):
Bestimmung der Ausführungsreihenfolge abhängiger Aufgaben, sodass jede Aufgabe nach all ihren Abhängigkeiten ausgeführt wird.
Beispiel:
Projektplanung in einem Projektmanagement-System.
2. Code-Kompilierung:
Bestimmung der Reihenfolge der Kompilierung von Modulen oder Quellcode-Dateien, die voneinander abhängen.
Beispiel:
Optimierung der Software-Builds in Build-Systemen (z.B. Makefile).
3. Abhängigkeitsauflösung in Paketmanagern:
Anordnung von Paketen, sodass alle Abhängigkeiten vor der Installation des Pakets selbst installiert sind.
Beispiel:
Vereinfachung des Software-Installationsprozesses in Paketmanagern (z.B. npm, pip, apt).
4. Routenoptimierung:
Bestimmung der Reihenfolge des Besuchs von Punkten oder der Durchführung von Aktionen unter Berücksichtigung der Abhängigkeiten zwischen ihnen.
Beispiel:
Logistik und Routenplanung für die Zustellung von Waren.
Zeit- und Raumkomplexität der Topologischen Sortierung:
Zeitkomplexität:
Beide Hauptalgorithmen der Topologischen Sortierung (DFS und Kahn's Algorithmus) haben eine Zeitkomplexität von O(V + E), wobei V die Anzahl der Knoten und E die Anzahl der Kanten im Graph ist.
Raumkomplexität:
Die Raumkomplexität beider Algorithmen beträgt O(V + E), da die Speicherung des Graphen sowie der Arrays zur Verfolgung der besuchten Knoten und Vorgänger erforderlich ist.
10.2 Implementierung durch Tiefensuche (DFS)
Die Topologische Sortierung kann auf verschiedene Weisen durchgeführt werden, eine davon basiert auf der Tiefensuche — DFS. Der DFS-Algorithmus für die Topologische Sortierung verwendet einen Stapel zur Nachverfolgung der abgeschlossenen Knoten.
Beispielimplementierung:
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # Ergebnis in umgekehrter Reihenfolge
# Beispiel der Verwendung:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Topologische Sortierung:", result)
Ausgabe:
Topologische Sortierung: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Implementierung: Kahn's Algorithmus
Ein weiterer Ansatz wird Kahn's Algorithmus genannt. Der Kahn-Algorithmus für die Topologische Sortierung verwendet das Konzept der eingehenden Knotenanzahl.
Beispielimplementierung:
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("Graph enthält einen Zyklus")
# Beispiel der Verwendung:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Topologische Sortierung:", result)
Ausgabe:
Topologische Sortierung: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION