Cad atá i ndiaidh socrúchán topeolaíochta?

Question

Accepted Answer

**Sórtáil thopeolaíochta** ordaíonn go líneach rinn **DAG** (graf dírithe acyclic) ionas gur bhfuil gach imeall u->v ag u **roimh** v. Freagraíonn sé ar an gceist "in ord ar bith is féidir liom na tascanna seo a dhéanamh agus a dhréimpleachtaí ann?"

## An smaoineamh

Dhá dhóigh choitianta: **algartam Kahn** (bain nó dhá nód le céim-isteach 0 i ndiaidh a chéile) nó **DFS** (post-ord droichead). Ní bhíonn ordú bailí ann **ach amháin mura bhfuil thimpeall ann**.

## Sampla (algartam Kahn)

```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']
```

## Castacht

- **Am:** O(V + E). **Spás:** O(V).

## Cathain atá sé ag baint úsáide / gaothanna

Baineann le **córais thógála**, sceideal tascanna, réamhriachtanais chúrsa, agus réiteach imdháileachta. Más gearr an toradh ná V, bíonn **foluain** sa ghraf (gan ord bailí). Níl an t-ordú i gcoitinne **nach bhfuil uathúil**.

## Cén fáth gur thábhachtach

Tá ordú imdháileachta i ngach áit — tiomsaitheoirí, bainisteorí pacáistí, ríomh scarbhileog, pipleanna CI.

Feidhmíonn sórtáil thopeolaíochta mar bhraistintí timpeall do ghraif dhírithe.

Proibléim a aithint mar "ordú faoi shrianta" agus socrúchán topeolaíochta a bhaint amach ná comhartha láidir sinsearachta.