topological sort

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.

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:

• 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)

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.

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.

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.

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:
            indegree += 1

    queue = deque( == 0])
    topo_order = 

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

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

    return topo_order

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.

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

    def dfs(u):
        visited.add(u)
        for v in graph:
            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  # fordított sorrend

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

• 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).

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

• 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)