1 of 50

Adatszerkezetek�2022.11.16

2 of 50

Ismétlés

3 of 50

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 visszajussanak a kiindulópontba.

​

​

​

4 of 50

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:

​

5 of 50

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.

​

​

​

6 of 50

A gráfok ábrázolása

​

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

​

​

​

​

​

​

​

​

​

​

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

​

7 of 50

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

​

  • A megvalósításhoz sorra van szükségünk mely 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.

​

​

​

8 of 50

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.

​

​

9 of 50

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.

​

10 of 50

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.

11 of 50

Ismétlés

12 of 50

Minimális feszítőfák

13 of 50

14 of 50

Hogyan találjuk meg a legkisebb költségű útvonalat? (Minimális feszítőfa)

15 of 50

Hogyan találjuk meg a legkisebb költségű útvonalat? (Minimális feszítőfa)

Végig próbálunk minden opciót!?

16 of 50

Prim algoritmus

  • egyetlen fát növesztünk
  • tetszőleges gyökér pontból indulva
  • minden lépésben új csúcsot kötünk be a fába
  • legolcsóbb éllel elérhető csúcsot választjuk
  • Mohó algoritmus!

17 of 50

Prim algoritmus

18 of 50

Prim algoritmus

Induljunk el az 1 elemtől. Keressük meg a legkisebb súlyú útvonalat

19 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

20 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

21 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

22 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

23 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

24 of 50

Prim algoritmus

Keressük meg a következő legkisebb súlyú útvonalat amely kapcsolódik a jelenlegi (új) gráfunkhoz.

25 of 50

Kruskal algoritmus

26 of 50

Kruskal algoritmus

  • A Kruskal-algoritmus Joseph Kruskal (1928–2010) amerikai matematikustól és informatikustól származik, aki 1956-ban írta le.

​

  • Ez egy súlyozott gráfokat feldolgozó mohó algoritmus.

​

  • Ha a gráf összefüggő, akkor minimális feszítőfa megalkotására szolgál, ha nem, akkor minimális feszítő erdőt hoz létre.

​

​

​

​

27 of 50

Kruskal algoritmus

Kruskal algoritmus

  • Minimális fák erdejét tároljuk
  • Kezdetben minden pont egy külön fa
  • Minden lépésben a legkisebb, két fát összekötő élt húzzuk be (egyesítjük egyetlen fává a két fát)

​

Mohó algoritmus!

​

28 of 50

Kruskal algoritmus

  • Kezdjük az első lépéssel és keressük meg a legkisebb élet

​

​

29 of 50

Kruskal algoritmus

  • Kezdjük az első lépéssel és keressük meg a következő legkisebb élet

​

​

30 of 50

Kruskal algoritmus

  • Kezdjük az első lépéssel és keressük meg a következő legkisebb élet

​

​

31 of 50

Kruskal algoritmus

  • A következő legkisebb súlyú él a 7-4(18) lenne, de a Kruskal algoritmus kimondja, hogy nem lehet kör a feszítő fában, így ez a megoldás ELFOGADHATATLAN
  • Vegyük helyette a rákövetkező elemet

​

​

32 of 50

Kruskal algoritmus

  • Kezdjük az első lépéssel és keressük meg a következő legkisebb élet

​

​

33 of 50

Kruskal algoritmus

  • Kezdjük az első lépéssel és keressük meg a következő legkisebb élet

​

​

34 of 50

Kruskal vs Prim

  • Kruskal O(ElogE)

  • Prim O(ElogV)

(tovább gyorsítható O(E+VlogV))

​

Sűrű gráfok esetén (E nagy) Prim előnyösebb, egyébként Kruskal egyszerűbb adatszerkezetet használ

35 of 50

Legrövidebb út

36 of 50

Dijkstra algoritmus

37 of 50

Dijkstra algoritmus

  • A Dijkstra-algoritmus egy mohó algoritmus, amivel irányított vagy irányítás nélküli gráfokban lehet megkeresni a legrövidebb utakat egy adott csúcspontból kiindulva.

​

  • Az algoritmust Edsger Wybe Dijkstra holland informatikus fejlesztette.

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

7

E

D

1

A

E

2

D

Mit jelent a mohó algoritmus? Katt ide

38 of 50

Dijkstra algoritmus

Diskstra algoritmus

  • azokat a csúcsokat tárolja, amihez már megtalálta a legrövidebb utat
  • minden lépésben eggyel bővíti az elért csúcsok halmazát (legkisebb legrövidebb úttal bíró csúcsot választja)

Mohó algoritmus!

​

39 of 50

Dijkstra algoritmus

  • Az algoritmus működése a következőképpen néz ki.

​

  • Két tömböt rendelünk a gráfunkhoz.

​

Megnézve = [] NemMegnézve = [A,B,C,D,E]

​

  • Megnézzük, hogy az A-ból A-ba mekkora a távolság, a többit inf.-ra állítjuk

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

inf

​

C

inf

​

D

inf

​

E

inf

​

40 of 50

Dijkstra algoritmus

  • Most megnézzük, hogy az A még nem látogatott szomszédjaihoz, hogyan tudunk eljutni.

​

  • Amennyiben a kalkulált érték kisebb mint az eddig ismert érték, úgy felülírjuk azt.

​

Megnézve = [A] NemMegnézve = [B,C,D,E]

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

6

A

C

inf

​

D

1

A

E

inf

​

41 of 50

Dijkstra algoritmus

  • Következő lépésben kiválasztjuk azt a legkisebb VERTEXET a listából melyet még nem látogattunk meg. Esetünkben ez a D.

​

  • Most a D szomszédjait kell megvizsgálnunk.

​

Megnézve = [A] NemMegnézve = [B,C,D,E]

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

inf

​

D

1

A

E

2

D

42 of 50

Dijkstra algoritmus

  • Következő lépésben kiválasztjuk azt a legkisebb VERTEXET a listából melyet még nem látogattunk meg. Esetünkben ez a E.

​

  • Most a E szomszédjait kell megvizsgálnunk.

​

Megnézve = [A,D] NemMegnézve = [B,C,E]

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

7

E

D

1

A

E

2

D

43 of 50

Dijkstra algoritmus

  • Következő lépésben kiválasztjuk azt a legkisebb VERTEXET a listából melyet még nem látogattunk meg. Esetünkben ez a B.

​

  • Most a B szomszédjait kell megvizsgálnunk.

​

Megnézve = [A,D,E] NemMegnézve = [B,C]

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

7

E

D

1

A

E

2

D

44 of 50

Dijkstra algoritmus

  • Következő lépésben kiválasztjuk azt a legkisebb VERTEXET a listából melyet még nem látogattunk meg. Esetünkben ez a C.

​

  • Most a C szomszédjait kell megvizsgálnunk.

​

Megnézve = [A,D,E,B] NemMegnézve = [C]

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

7

E

D

1

A

E

2

D

45 of 50

Dijkstra algoritmus

  • Megkaptuk a végeredményt

​

VERTEX

Legr. A-ból

Előző elem.

A

0

​

B

3

D

C

7

E

D

1

A

E

2

D

46 of 50

Feladatok

47 of 50

Feladatok

48 of 50

Feladatok

49 of 50

Feladatok

50 of 50

Ajánlott linkek

​