Sortowanie topologiczne

10.1 Definicja sortowania topologicznego

Sortowanie topologiczne to liniowe uporządkowanie wierzchołków skierowanego grafu acyklicznego (DAG) takie, że dla każdej krawędzi (u, v) wierzchołek u poprzedza wierzchołek v. To uporządkowanie jest możliwe tylko dla DAG i nie może być wykonane na grafach zawierających cykle.

Jak ci pasuje definicja? Jeśli zrozumiałeś ją od razu, to prawdopodobnie masz duże doświadczenie w pracy z algorytmami.

Proste słowa będą takie: masz listę zadań (wierzchołki grafu) i listę zależności między nimi (strzałki w grafie). Uporządkuj zadania (wierzchołki) tak, aby wszystkie zadania, od których zależy „zadanie A”, były wykonane przed nim. I od razu wszystko jasne, a nie „liniowe uporządkowanie wierzchołków skierowanego grafu acyklicznego” …

Sortowanie topologiczne to bardzo ważny algorytm z praktyki, dlatego ma własną nazwę, a nie tylko imię autora. Zobaczmy, gdzie jest potrzebny:

Zastosowanie:

1. Planowanie zadań (Task Scheduling):

Określenie kolejności wykonywania zależnych zadań tak, aby każde zadanie było wykonywane po wszystkich jego zależnościach.

Przykład:

Planowanie projektów w systemie zarządzania projektami.

2. Kompilacja kodu:

Określenie kolejności kompilacji modułów lub plików kodu źródłowego, które zależą od siebie.

Przykład:

Optymalizacja budowy oprogramowania w systemach budowy (np. Makefile).

3. Rozwiązywanie zależności w menedżerach pakietów:

Uporządkowanie pakietów tak, aby wszystkie zależności były zainstalowane przed instalacją samego pakietu.

Przykład:

Uproszczenie procesu instalacji oprogramowania w menedżerach pakietów (np. npm, pip, apt).

4. Optymalizacja tras:

Określenie kolejności odwiedzania punktów lub wykonywania działań, uwzględniając zależności między nimi.

Przykład:

Logistyka i planowanie tras dostarczania towarów.

Czasowa i przestrzenna złożoność sortowania topologicznego:

Złożoność czasowa:

Oba główne algorytmy sortowania topologicznego (DFS i algorytm Kahna) mają złożoność czasową O(V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi w grafie.

Złożoność przestrzenna:

Złożoność przestrzenna obu algorytmów to O(V + E), ponieważ wymaga przechowywania grafu, a także tablic do śledzenia odwiedzonych wierzchołków i poprzedników.

10.2 Implementacja poprzez przeszukiwanie w głąb (DFS)

Sortowanie topologiczne można wykonać na różne sposoby, jednym z nich jest przeszukiwanie w głąb — DFS. Algorytm DFS dla sortowania topologicznego używa stosu do śledzenia zakończonych węzłów.

Przykład implementacji:

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]  # Wynik w odwrotnej kolejności
    
# Przykład użycia:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_dfs(graph)
print("Sortowanie topologiczne:", result)

Wynik:

Sortowanie topologiczne: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']

10.3 Implementacja: algorytm Kahna

Innym podejściem jest algorytm Kahna (Kahn's Algorithm). Algorytm Kahna dla sortowania topologicznego wykorzystuje koncepcję stopni wejściowych wierzchołków.

Przykład implementacji:

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("Graf zawiera cykl")
            
# Przykład użycia:
graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['H', 'F'],
    'F': ['G'],
    'G': [],
    'H': []
}
result = topological_sort_kahn(graph)
print("Sortowanie topologiczne:", result)

Wynik:

Sortowanie topologiczne: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']

1

Опрос

Przeszukiwanie wszerz i w głąb,  56 уровень,  4 лекция

недоступен

Przeszukiwanie wszerz i w głąb

Przeszukiwanie wszerz i w głąb

Открыть