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.
KahnAlgorithm(graph):
indegree = * len(graph)
for u in graph:
for v in graph:
indegree += 1
queue =
for i in range(len(indegree)):
if indegree == 0:
queue.append(i)
topo_order =
while queue:
u = queue.pop(0)
topo_order.append(u)
for v in graph:
indegree -= 1
if indegree == 0:
queue.append(v)
if len(topo_order) != len(graph):
return "Kör található a gráfban!"
return topo_order
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:
indegree += 1
# Indegree = 0 csúcsok hozzáadása a sorhoz
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)
# 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: ,
3: ,
4:
}
print("Topologikus sorrend:", kahn_topological_sort(graph))
Kimenet:
Topologikus sorrend:
#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& : graph) {
for (int v : neighbors) {
indegree++;
}
}
// Indegree = 0 csúcsok hozzáadása a sorhoz
queue<int> q;
for (int i = 0; i < V; ++i) {
if (indegree == 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) {
indegree--;
if (indegree == 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
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.