graph data type

Angol

Főnév

graph data type (tsz. graph data types)

1. (informatika, mesterséges intelligencia) A Graph (gráf) ADT (Abstract Data Type) olyan általános adatszerkezetet definiál, amely egy csúcsok (vertices, nodes) és élek (edges, arcs) halmazát tárolja, valamint a köztük lévő kapcsolatokat (incidencia‐, szomszédsági relációt). A gráf ADT feladata, hogy absztrakt módon kezelje a hálózatoszerű adatokat — utakat, kapcsolódásokat, függőségeket stb. — anélkül, hogy a felhasználónak a belső reprezentációval (mátrix, lista, incidens‐tábla) kellene törődnie.

---

1. Mit tárolunk a gráfban?

• V: csúcsok halmaza (pl. V = {v1, v2, …, vn})
• E: élek halmaza, amelyek két csúcsot kötnek össze.
  • Iránnyal nem rendelkező gráf: E ⊆ {{u,v} | u,v ∈ V, u≠v}
  • Irányított gráf (digraph): E ⊆ {(u,v) | u,v ∈ V, u≠v}
  • Élsúlyok (weighted graph): minden élhez rendelünk egy súlyt w: E→ℝ

---

2. Elsődleges műveletek (Graph ADT API)

Művelet	Leírás
CreateGraph(n)	Üres gráf létrehozása n csúccsal (vagy dinamikusan bővíthető).
addVertex(v)	Új csúcs beszúrása a gráfba.
removeVertex(v)	Adott csúcs és az abból induló/érkező élek eltávolítása.
addEdge(u,v[,w])	Él beszúrása (esetleg súllyal) u→v vagy {u,v} között.
removeEdge(u,v)	Él eltávolítása u→v vagy {u,v} között.
**vertexCount() →	V	**	Csúcsok száma.
**edgeCount() →	E	**	Élek száma.
adjacent(u,v) → bool	Igaz, ha u és v között van él (vagy u→v).
neighbors(u) → List<V>	A u-ból közvetlenül elérhető szomszéd csúcsok listája.
getWeight(u,v) → w	Él súlya (ha súlyozott és ha létezik él).
transpose() → Graph	Irányított gráf esetén a nyilak irányának megfordítása.
clear()	Az összes csúcs és él törlése, üres gráf.

---

3. Kiegészítő műveletek és algoritmusok

• Traversal / bejárás
  • BFS (Breadth-First Search): távolság vagy szint szerinti bejárás.
  • DFS (Depth-First Search): mélységi bejárás, cikluskidolgozás, top‐sorting, komponensek felderítése.
• Shortest Path
  • Dijkstra (nemnegatív súlyok), Bellman-Ford (negatív élekkel).
• Minimum Spanning Tree
  • Kruskal, Prim algoritmus.
• Connectivity / Komponensek
  • Union‐Find (disjoint‐set) a komponensek folyamatos követéséhez.
  • Kosaraju, Tarjan erősen összefüggő komponensekhez.
• Cycle detection (DFS‐alapú, in‐edge kimutatás).
• Topological sort (irányított aciklikus gráfokra).

---

4. Belső reprezentációk

4.1. Adjacency Matrix (szomszédsági mátrix)

   v1 v2 v3 ... vn
v1  0  w  0 ... 0
v2  w  0  w ... 0
...

• matrix[u][v] = w ha van él u→v (súlyozott), 1 ha egyszerű.
• Előny: O(1) az adjacent(u,v) és getWeight(u,v).
• Hátrány: memóriaigény O(n²), iterálás szomszédokon O(n) minden csúcsnál.

4.2. Adjacency List (szomszédsági lista)

vector<vector<pair<int,Weight>>> adj;  // csúcs → lista< (szomszéd, súly) >

• Előny: memóriaigény O(n + m) (m = élek száma), gyors iterálás csak a valódi szomszédokon.
• Hátrány: adjacent(u,v) O(deg(u)), getWeight(u,v) O(deg(u)).

4.3. Edge List (él‐lista)

vector<Edge> edges;  // Edge = {u,v,weight}

• Egyszerű, de nem alkalmas gyors szomszéd‐keresésre. Tetszőleges él‐vezérlésre (pl. Kruskal‐hoz).

4.4. Incidence List / Incidence Matrix

• Ritkábban használt, ahol az élekre és csúcsokra egyaránt mutatók vannak tárolva.

---

5. Komplexitások

Művelet	Mátrix	Lista	Él‐lista
addVertex	O(n²)¹	O(1)	O(1)
removeVertex	O(n²)¹	O(deg(v))	O(m)
addEdge(u,v)	O(1)	O(1)	O(1)
removeEdge(u,v)	O(1)	O(deg(u))	O(m)
adjacent(u,v)	O(1)	O(deg(u))	O(m)
neighbors(u)	O(n)	O(deg(u))	O(m)
BFS/DFS	O(n²)	O(n + m)	O(n + m)

¹ Mátrix esetén a csúcsok hozzáadása/el­ávolítása átméretezést igényel.

---

6. Tipikus implementációk a standard könyvtárakban

• C++
  • Adjacency List: vector<vector<int>>, vagy vector<list<int>>
  • Graph class saját wrapperrel (nincs beépített “Graph” STL)
• Java
  • List<List<Integer>> adj = new ArrayList<>();
• Python
  • defaultdict(list) vagy dict[int, list[int]]

---

7. Mikor melyik reprezentáció?

1. Sűrű gráf (m≈n²) → Adjacency Matrix
2. Ritka gráf (m ≪ n²) → Adjacency List
3. Él‐orientált algoritmus (Kruskal) → Edge List
4. Gyors szomszéd‐ellenőrzés (adjacent(u,v)) → Matrix
5. Memória‐kímélő és átfogó bejárás → List

---

Összefoglalás

A Graph ADT:

• Definiálja az alapvető gráf‐műveleteket (csúcs/él beszúrás, eltávolítás, szomszéd‐lekérdezés).
• Elrejti a belső reprezentációt (mátrix, lista, él‐lista).
• Támogatja a klasszikus algoritmusokat (BFS, DFS, Dijkstra, Kruskal, Prim, topological sort).
• Rugalmas, mert a különböző igényekhez (sűrű/rika, orientált/nem, súlyozott/nem) optimális adattárolást választhatjuk.

Ezzel a absztrakt réteggel az algoritmusok és applikációk gráfokat kezelő részét könnyedén, hatékonyan és portábilis módon valósíthatjuk meg.

További információk

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