Üdvözlöm, Ön a
graph data type szó jelentését keresi. A DICTIOUS-ban nem csak a
graph data type szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
graph data type szót egyes és többes számban mondani. Minden, amit a
graph data type szóról tudni kell, itt található. A
graph data type szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
graph data type és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
graph data type (tsz. graph data types)
- (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)
|
É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 = 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]
7. Mikor melyik reprezentáció?
- Sűrű gráf (m≈n²) → Adjacency Matrix
- Ritka gráf (m ≪ n²) → Adjacency List
- Él‐orientált algoritmus (Kruskal) → Edge List
- Gyors szomszéd‐ellenőrzés (
adjacent(u,v)) → Matrix
- 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.