1 of 57

Gráfok�2024.11.20

2 of 57

Ismétlés

3 of 57

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

4 of 57

Hasító táblázatok

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

5 of 57

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)

6 of 57

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)

7 of 57

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

8 of 57

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)= i2 -el számolunk

​

9 of 57

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

10 of 57

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

  • A törlés

11 of 57

Gráfok

12 of 57

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.

​

​

​

13 of 57

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.

​

14 of 57

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:

​

15 of 57

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:

​

16 of 57

Bevezető a gráfokba

​

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

​

17 of 57

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:

​

18 of 57

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

19 of 57

A gráfok tulajdonságai

Topológia

20 of 57

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.

​

​

​

21 of 57

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.

​

​

​

22 of 57

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:

​

​

​

23 of 57

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

​

​

​

24 of 57

A gráfok ábrázolása

25 of 57

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?

​

26 of 57

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.

​

​

​

27 of 57

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.

​

​

​

28 of 57

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.

​

​

​

29 of 57

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.

​

​

​

​

​

30 of 57

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

​

​

​

31 of 57

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.

​

​

​

32 of 57

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

​

33 of 57

A gráfok ábrázolása

​

​

​

​

​

34 of 57

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

​

  • Erről bővebben itt olvashatunk:

​

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

​

​

35 of 57

A gráfok bejárása

36 of 57

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

​

37 of 57

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

​

38 of 57

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.

​

39 of 57

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.

​

​

​

40 of 57

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.

​

41 of 57

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.

​

​

42 of 57

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.

​

​

​

43 of 57

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.

​

​

​

44 of 57

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.

​

​

​

45 of 57

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.

​

​

​

46 of 57

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.

​

​

​

47 of 57

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.

​

​

​

48 of 57

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

​

​

​

49 of 57

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!

​

​

50 of 57

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!

​

​

51 of 57

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.

​

52 of 57

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.

53 of 57

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.

​

  1. 2

​

​

​

​

3 4

5 6

7 8

9 10

11 12

54 of 57

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.

55 of 57

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.

56 of 57

Mélységi bejárás

57 of 57

Mélységi bejárás