Adatszerkezetek�2022.11.09

Ismétlés

Hasító táblázatok

• Egy nagyon primitív megoldásban a már előzőekben megismert függvény is alkalmazható lenne

​

​

Tárolandó elemek

Tárolási hely

Hasító táblázatok

• Teszteljük a megoldást
• Egy pár számig jól működik az elgondolás

Hasító táblázatok

Ütközésfeloldásra a következő megoldásokat használjuk:

• Zárt hashing
• Láncolás (chaining)
• Nyílt hashing
• Lineáris kipróbálás (linear probing)
• négyzetes kipróbálás (quadritic probing)
• Dupla hasítás (double hashing)

Láncolás (chaining)

• Ebben az esetben a 3. elem láncában kell keresni az elemet
• Ez a megoldás nem O(1) , de jobb mint O(log n)

Lineáris kipróbálás

• Nézzünk meg a képletet keresésre
• Ismét visszavezettük arra az állapotra amikor az első vagy az őt követő helyen van az érték

Négyzetes kipróbálás

• Az alap elgondolás megegyezik a lineáris kipróbálás műveletével, de az f(i)=i helyett f(i)= i² -el számolunk

​

Lineáris próba, törlés

• A törlés problematikusabb
• Ha valóban törlünk hibás működést kapnánk
• Ha csak törlünk egy elemet, akkor a következő beillesztésnél a lináris próba idő előtt leállhat

Lineáris próba, törlés

• A törlés

Gráfok

Gráfok�

• Az első olyan feladat, amelyet gráfok segítségével oldottak meg, a königsbergi hidak problémája.

​

​

​

​

​

​

​

​

​

• A város lakói olyan sétát szerettek volna tenni, ha lehet úgy, hogy mind a hét hídon átsétáljanak, de csak egyszer mindegyiken, és vissza jussanak a kiinduló pontba.

​

​

​

Bevezető a gráfokba

​

• Az internet is felfogható egy gráfként, de akár egy adott épület villamos hálózata is.

​

• Az emberek közötti ismeretségek is kezelhetők gráfként (Facebook).

​

• A GPS is gráfként kezeli a térképeket, és gráfelméleti algoritmusok használatával állítja elő az útvonalat.

​

• A kémiai molekulák is vizsgálhatók gráfként, mint az atomok és a köztük lévő kötések megjelenítése.

​

Bevezető a gráfokba

​

​

• Gráf: G(V,E)
• Ahol:

G – gráf pontjai halmaza

V - csúcsok(az angol vertex= csúcs szóból)

E - élek (az angol edge = él szóból)

​

​

​

​

​

• Amennyiben a gráfok rendezett párok halmazáról beszélünk, úgy fontos kiemelni, hogy:

​

​

• Rendezetlen esetén:

​

Bevezető a gráfokba

​

​

• A következő képen egy 10 élű és 8 csomópontos gráfot láthatunk.

​

• Mivel a gráf minden pontjának kell, hogy legyen valamilyen elnevezése.

​

​

​

​

Csomópontok halmaza:

​

Élek halmaza:

​

Bevezető a gráfokba

​

• Irányított (Digraph) vs. Irányítatlan gráf

​

Bevezető a gráfokba

​

• A gráfok egy másik tulajdonsága a súlyozás.

​

• Egy gráf súlya alatt értjük azt a folyamatot melynek során egyes éleknek különböző nagyságú értékeket adunk.

​

• Egy gráf ebből adódóan lehet súlyozott vagy súlyozatlan.

​

• Pl. egy vasúti hálózat gráf modellje:

​

Bevezető a gráfokba

​

• Belgiumi telefonbeszélgetések – Flamand/Vallon

http://iopscience.iop.org/article/10.1088/1742-5468/2008/10/P10008/fulltext/

​

Bővebben Belgiumról:

​

https://www.youtube.com/watch?v=QlwHotpl9DA

A gráfok tulajdonságai

Topológia

A gráfok tulajdonságai

​

• Egy gráfunk lehet irányított és irányítatlan

​

• Az élei lehetnek súlyozottak és súlyozatlanok

​

• A standard tulajdonságokkal rendelkező gráfokat egyszerű gráfoknak hívjuk.

​

• Azonban vannak ön vagy párhuzamos élekkel rendelkező gárfok melyet összetett gráfoknak nevezzük.

​

​

​

A gráfok tulajdonságai

​

• Többélű avagy párhuzamos hivatkozás.

​

​

​

​

​

​

• Mi értelme van a párhuzamos éleknek?
• Vegyünk egy példát: Repülőgépek a különböző városok között.

​

​

​

A gráfok tulajdonságai

​

• Amennyiben egyszerű gráfokkal akarunk dolgozni mennyi lehet az élek maximális száma?

​

• Vegyük a következő példát:

​

​

​

A gráfok tulajdonságai

​

• A legkisebb élszám: v=4,e=0

​

​

​

​

​

• Irányított gráf esetén v=4,e=12

​

​

​

​

• Irányítatlan gráf esetén: v=4,e=6

​

​

​

A gráfok ábrázolása

A gráfok ábrázolása

​

• A gráfunk pontokból (NODE, Vertex) és élekből (Edge) épülnek fel.

​

• Hogyan tudnánk ezt ábrázolni?

​

A gráfok ábrázolása

​

• Az előző megoldás túl bonyolult keresésének és kezelésének megoldására alkalmazzák a SZOMSZÉDOSSÁGI MÁTRIX-okat.

​

​

​

A gráfok ábrázolása

​

• Az előző megoldás túl bonyolult keresésének és kezelésének megoldására alkalmazzák a SZOMSZÉDOSSÁGI MÁTRIX-okat.
• Irányítatlan gráfoknál a szomszédsági mátrixunk főátló szerint tükröződik.

​

​

​

A gráfok ábrázolása

​

• Ahogy az előző ábrázolásnál, úgy a szomszédossági mátrixnál is módunk van az élek súlyainak a tárolására.

​

• Ezt a következőképpen tehetjük meg.

​

​

​

A gráfok ábrázolása

​

• A szomszédossági mátrixok kezelésének számtalan előnye van, azonban O(v*v) helyfoglalása miatt aligha nevezhető memória barát folyamatnak.

​

• Épp ezért a tömbök és a szomszédsági lista mellett ábrázolhatjuk a gráfunkat SZOMSZÉDOSSÁGI LISTÁBAN is.

​

​

​

​

​

A gráfok ábrázolása

​

​

• Vegyünk egy egyszerű példát:

​

• 10^9 Facebook „barátságot” akarunk ábrázolni
• 1 felhasználónak 1000 „barátja” van
• A többi mezőben 0 értékek találhatóak

1-es elemek száma 1000 = 1KB

0-ás elemek száma 10^9-1000 ~ 1Gb

​

​

​

A gráfok ábrázolása

​

• Mi történne azonban akkor, ha csak azokat az értékeket próbálnánk meg eltárolni, amelyek kapcsolatban állnak egymással?

​

• Csökken a memória igény.

​

​

​

​

​

​

​

​

• Ennek megvalósításához egyik legjobb megoldást a LISTÁK nyújtják.

​

​

​

A gráfok ábrázolása

​

• A szomszédossági mátrix helyett tehát használhatunk valami ilyet is.

​

​

​

​

​

​

​

​

​

​

• Ezzel a megoldással ugyanazt az értéket tároljuk el, kevesebb helyen

​

A gráfok ábrázolása

​

​

​

​

​

A gráfok ábrázolása MÁS nyelveken

​

• Erről bővebben itt olvashatunk:

​

https://www.programiz.com/dsa/graph-adjacency-list

​

​

A gráfok bejárása

A gráfok bejárása

​

• A gráfok két alapvető bejárási módja a mélységi és a szélességi bejárás.

​

• Az ezekkel a módszerekkel bejárt útvonalat mélységi vagy szélességi feszítő fának is szokták nevezni.

​

• Alapvető felépítésük megegyezik a bináris fáknál tanultakkal.

​

​

​

​

https://www.cs.usfca.edu/~galles/visualization/DFS.html

https://visualgo.net/en/dfsbfs

​

A gráfok bejárása

​

​

• A bejárási stratégiákról megkapóan egyszerű példája, amikor az öreg városka girbe-gurba utcáin bolyongó kopott emlékezetű lámpagyújtogatót képzeljük el.

​

​

​

https://www.cs.usfca.edu/~galles/visualization/DFS.html

https://visualgo.net/en/dfsbfs

​

A gráfok bejárása

​

• Az egyik eljárás szerint a lámpagyújtogatót egy este nagyszámú barátja elkíséri a városka főterére, ahol együtt meggyújtják az első lámpát.

​

• Utána annyi felé oszlanak, ahány utca onnan kivezet.

​

• A különvált kis csapatok meggyújtják az összes szomszédos lámpát, majd tovább osztódnak.

​

• A városka lámpáit ilyen módon széltében terjeszkedve érik el.

​

Szélességi bejárás megvalósítása

​

• A megvalósításhoz sorra van szükségünk amely képes az elemeket tárolni.

​

• Azonban, már rögtön a kezdetekor láthatóvá válik, hogy ha minden elemet a bedobálnánk a sorba akkor rengeteg redundáns (ismétlődő) adatunk lenne.

​

​

​

A gráfok bejárása

​

• E probléma megoldására valahogy jeleznünk kell a programunknak, hogy egy-egy VERTEX-et már kiírtunk.

​

• Ehhez egy új mezőt adunk a gráfunknak ez pedig a megnézve boolean változó lesz.

​

A gráfok bejárása

​

• Nézzünk egy példát melyen keresztül egyértelművé válik a bejárás működése.

​

• Vegyünk egy egyszerű gráfot.

​

​

A gráfok bejárása

​

• Kiválasztjuk az induló elemünket. Esetünkben ez a 0 lesz.

​

• Beolvassuk az elemünkhez kapcsolódó szomszédokat a SORBA, állítjuk azok megnézve változóját TRUE-ra és kiírjuk az elemünket a képernyőre.

​

​

​

A gráfok bejárása

​

• Következő lépés az 1-es VERTEX-et írjuk ki illetve a SORBA rakjuk a hozzá tartozó olyan elemeket melynek megnézve értéke FALSE.

​

• Esetünkben egy ilyen elem sincs.

​

​

​

A gráfok bejárása

​

• Következő lépés az 2-es VERTEX-et írjuk ki illetve a SORBA rakjuk a hozzá tartozó olyan elemeket melynek megnézve értéke FALSE.

​

• Esetünkben ez a 4-es elem.

​

​

​

A gráfok bejárása

​

• Következő lépés a 3- as VERTEX-et írjuk ki illetve a SORBA rakjuk a hozzá tartozó olyan elemeket melynek megnézve értéke FALSE.

​

• Esetünkben egy ilyen elem sincs.

​

​

​

A gráfok bejárása

​

• Következő lépés a 4-es VERTEX-et írjuk ki illetve a SORBA rakjuk a hozzá tartozó olyan elemeket melynek megnézve értéke FALSE.

​

• Esetünkben egy ilyen elem sincs.

​

​

​

A gráfok bejárása

​

• Következő lépés a 4-es VERTEX-et írjuk ki illetve a SORBA rakjuk a hozzá tartozó olyan elemeket melynek megnézve értéke FALSE.

​

• Esetünkben egy ilyen elem nincs, tehát kiürült a listánk és leállt a programrész.

​

​

​

Feladat

​

• Mi a szomszédsági listás ábrázolása következő gráfnak ?
• MI a szomszédsági mátrixa következő gráfnak?

​

• Az 5 csúcsból kiindulva hajtsunk végre szélességben keresést!
• https://visualgo.net/en/dfsbfs

​

​

​

Feladat

​

• Mi a szomszédsági listás ábrázolása következő gráfnak ?
• MI a szomszédsági mátrixa következő gráfnak?

​

• Az 5 csúcsból kiindulva hajtsunk végre szélességben keresést!

​

​

Feladat

​

• Mi a szomszédsági listás ábrázolása következő gráfnak ?
• MI a szomszédsági mátrixa következő gráfnak?

​

• Az 5 csúcsból kiindulva hajtsunk végre szélességben keresést!

​

​

Mélységi bejárás

• A mélységi bejárás szemléltetéséhez is „az öreg városka girbe-gurba utcáin bolyongó kopott emlékezetű lámpagyújtogató” példát vesszük szemügyre.

​

• A lámpagyújtogató az első, majd a további lámpák felgyújtása után mindig egy olyan utcán indul tovább, amelyikben még nem lát fényt, és elérve a következő sarokhoz, meggyújtja az ott elhelyezett lámpát.

​

Mélységi bejárás

​

• Ha egy lámpa alól körül nézve már minden onnan kiinduló utcából fényt lát, akkor visszamegy arra, ahonnan ide érkezett, és onnan egy még meg nem gyújtott lámpa irányába indul.

​

• Ha ilyet nem lát, akkor innen is visszamegy a megelőző sarokra.

​

• Egy idő után visszatért eredeti kiinduló helyére, és ekkor már minden innen elérhető köztéri lámpa világít.

Mélységi bejárás

• Ha fentről néznénk a várost, ahogy kigyulladnak a lámpák, ezúttal azt látnánk, hogy egy pontból egy útvonal mentén terjed a világosság.

​

5 6

7 8

9 10

11 12

Mélységi bejárás

• A mélységi bejárás is hasonló elven működik mint a szélességi bejárás. Itt is használnunk kell a megnézve változót.

​

• A megvalósításhoz használhatunk vermet vagy rekurzív metódust.

​

• A mélységi bejárás során keletkezett útvonalat mélységi feszítő fának is szokás nevezi.

Mélységi bejárás

• Nézzünk egy példát a mélységi bejárás megvalósítására.

​

• A részletekbe menő magyarázattól most eltekinthetünk, hiszen az ábra magáért beszél.

Mélységi bejárás

Mélységi bejárás

Mélységi bejárás

• A következő gráfon hajtsuk végre a mélységi keresést!
• 0. pontból indulva
• https://visualgo.net/en/dfsbfs

Mélységi bejárás

• A következő gráfon hajtsuk végre a mélységi keresést!
• 0. pontból indulva

Topologikus rendezés

• Egy G = (V, E) irányított gráf topologikus rendezése a csúcsainak sorba rendezése úgy, hogy ha G-ben szerepel az (u, v) él, akkor u előzze meg v-t a sorban.

​

• Ha a gráf tartalmaz irányított kört, akkor nincs ilyen sorba rendezés.

​

• Eljárás: minden v csúcsra meghatározzuk az f [v] elhagyási időt és az egyes csúcsok elhagyásakor szúrjuk be azokat egy láncolt lista elejére

Topologikus rendezés

Határozzuk meg a következő gráf topologikus rendezését!

​

Topologikus rendezés

Topologikus rendezés

Topologikus rendezés

Topologikus rendezés

Topologikus rendezés

Topologikus rendezés

Topologikus rendezés