Wikiszótár

Kahn-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkɒxnɒlɡoritmuʃ]

Főnév

Kahn-algoritmus

  1. (matematika) A Kahn-algoritmus egy széles körben használt módszer a topologikus rendezés elvégzésére irányított, körmentes gráfokon (DAG - Directed Acyclic Graph). A topologikus rendezés egy olyan sorrend, amelyben a gráf csúcsai elrendezhetők úgy, hogy minden irányított él ( (u, v) ) esetén ( u ) mindig ( v ) előtt szerepel a sorrendben.


Fő ötlet

Az algoritmus az indegree (bejövő élek száma) fogalmát használja: 1. Azokat a csúcsokat választja ki, amelyeknek nincs bejövő élük (indegree = 0). 2. Ezeket a csúcsokat a sorrendbe helyezi, majd eltávolítja őket a gráfból. 3. A folyamatot addig ismétli, amíg az összes csúcsot feldolgozza, vagy megáll, ha kör található a gráfban.


Algoritmus lépései

1. Indegree kiszámítása

  • Minden csúcsra meghatározzuk a bejövő élek számát.

2. Indegree = 0 csúcsok hozzáadása a várakozási sorhoz

  • Egy olyan adatszerkezetbe helyezzük a csúcsokat (például sorba vagy verembe), amelyeknek nincs bejövő élük.

3. Iteráció

  • Amíg a várakozási sor nem üres:
    • Vegyük ki a sor első elemét, és adjuk hozzá a topologikus sorrendhez.
    • Távolítsuk el a gráfhoz tartozó éleit, és frissítsük a bejövő élek számát.
    • Ha egy csúcs bejövő élei 0-ra csökkennek, adjuk hozzá a várakozási sorhoz.

4. Ellenőrzés

  • Ha minden csúcs feldolgozásra került, a gráf topologikusan rendezett.
  • Ha maradnak csúcsok bejövő élekkel, a gráf kör tartalmaz.


Idő- és tárkomplexitás

  • Időbonyolultság: ( O(V + E) ), ahol ( V ) a csúcsok és ( E ) az élek száma.
  • Tárbonyolultság: ( O(V + E) ) az adatszerkezetek tárolására.


Pszeudokód

KahnAlgorithm(graph):
    indegree = [0] * len(graph)
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    queue = []
    for i in range(len(indegree)):
        if indegree[i] == 0:
            queue.append(i)

    topo_order = []
    while queue:
        u = queue.pop(0)
        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):
        return "Kör található a gráfban!"
    return topo_order

Python implementáció

from collections import deque

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

    # Indegree = 0 csúcsok hozzáadása a sorhoz
    queue = deque([node for node in graph if indegree[node] == 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)

    # Ellenőrzés, hogy körmentes-e a gráf
    if len(topo_order) != len(graph):
        return "Kör található a gráfban!"
    return topo_order

# Példa gráf
graph = {
    0: [1, 2],
    1: [3],
    2: [3],
    3: [4],
    4: []
}

print("Topologikus sorrend:", kahn_topological_sort(graph))

Kimenet: 

Topologikus sorrend: [0, 1, 2, 3, 4]

C++ implementáció

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

using namespace std;

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

    // Indegree kiszámítása
    for (const auto& [u, neighbors] : graph) {
        for (int v : neighbors) {
            indegree[v]++;
        }
    }

    // Indegree = 0 csúcsok hozzáadása a sorhoz
    queue<int> q;
    for (int i = 0; i < V; ++i) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector<int> topo_order;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);

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

    // Ellenőrzés, hogy körmentes-e a gráf
    if (topo_order.size() != V) {
        cout << "Kör található a gráfban!" << endl;
        return {};
    }

    return topo_order;
}

int main() {
    unordered_map<int, vector<int>> graph = {
        {0, {1, 2}},
        {1, {3}},
        {2, {3}},
        {3, {4}},
        {4, {}}
    };

    int V = 5;
    vector<int> topo_order = kahn_topological_sort(graph, V);

    cout << "Topologikus sorrend: ";
    for (int node : topo_order) {
        cout << node << " ";
    }
    cout << endl;

    return 0;
}

Kimenet: 

Topologikus sorrend: 0 1 2 3 4

Alkalmazások

  1. Feladatütemezés:
    • Függőségek kezelése, például projektek vagy feladatok sorrendjének meghatározása.
  2. Verziókezelés:
    • Kód függőségek sorrendjének meghatározása.
  3. Gráf algoritmusok:
    • Körök keresése irányított gráfokban.
  4. Fordítóprogramok:
    • Kódkomponensek (osztályok, függvények) sorrendjének meghatározása.


Összegzés

A Kahn-algoritmus egy hatékony és egyszerű módszer a topologikus rendezésre irányított, körmentes gráfokon. Az (O(V + E)) időbonyolultsága miatt nagy gráfok esetén is hatékony, és széles körben alkalmazható valós problémák megoldására, például feladatütemezésre és függőségkezelésre. Az algoritmus körök detektálására is használható, ami különösen hasznos hibakeresési és rendszerelemzési feladatokban.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Kahn-algoritmus&oldid=3479602”