Τι είναι η τοπολογική ταξινόμηση;

Question

Accepted Answer

**Topological sort** διατάσσει γραμμικά τις κορυφές ενός **DAG** (κατευθυνόμενου ακυκλικού γραφήματος) έτσι ώστε κάθε ακμή u->v να έχει το u **πριν** το v. Απαντά στο ερώτημα "σε ποια σειρά μπορώ να εκτελέσω αυτές τις εργασίες δεδομένων των εξαρτήσεών τους;"

## Η ιδέα

Δύο κοινές προσεγγίσεις: **Kahn's algorithm** (επαναληπτική αφαίρεση κόμβων με in-degree 0) ή **DFS** (αντίστροφη post-order). Μια έγκυρη ταξινόμηση υπάρχει **μόνο αν δεν υπάρχει κύκλος**.

## Παράδειγμα (Kahn's algorithm)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # count incoming edges
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # "remove" the edge
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> cycle

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## Πολυπλοκότητα

- **Χρόνος:** O(V + E). **Χώρος:** O(V).

## Πότε να χρησιμοποιήσετε / παγίδες

Χρησιμοποιήστε για **build systems**, προγραμματισμό εργασιών, προαπαιτούμενα μαθήματα και επίλυση εξαρτήσεων. Αν το αποτέλεσμα είναι μικρότερο από V, το γράφημα έχει **κύκλο** (δεν υπάρχει έγκυρη σειρά). Η ταξινόμηση είναι γενικά **όχι μοναδική**.

## Γιατί είναι σημαντικό

Η ταξινόμηση εξαρτήσεων είναι παντού — compilers, package managers, υπολογισμός υπολογιστικών φύλλων, CI pipelines.

Η topological sort λειτουργεί επίσης ως ανίχνευση κύκλου για κατευθυνόμενα γραφήματα.

Η αναγνώριση ενός προβλήματος ως "ταξινόμηση υπό περιορισμούς" και η χρήση topological sort είναι ένα ισχυρό σήμα ανώτερου επιπέδου.