directed acyclic graph

Angol

Főnév

directed acyclic graph (tsz. directed acyclic graphs)

1. (informatika) irányított körmentes gráf

---

A Directed Acyclic Graph vagy röviden DAG (irányított körmentes gráf) egy olyan gráf, amely:

* irányított éleket tartalmaz,

• nem tartalmaz köröket (azaz nincs olyan út, ami visszavezet önmagához).

Ez a struktúra rendkívül gyakori sokféle alkalmazásban, például:

• feladatütemezésben (task scheduling),
• fordítóprogramokban (pl. fordítási sorrend),
• verziókövetésben (pl. Git),
• adatbázisban (pl. lekérdezési tervek),
• blokklánc-technológiákban.

---

🧠 Tulajdonságai

Tulajdonság	Leírás
Irányított	Minden él egy irányba mutat (pl. A → B)
Körmentes	Nincs olyan út, hogy A → B → C → … → A
Topológiai sorrend létezik	Mindig van olyan csúcssorrend, ahol az élek “előre” mutatnak
Nem feltétlenül összefüggő	Lehet több komponense is

---

📊 Példa DAG-ra

A → B → D
 \       ↓
  → C → E

• Itt minden él egy irányba mutat.
• Nincs olyan út, ami visszavezet valamelyik korábbi csúcshoz.

---

🔄 Topológiai rendezés

A DAG egyik legfontosabb alkalmazása a topológiai sorrend meghatározása, ami egy olyan sorrend, ahol minden csúcs megelőzi azokat, ahová élek mutatnak belőle.

Például az alábbi DAG-hoz:

A → B
A → C
B → D
C → D

A lehetséges topológiai sorrendek:

• A, B, C, D
• A, C, B, D

---

🧰 Alkalmazások

Terület	Példa
Fordítók	Függőségi sorrend rendezése (make, gcc)
Ütemezés	Feladatok sorrendje (task dependency graph)
Verziókövetés (Git)	Commit-történet DAG, nem lineáris
Adatbázis	Lekérdezések optimalizálása (query plan)
Deep learning keretrendszerek	TensorFlow gráfjai
Build rendszerek	pl. Bazel, CMake: mit kell mikor fordítani

---

🔁 Algoritmusok DAG-hoz

• Topological Sort (Kahn’s algorithm vagy DFS-alapú)
• Longest Path in DAG (dinamikus programozással: O(V + E))
• Critical Path Method (projektmenedzsment)
• Cycle detection (ha van ciklus → nem DAG)

---

✅ Példák programozásban

C++ topológiai sorrend (DFS alapú):

void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& s) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u]) dfs(u, adj, visited, s);
    }
    s.push(v);
}

vector<int> topoSort(int V, vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    stack<int> s;
    for (int i = 0; i < V; ++i) {
        if (!visited[i]) dfs(i, adj, visited, s);
    }

    vector<int> result;
    while (!s.empty()) {
        result.push_back(s.top()); s.pop();
    }
    return result;
}

---

🚫 Mi NEM DAG?

• Ha van visszacsatolás (pl. A → B → A) → nem DAG
• Ha egy gráf nem irányított → alapértelmezés szerint nem tekinthető DAG-nak

---

🧾 Összefoglalás

Jellemző	DAG
Irányított?	✅ Igen
Körmentes?	✅ Igen
Lehet topológiai sorrendje?	✅ Igen
Példák	Fordító, Git, Task scheduler

A DAG tehát olyan eszköz, amellyel függőségi viszonyokat lehet hatékonyan modellezni és feldolgozni.

További információk

• directed acyclic graph - Szótár.net (en-hu)
• directed acyclic graph - Sztaki (en-hu)
• directed acyclic graph - Merriam–Webster
• directed acyclic graph - Cambridge
• directed acyclic graph - WordNet
• directed acyclic graph - Яндекс (en-ru)
• directed acyclic graph - Google (en-hu)
• directed acyclic graph - Wikidata
• directed acyclic graph - Wikipédia (angol)