topological sort

Angol

Főnév

topological sort (tsz. topological sorts)

1. (informatika) ?

---

A topological sort (topologikus rendezés) egy irányított gráf (DAG – Directed Acyclic Graph) csúcspontjainak olyan lineáris sorrendbe állítása, amelyben minden él irányát figyelembe vesszük. Ez azt jelenti, hogy ha van egy él ${\textstyle u\rightarrow v}$, akkor a ${\textstyle u}$ csúcs megelőzi ${\textstyle v}$-t a rendezésben.

---

🧠 1. Mikor használjuk?

Topologikus rendezést olyan függőségi viszonyokat tartalmazó problémákban alkalmazunk, ahol a tevékenységeket vagy eseményeket sorrendbe kell állítani:

Példák:

• Feladatütemezés (pl. egy feladat csak másik után kezdhető)
• Fordítási sorrend (egyes fájlok függnek másoktól)
• Kurzusok előfeltételei (melyiket kell előbb elvégezni)
• Makefile / build rendszer
• Adatfolyam modellek (Dataflow DAG)

---

🔁 2. Feltételek

Topologikus sorrend csak akkor létezik, ha a gráf irányított és körmentes (DAG). Ha kör van benne, akkor nem létezik olyan sorrend, ami megfelel az élirányoknak.

---

📐 3. Formális definíció

Adott egy irányított gráf ${\textstyle G=(V,E)}$, a topologikus sorrend olyan permutáció ${\textstyle (v_{1},v_{2},...,v_{n})}$, ahol:

Minden él ${\textstyle (u,v)\in E}$ esetén: ${\textstyle u}$ megelőzi ${\textstyle v}$-t, azaz ${\textstyle u}$ szerepel előbb a listában.

---

🔢 4. Algoritmusok

4.1 Kahn algoritmusa (indegree-alapú, BFS jellegű)

1. Számoljuk meg minden csúcs bejövő fokát (indegree).
2. Helyezzük azokat a csúcsokat egy sorba, amelyeknek ${\textstyle indegree=0}$.
3. Vegyünk ki egy ilyen csúcsot, tegyük a sorrendbe.
4. Csökkentsük az utódainak az ${\textstyle indegree}$-jét.
5. Ha valamelyik utód ${\textstyle indegree=0}$ lesz, tegyük a sorba.
6. Ismételjük, amíg van csúcs a sorban.

Ha nem dolgoztunk fel az összes csúcsot, akkor ciklus van.

Pythonban:

from collections import deque, defaultdict

def kahn_topological_sort(graph):
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    queue = deque([u for u in graph if indegree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    if len(topo_order) != len(graph):
        raise ValueError("A ciklus miatt nincs topologikus sorrend.")

    return topo_order

---

4.2 DFS-alapú algoritmus

1. Minden csúcson futtass DFS-t.
2. Ha végeztünk egy csúcs bejárásával, tegyük a listánk elejére.
3. A végeredmény: topologikusan rendezett lista.

Pythonban:

def dfs_topological_sort(graph):
    visited = set()
    topo_order = []

    def dfs(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                dfs(v)
        topo_order.append(u)

    for u in graph:
        if u not in visited:
            dfs(u)

    return topo_order[::-1]  # fordított sorrend

---

🧭 5. Példa gráfra

Adott egy gráf:

A → C
B → C
C → D
D → E

Lehetséges topologikus sorrendek:

• A, B, C, D, E
• B, A, C, D, E

---

🧮 6. Alkalmazások

Terület	Példa
Ütemezés	Feladatfüggőségek
Build rendszerek	Fordítási sorrend (pl. make)
Fordítási sorrend	Fordítási sorrend a nyelvfordítóban
Adatcsővezeték	Moduláris adatfeldolgozás
Kurzus-előfeltétel	Kurzusok teljesítési sorrendje

---

⚠️ 7. Hibakezelés

• Ha nem létezik topologikus sorrend, akkor a gráf kört tartalmaz.
• Ez észlelhető:
  • Kahn algoritmusánál: ha a végén marad feldolgozatlan csúcs.
  • DFS-nél: ha szürke csúcsra lépünk újra (ciklusdetektálás).

---

📌 8. Összefoglalás

Tulajdonság	Érték
Adatstruktúra	Irányított gráf (DAG)
Cél	Csúcsok sorrendbe állítása, hogy minden él iránya megmaradjon
Módszerek	Kahn (BFS), DFS
Komplexitás	${\textstyle O(V+E)}$
Feltétel	Csak körmentes irányított gráfra létezik
Alkalmazás	Fordítás, ütemezés, függőség-kezelés

További információk

• topological sort - Szótár.net (en-hu)
• topological sort - Sztaki (en-hu)
• topological sort - Merriam–Webster
• topological sort - Cambridge
• topological sort - WordNet
• topological sort - Яндекс (en-ru)
• topological sort - Google (en-hu)
• topological sort - Wikidata
• topological sort - Wikipédia (angol)