Wikiszótár

topologikus rendezés

Magyar

Kiejtés

  • IPA: [ ˈtopoloɡikuʃrɛndɛzeːʃ]

Főnév

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ó.


Algoritmusok

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.


1. Kahn-algoritmus

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

Lépések:

  1. Indegree kiszámítása:
    • Számítsd ki minden csúcs bejövő éleinek számát (( [v] )).
  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.

Időbonyolultság:

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


2. Mélységi keresés alapú algoritmus

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

Lépések:

  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.

Időbonyolultság:

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


Pszeudokód

Kahn-algoritmus

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

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

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

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

DFS alapú algoritmus

DFSTopologicalSort(G):
    visited = [False] * V
    stack = []

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

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

    return stack.reverse()

Python implementáció

Kahn-algoritmus

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[u]:
            indegree[v] += 1

    # Kezdeti csúcsok azonosítása
    queue = deque([node for node in graph if indegree[node] == 0])
    topological_order = []

    while queue:
        node = queue.popleft()
        topological_order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 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],
    1: [3],
    2: [3],
    3: [4],
    4: []
}
print("Topologikus sorrend:", kahn_topological_sort(graph))

DFS alapú algoritmus

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

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

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

    return stack[::-1]  # Megfordítás

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

C++ implementáció

Kahn-algoritmus

#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[u]) {
            indegree[v]++;
        }
    }

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

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

        for (int v : graph[u]) {
            indegree[v]--;
            if (indegree[v] == 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;
}

Alkalmazások

  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.


Összegzés

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.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=topologikus_rendezés&oldid=3479748”