topologikus rendezés

• IPA:

topologikus rendezés

1. (matematika, algoritmusok) A topologikus rendezés egy irányított gráf csúcsainak lineáris rendezése úgy, hogy minden él ( (u, v) ) esetén ( u ) megelőzi ( v )-t a sorrendben. Csak irányított, körmentes gráfokra (DAG) alkalmazható.

Két fő módszer létezik a topologikus rendezés végrehajtására:

1. Kahn-algoritmus (szélességi keresésen alapul),
2. Mélységi keresés (DFS) alapú megközelítés.

Ez az algoritmus szélességi keresést (BFS) használ.

1. Indegree kiszámítása:
   • Számítsd ki minden csúcs bejövő éleinek számát (( )).
2. Kezdeti csúcsok azonosítása:
   • Tedd azokat a csúcsokat, amelyeknek nincs bejövő élük (( = 0 )), egy sorba.
3. Feldolgozás:
   • Amíg a sor nem üres:
     • Vedd ki az első csúcsot, és add hozzá a rendezett listához.
     • Csökkentsd az összes szomszédos csúcs bejövő élének számát.
     • Ha egy csúcs bejövő éleinek száma 0 lesz, tedd a sorba.
4. Eredmény ellenőrzése:
   • Ha a rendezett lista tartalmazza az összes csúcsot, akkor a gráf körmentes volt, és az eredmény a topologikus sorrend.

• ( O(V + E) ), ahol ( V ) a csúcsok, ( E ) az élek száma.

Ez az algoritmus mélységi keresést (DFS) használ.

1. Látogatott csúcsok jelölése:
   • Tarts nyilván egy listát a meglátogatott csúcsokról.
2. Postorder sorrend:
   • Végezz mélységi keresést:
     • Ha egy csúcs minden gyermeke feldolgozásra került, add a csúcsot a rendezett listához.
3. Lista megfordítása:
   • A DFS során kapott sorrendet fordítsd meg, hogy a megfelelő topologikus sorrendet kapd.

• ( O(V + E) ), mivel a DFS minden csúcsot és élt pontosan egyszer látogat meg.

KahnTopologicalSort(G):
    indegree =  * V
    for minden él (u, v) ∈ E:
        indegree += 1

    Q = üres sor
    for minden v ∈ V:
        if indegree == 0:
            Q.push(v)

    topological_order = 
    while Q nem üres:
        u = Q.pop()
        topological_order.append(u)
        for minden szomszéd v ∈ G:
            indegree -= 1
            if indegree == 0:
                Q.push(v)

    if len(topological_order) != V:
        throw "A gráf körkörös!"
    return topological_order

DFSTopologicalSort(G):
    visited =  * V
    stack = 

    def dfs(v):
        visited = True
        for minden szomszéd u ∈ G:
            if not visited:
                dfs(u)
        stack.append(v)

    for minden v ∈ V:
        if not visited:
            dfs(v)

    return stack.reverse()

from collections import deque, defaultdict

def kahn_topological_sort(graph):
    # Indegree számítása
    indegree = {node: 0 for node in graph}
    for u in graph:
        for v in graph:
            indegree += 1

    # Kezdeti csúcsok azonosítása
    queue = deque( == 0])
    topological_order = 

    while queue:
        node = queue.popleft()
        topological_order.append(node)
        for neighbor in graph:
            indegree -= 1
            if indegree == 0:
                queue.append(neighbor)

    # Ellenőrzés: tartalmaz-e minden csúcsot
    if len(topological_order) == len(graph):
        return topological_order
    else:
        raise ValueError("A gráf körkörös!")

# Példa gráf
graph = {
    0: ,
    1: ,
    2: ,
    3: ,
    4: 
}
print("Topologikus sorrend:", kahn_topological_sort(graph))

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

    def dfs(node):
        visited.add(node)
        for neighbor in graph:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)

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

    return stack  # Megfordítás

# Példa gráf
graph = {
    0: ,
    1: ,
    2: ,
    3: ,
    4: 
}
print("Topologikus sorrend:", dfs_topological_sort(graph))

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> kahn_topological_sort(int V, vector<vector<int>>& graph) {
    vector<int> indegree(V, 0);
    vector<int> result;

    // Indegree számítása
    for (int u = 0; u < V; ++u) {
        for (int v : graph) {
            indegree++;
        }
    }

    // Kezdeti csúcsok azonosítása
    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (indegree == 0) {
            q.push(i);
        }
    }

    // Feldolgozás
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u);

        for (int v : graph) {
            indegree--;
            if (indegree == 0) {
                q.push(v);
            }
        }
    }

    // Ellenőrzés
    if (result.size() != V) {
        throw runtime_error("A gráf körkörös!");
    }

    return result;
}

int main() {
    int V = 5;
    vector<vector<int>> graph = {
        {1, 2},  // 0 -> 1, 0 -> 2
        {3},     // 1 -> 3
        {3},     // 2 -> 3
        {4},     // 3 -> 4
        {}       // 4
    };

    try {
        vector<int> result = kahn_topological_sort(V, graph);
        cout << "Topologikus sorrend: ";
        for (int v : result) {
            cout << v << " ";
        }
        cout << endl;
    } catch (const runtime_error& e) {
        cout << e.what() << endl;
    }

    return 0;
}

1. Feladatütemezés:
   • Ha egyes feladatok csak mások elvégzése után kezdhetők el.
2. Programfordítás:
   • Modulok vagy osztályok sorrendjének meghatározása a függőségek alapján.
3. Hálózati folyamatok:
   • Adatfüggőségek kezelése adatbázisokban vagy adatfolyamokban.

A topologikus rendezés alapvető algoritmus a körmentes irányított gráfok (DAG-ok) kezelésében. A Kahn-algoritmus és a DFS-alapú megközelítés egyszerű, mégis hatékony módszereket kínálnak, amelyek számos gyakorlati alkalmazásban használhatók, például ütemezési és függőségi problémák megoldására.

• topologikus rendezés - Értelmező szótár (MEK)
• topologikus rendezés - Etimológiai szótár (UMIL)
• topologikus rendezés - Szótár.net (hu-hu)
• topologikus rendezés - DeepL (hu-de)
• topologikus rendezés - Яндекс (hu-ru)
• topologikus rendezés - Google (hu-en)
• topologikus rendezés - Helyesírási szótár (MTA)
• topologikus rendezés - Wikidata
• topologikus rendezés - Wikipédia (magyar)