Programozási Paradigmák. és Technikák

Programozási Paradigmák és Technikák Láncolt Lista Generikus osztályok Láncolt Lista megvalósítása

Bináris keresőfa (BST) BST megvalósítása

Gráfok Dijkstra algoritmus Kruskal algoritmus

V 1.0

Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

1

Programozási Paradigmák és Technikák Láncolt Lista Generikus osztályok © Erdélyi Krisztina Láncolt Lista megvalósítása



V 1.0


2

Generikus Osztályok • • • • • •

V 1.0

Generikus osztályok Generikus metódusok Megszorítások Statikus tagok Öröklés A generikus osztályok működése a .NET-ben


3

Bevezetés – feladat • Cél: személyeket tároló halmaz létrehozása, egy elemet egyszer tartalmazhat, a lehető legáltalánosabb módon • Milyen elemekből álljon a halmaz? – Személy – akkor a kutya-klubhoz át kell írni – A személy és a kutya őse – ez biztos, hogy elég általános? – Object (mindennek az őse) - ez lehet megoldás ArrayList, .NET1, csak object-et tárol, állandó castolás – A típust adjuk meg paraméterként, így elég a deklarációban megadni a konkrét típust Vizsgáljuk meg ezt közelebbről! V 1.0


4

Generics • Más néven sablon vagy template • Paraméterezett típus vagy metódus • Minden egyes paraméter egy még meg nem határozott típus helye • Az osztály tervezésekor csak T néven hivatkozok a típusra, csak az osztály példányosításakor definiálom, hogy ez a T pontosan mi

V 1.0


5

Paraméterezett típusok • A paraméter a típus fejrészében helyezkedik el class MyGenericClass { } • Deklarációnál és példányosításkor az aktuális típus kerül a paraméter helyére MyGenericClass mgcINT = new MyGenericClass(); • A generic-ek tipikusan gyűjtemények létrehozásához valók, mivel a gyűjtemények több típussal is használhatók

V 1.0


6

Generikus gyűjtemények • ArrayList object típust tárol, állandó castolás, elavult • List: Add(), Insert(), Remove(), RemoveAt(), Reverse(), [], Clear(), Contains(), Count • Queue: Enqueue(), Dequeue(), Peek(), Clear(), Contains(), Count • Stack: Push(), Pop(), Peek(), Clear(), Contains(), Count • Lehetőség van több típus használatára: class valami { } • Dictionary: Add(), Remove(), TryGetValue(), Keys, Values, Clear(), ContainsKey(), ContainsValue(), Count V 1.0


7

Saját generikus osztály létrehozása

V 1.0


8

Generikus osztály használata

V 1.0


9

Paraméterezett típus inicializálása • • • •

V 1.0

object valtozo=null; int valtozo=0; string valtozo=””; T valtozo = ???? Nem tudható, hogy érték vagy referencia típusú-e a paraméter Megoldás: default expression T valtozo = – Referenciánál null-t ad vissza default(T); – Érték típusnál bitenkénti nullát


10

Megszorítások • Lefordulnak a következő kódok? • Ha nem, akkor mi a megoldás? • Csak annyit tudhatunk a T típusról biztosan, hogy a System.Object-ből származik • Ezért ennek megfelelően viselkedik

V 1.0


11

Interfész megszorítás class MyClass2 { public void Iterate(T data) { foreach (object item in data) { Console.WriteLine(item); } } Nem biztos, hogy T felsorolható! } (A foreach ciklus akkor működik saját típuson, ha a saját

típus megvalósítja az IEnumerable interfészt, ld. később) class MyClass2 where T : IEnumerable{ public void Iterate(T data) { foreach (object item in data) { Console.WriteLine(item); } } }

OK V 1.0

(Azonos módon interface megszorítással lehet azt garantálni, hogy a T típusnak van egy adott metódusa) Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

12

Konstruktor megszorítás class MyClass { T obj = new T(); } Nem biztos, hogy T-nek van alapértelmezett konstruktora!

class MyClass where T:new() { T obj = new T(); } OK

V 1.0


13

Művelet megszorítás??? class Arithmetic{ Nem biztos, hogy T-n public T Cubed(T number){ return number * number * number; értelmezett a szorzás! } } class Arithmetic where T : System.Int32{ public T Cubed(T number){ return number * number * number; } Érték és primitív típusok }

nem lehetnek megszorítások!

Súlyos korlátja a generics használatának, hogy standard operátorok az érték típusokkal nem használhatók.

V 1.0


14

A Generic korlátja class Program2 { A standard operátorok public T Min(T a, T b) így sem használhatók. where T : IComparable { if (a(T a, T b) } where T : IComparable } { if (a.CompareTo(b)<0) return a; else return b; }… Szabó Zsolt, Óbudai Egyetem, 2011 V 1.0 15 } [email protected]

Megszorítások összefoglalása • • • •

A megszorítások a típus paraméterektől elvárt viselkedést írják le A where kulcsszóval vezetjük be Típusnál és metódusnál is használhatók Fajtáik: – – – – –

Leszármazott (where T : Személy) Interfész (where T: IEnumerable) Érték típus (where T: struct) Referencia típus (where T: class) Konstruktor (where T: new())

• Az alábbi típusok nem lehetnek megszorításban: – – – – – – V 1.0

Lezárt osztályok Primitív típusok System.Array System.Delegate System.Enum System.ValueType Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

16

Generikus metódus • • • •

V 1.0

Tartozhat generikus vagy nem generikus típushoz Azért, mert az osztály generikus, a metódus még nem A metódus generikus, ha saját típusparamétere(i) van(nak) A típusparaméter megjelenhet visszatérési értékként vagy a paraméterlistában


17

Generikus metódusok meghívása • A metódus meghívásakor a paraméterek típusa adja meg a típusparaméter aktuális értékét: int i=Min(2, 3); //egészek float f=Min(2.0, 3.0); //valósak • Két azonos nevű és szignatúrájú metódus nem lehet • És ha T=int? • Ellentmondás esetén a nem-generikus eljárás hívódik meg • Ha két generikus metódus van különböző generikus paraméterrel pl. Method(T arg), Method(U arg), és T és U konkrétan ugyanaz, akkor a metódus meghívásánál jelez hibát.

V 1.0


18

Statigus tagok generikus osztályokban class MyGenericClass { private static int counter = 0; public MyGenericClass() { counter++; } public static void Count() { Console.WriteLine(counter); } }

V 1.0


19

Statikus tagok generikus osztályokban • A statikus tagok eléréséhez be kell helyettesíteni egy konkrét típust a paraméterbe MyGenericClass.Count(); • Különböző behelyettesített típusokhoz különböző statikus tagok tartoznak • A statikus konstruktor implicit meghívódik, és a behelyettesített típusnak megfelelően inicializálja a statikus mezőket

V 1.0


20

Generikus osztályok az öröklésben • Generikus osztály lehet őse generikus és nem generikus osztálynak • Generikus osztály származhat generikus vagy nem generikus osztályból • De mindkét állítás csak bizonyos esetekben igaz! • Az utód példányosításakor a típusparaméterek értékét mindenképpen meg kell határozni • Ha Derived : BaseGeneric , és new Derived() a T típus mindkét osztályban int lesz. • Ha Derived : BaseGeneric, és new Derived() az ős T típusparamétere nincs definiálva, NEM MEGENGEDETT • Ha Derived : BaseGeneric, és new Derived() az U típus nincs definiálva az ősosztályban, NEM MEGENGEDETT

V 1.0


21

Generikus osztályok az öröklésben

Melyik eset lehetséges?

V 1.0


22

Generikus osztályok az öröklésben és a .NET-ben • A típusra vonatkozó ős osztálybeli megszorításokat az utódosztályban meg kell ismételni • Az utódosztály tartalmazhat további megszorításokat

• Nem nyelvspecifikus, minden felügyelt nyelvben elérhető • A köztes kódra való fordítás során metaadatok és a generic-ekre vonatkozó MSIL kód áll elő, a JIT fordítás során történik meg a konkrét típusok behelyettesítése

V 1.0


23




V 1.0


24

IEnumerable / IEnumerator • A foreach ciklus akkor működik saját típuson, ha a saját típus megvalósítja a IEnumerable interfészt • Ez az interfész előírja a GetEnumerator() eljárást, ami visszaad egy olyan objektumpéldányt, ami megvalósítja az IEnumerator interfészt • Az IEnumerator előírja a következő műveleteket: Aktuális elem olvasása (Current), következő elemre mozgás (MoveNext()), visszaállás az első előtti elemre (Reset()) lista bejárása • Mindegyik interfész előírja a nemgenerikus (object) változatot is • Saját enumerator helyett bizonyos esetben meglévő enumeratort is használhatunk, ha olyan struktúrába rendezhetőek az adatok, ahol ez elérhető (tömb / Szabó List) Zsolt, Óbudai Egyetem, 2011

V 1.0

[email protected]

25

Láncolt Lista

• Egyszeresen láncolt, ciklikus, kétszeresen láncolt listák (ld. Ea.) • Strázsa-elemes, rendezett láncolt listák (ld. Ea.) • Órai feladat: telefonkönyv-bejegyzések (név, cím, telefonszám) egyirányú, nem rendezett láncolt listába fejtése • ZH: egyéb láncolás is lehetséges

V 1.0


26

A fejlesztés menete 1. Generikus osztályként megtervezzük a ListaElem osztályt, amely egy T típusú referenciát tárol, valamint egy referenciát a következő listaelemre 2. Generikus osztályként megtervezzük a Lista osztályt, amely tárol egy referenciát az első listaelemre, emellett itt implementáljuk az eljárásokat is: a) public void Beszúr(T elem) b) public T Keres(T mitkeres, out bool talalt) c) public bool Töröl(T elem) d) public bool Töröl(int index) e) Cél: a lista osztályt be lehessen járni foreach ciklussal 3. A foreach ciklus működése miatt tervezünk egy saját felsorolót 4. Megtervezzük a bejegyzés osztályt, amit ténylegesen tárolni akarunk 5. Tesztprogram írása V 1.0


27

ListaElem • T típusú adatot tárol + egy referenciát a következő elemre • Tulajdonságok, konstruktor, ToString()

Lista + ListaEnumerator • • • • • •

V 1.0

ListaElem Elso; + konstruktor? public void Beszúr(T elem) PPT előadás public T Keres(T mitkeres, out bool talalt) PPT előadás, p.Elem.Equals(mitkeres) public bool Töröl(T elem) PPT előadás, ugyanúgy Equals() public bool Töröl(int index) index szerinti törlés Cél: a lista osztályt be lehessen járni foreach ciklussal saját felsoroló készítése: Current, MoveNext(), Reset()


28

Telefonkönyv bejegyzés • Név + Cím + Telefonszám • Konstruktor + ToString() • Speciális Equals() : rész-egyenlőség visszaadott értéke is true

Tesztprogram • Lista telefonszámok = new Lista(); • Bejegyzes keresett, talalt; • bool van;

V 1.0


29

Tesztprogram

V 1.0


30

Tesztprogram

V 1.0


31




V 1.0


32

Bináris keresőfa

V 1.0


33

A fejlesztés menete 1. Generikus osztályként megtervezzük a csucs osztályt, amely egy T típusú referenciát tárol, valamint egy referenciát a jobb és a bal oldali gyermek-elemre 2. Generikus osztályként megtervezzük a fa osztályt, amely tárol egy referenciát a gyökérelemre, valamint azt, hogy milyen bejárást akarunk használni (szélességi, mélységi, inorder, preorder, postorder) , emellett itt implementáljuk az eljárásokat is: a) public bool bennevan(T elem) b) public void beszur(T ujelem) c) public bool torol(T x) d) Cél: a fát be lehessen járni foreach ciklussal 3. A foreach ciklus működéséhez az éppen kiválasztott bejárást hívjuk meg, és a produkált lista felsorolóját ( List.GetEnumerator() ) használjuk fel 4. Tesztprogram írása, amiben a fa számokat tárol V 1.0


34

Fejlesztési sajátosságok • Szélességi bejárás sor, mélységi bejárás verem adatszerkezettel • InOrder/PreOrder/PostOrder bejárás rekurzióval • Az előadáson bemutatott eljárások egyik paramétere az aktuális csúcs (pl. Függvény Beszúrás(címszerint p, újkulcs) ), és az első meghíváskor a p paraméter értéke a gyökér • OOP megközelítésben a publikus eljárásainkban az aktuális csúcs nem szerepel, pl. public void beszur(T ujelem) • A publikus eljárás nem-publikus eljárásra hivatkozik, pl. private priv_beszur(ref FRoot, ujelem) • Fontos kérdés: miért kell a paraméternél ref kulcsszó, amikor már úgyis referencia típus a csucs? OOP tárgy, paraméter-átadási módok V 1.0


35

Ref.típusok cím szerinti paraméterátadása static void tombkez1(ref int[] arr) { arr[1] = 42; } static void tombkez2(ref int[] arr) { arr = new int[3] { 23, 23, 23 }; }

V 1.0

ÓE-NIK, 2011

36

Ref.típusok cím szerinti paraméterátadása static void Main(string[] args) { int[] t = { 3, 4, 5 }; tombkez1(ref t); tombkez2(ref t); } • Híváskor a változó CÍMÉRŐL másolat képződik, és a CÍM kerül át paraméterként a hívott eljárásokba Referenciára mutató referencia • A hívott eljárásokban ezt a változót és a hivatkozott memóriaterületet is lehet módosítani V 1.0

ÓE-NIK, 2011

37

Ref.típusok cím szerinti paraméterátadása Memória cím1 t cím2

cím2 3 4

int[] t= {3, 4, 5};

5

V 1.0

ÓE-NIK, 2011

38

Ref.típusok cím szerinti paraméterátadása Memória cím1 t cím2 cím3 arr cím1

V 1.0

cím2 3 4

int[] t= {3, 4, 5}; tombkez1(t);

5

ÓE-NIK, 2011

39


V 1.0

cím2 3 42 5

ÓE-NIK, 2011

int[] t= {3, 4, 5}; tombkez1(t); arr[1]=42; Teljesen mindegy, hogy hány referencián keresztül van az értékadás, mindig a megfelelő értékre történik a hivatkozás!

40


cím2 3 42 5

int[] t= {3, 4, 5}; tombkez1(t); arr[1]=42; tombkez2(t); arr=new int[3] { 23, 23, 23};

cím4 23 23 23

V 1.0

ÓE-NIK, 2011

41


cím2 3 42 5 cím4 23 23

int[] t= {3, 4, 5}; tombkez1(t); arr[1]=42; tombkez2(t); arr=new int[3] { 23, 23, 23}; A paraméterül adott változót cseréltem le

23 V 1.0

ÓE-NIK, 2011

42

Fejlesztési sajátosságok • Fontos kérdés: miért kell a paraméternél a ref kulcsszó, amikor már úgyis referencia típus a csucs ? • Válasz: hiába referencia típus, a cél az, hogy a hívott eljárásból a fa szerkezetét tudjam módosítani. • Ehhez nem csak a paraméterül adott csúcs adatait kell módosítanom, hanem törlésnél/beszúrásnál közvetlenül a paraméterül adott csúcsot kell cserélni ehhez kell a referencia típus referencia szerinti paraméterátadása • A csúcs osztályban a gyermek-elemekhez ne csináljuk tulajdonságot, maradjanak publikus adattagok – ez nem szép megoldás, de ha a gyermekcsúcsokat referenciaként akarom továbbadni, akkor erre szükség van V 1.0


43

A fejlesztés menete 1. Generikus osztályként megtervezzük a csucs osztályt, amely egy T típusú referenciát tárol, valamint egy referenciát a jobb és a bal oldali gyermek-elemre 2. Generikus osztályként megtervezzük a fa osztályt, amely tárol egy referenciát a gyökérelemre, valamint azt, hogy milyen bejárást akarunk használni (szélességi, mélységi, inorder, preorder, postorder) , emellett itt implementáljuk az eljárásokat is: a) public bool bennevan(T elem) b) public void beszur(T ujelem) c) public bool torol(T x) d) Cél: a fát be lehessen járni foreach ciklussal 3. A foreach ciklus működéséhez az éppen kiválasztott bejárást hívjuk meg, és a produkált lista felsorolóját ( List.GetEnumerator() ) használjuk fel 4. Tesztprogram írása, amiben a fa számokat tárol V 1.0


44

Tesztprogram I.

V 1.0


45

Tesztprogram II.

V 1.0


46

Tesztprogram III.

V 1.0


47




V 1.0


48

Gráfok & Dijkstra algoritmus • Gráf: csomópontok és a csomópontokat összekötő élek halmaza • Jelenleg: irányítatlan, súlyozott gráf • Cél: az 1. csúcsból meghatározni a legrövidebb utat az 5. csúcshoz • Dijkstra algoritmus: meghatározza valamely kezdőcsúcsból az összes többi csúcsba vezető legkisebb súlyú utat • Mohó algoritmus

V 1.0


49

Dijkstra algoritmus • Tegyük fel, hogy a gráf tárolása és a lényeges műveletek már készen vannak • Két tömböt használunk, mindegyik tömb ugyanannyi elemű, mint ahány csúcs van a gráfban • Az int típusú ElozoCsucs tömbben tároljuk a kiinduló csúcsból az egyes csúcsokhoz vezető legrövidebb útnál a csúcsot megelőző csúcs sorszámát • A double típusú OsszSuly tömbben tároljuk a kiinduló csúcsból az egyes csúcsokhoz vezető jelenleg ismert legrövidebb út összsúlyát • Az csúcsokat két halmazra kell osztani: függőben lévő csúcsok és fix útvonalú csúcsok. Mi ezt úgy oldjuk meg, hogy az i. csúcs még függőben van, ha OsszSuly[i]<0 • Jelenlegi kezdőcsúcs: #1 !

V 1.0


50

Inicializálás • Kell: kiinduló csúcs (Honnan), innen számoljuk a legrövidebb utat az összes többi csúcshoz • Minden I csúcs távolsága legyen az I és a Honnan csúcs távolságának negatív értéke: OsszSuly tömb – (a negatív távolság azt jelzi, hogy a csúcs még nincs kész) – (a Honnan-nal nem szomszédos csúcsoknál ez double.NegativeInfinity) • Minden I csúcsra jelezzük, hogy a Honann I útvonalban az I csúcs előtti csúcs a Honnan (közvetlen él): ElozoCsucs tömb – (ez a Honnan csúccsal szomszédos csúcsokra tényleg jó útvonalat definiál, a többi csúcsnál nincs olyan él, szóval ez biztos változni fog) – A Honnan csúcs előtti csúcs legyen -1, ezzel jelezzük, hogy a Honnan a kiinduló-csúcs V 1.0


51

Kiinduló állapot

IDX

ElozoCsucs OsszSuly

1

-1

0

2

1

-10

3

1

-∞ ∞

4

1

-5

5

1

-∞ ∞

V 1.0


52

Algoritmus Ciklus, amíg van negatív súly (vagyis: amíg létezik nem-kész csúcs) 1. Minimum=az abszolút értékben legkisebb negatív súly sorszáma; 2. OsszSuly[minimum] = -OsszSuly[minimum]; 3. Minden nem-kész (vagyis negatív összsúlyú) csúcsra megnézzük, hogy a jelenlegi OsszSuly[i] súlynál abszolút értékben kisebb súlyt kapunk –e, ha nem az ElozoCsucs[i] eddigi előző csúcson, hanem a Minimum-csúcson keresztül közelítjük meg. Ha igen, akkor ezzel frissítjük az OsszSuly[i]-t, és ElozoCsucs[i]=Minimum; Ciklus vége V 1.0


53

1. iteráció

IDX

ElozoCsucs OsszSuly

1

-1

2

1

4 -10

-8

3

1

∞ 4 -∞

-14

4

1

-5

5

1

∞ 4 -∞

V 1.0

0

5

A LEGKISEBB! (Abszolút értékben)

-16 Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

54

2. iteráció

IDX

ElozoCsucs OsszSuly

1

-1

0

2

4

-8

8

3

4

-14

-9

4

1

5

5

4

-16

V 1.0

2



55

3. iteráció

IDX

ElozoCsucs OsszSuly

1

-1

0

2

4

8

3

2

-9

4

1

5

5

4

V 1.0

9


3 -16 -10 Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

56

4. iteráció

IDX

ElozoCsucs OsszSuly

1

-1

0

2

4

8

3

2

9

4

1

5

5

3

-10 10

V 1.0


A LEGKISEBB! (Abszolút értékben) 57

Végállapot

IDX

ElozoCsucs OsszSuly

1

-1

0

2

4

8

3

2

9

4

1

5

5

3

10

V 1.0

Az útvonalak nem Bármelyik csúcs elérhető feltétlenül alkotnak fát a kezdőcsúcsból indulva vagy egyenest, ez egyedi Szabó Zsolt, Óbudai Egyetem, 2011 [email protected]

58

Fejlesztés • Gráf osztály: int FPontok; double[,] FSulyok; string[] FCimkek; – public Graf(int n) – public void UjCimke(int n, string cimke) – public void UjEl(int n, int m, double suly) – public int GetPont(string cimke) – public double GetSuly(int n, int m) • Dijkstra algoritmushoz szükséges eljárások: – private bool MinKer(double[] d, out int min) Visszaadja, hogy talált –e negatív súlyt, és ha talált, akkor ezek közül melyik az abszolút értékben a legkisebb – public List Utvonal(int honnan, int hova) Itt először legeneráljuk az ElozoCsucs + OsszSuly tömböket, aztán iterálunk, majd legeneráljuk a specifikus utat V 1.0


59

Tesztelés (Ctrl+C, Ctrl+V) Graf g; g = new Graf(5); g.UjCimke(0, "#1"); g.UjCimke(1, "#2"); g.UjCimke(2, "#3"); g.UjCimke(3, "#4"); g.UjCimke(4, "#5"); g.UjEl(0, 1, 10); g.UjEl(0, 3, 5); g.UjEl(1, 3, 3); g.UjEl(1, 2, 1); g.UjEl(2, 3, 9); g.UjEl(3, 4, 11); g.UjEl(2, 4, 1); utvonal(g, g.GetPont("#1"), g.GetPont("#5")); V 1.0


60

Tesztelés2 (Ctrl+C, Ctrl+V) g = new Graf(20); g.UjCimke(0, "Baja"); g.UjCimke(1, "Budapest"); g.UjCimke(2, "Debrecen"); g.UjCimke(3, "Eger"); g.UjCimke(4, "Esztergom"); g.UjCimke(5, "Győr"); g.UjCimke(6, "Gyula"); g.UjCimke(7, "Kaposvár"); g.UjCimke(8, "Kecskemét"); g.UjCimke(9, "Miskolc"); g.UjCimke(10, "Nyíregyháza"); g.UjCimke(11, "Pécs"); g.UjCimke(12, "Sopron"); g.UjCimke(13, "Szeged"); g.UjCimke(14, "Székesfehérvár"); g.UjCimke(15, "Szolnok"); g.UjCimke(16, "Szombathely"); g.UjCimke(17, "Tatabánya"); g.UjCimke(18, "Veszprém"); g.UjCimke(19, "Zalaegerszeg");

V 1.0


g.UjEl(0, 1, 192.5); g.UjEl(0, 6, 165.7); g.UjEl(0, 13, 93.1); g.UjEl(1, 2, 205.9); g.UjEl(1, 3, 240.3); g.UjEl(1, 8, 81.2); g.UjEl(1, 11, 197.8); g.UjEl(1, 18, 126.4); g.UjEl(2, 3, 35.6); g.UjEl(2, 6, 93.1); g.UjEl(3, 6, 104.3); g.UjEl(4, 7, 152.4); g.UjEl(4, 16, 133.8); g.UjEl(4, 17, 26.1); g.UjEl(5, 12, 33.4); g.UjEl(5, 16, 110.5); g.UjEl(6, 15, 72.3); g.UjEl(7, 11, 65.8); g.UjEl(7, 14, 99.9); g.UjEl(8, 9, 137.5); g.UjEl(8, 13, 91.8); g.UjEl(8, 15, 52.3); g.UjEl(9, 1, 210.4); g.UjEl(9, 6, 141.0); g.UjEl(9, 10, 62.7); g.UjEl(10, 2, 216.8); g.UjEl(10, 15, 44.6); g.UjEl(11, 0, 76.8); g.UjEl(11, 5, 258.2); g.UjEl(11, 14, 116.4); g.UjEl(11, 19, 145.0); g.UjEl(12, 14, 91.5); g.UjEl(12, 17, 60.7); g.UjEl(13, 1, 158.2); g.UjEl(13, 15, 56.3); g.UjEl(14, 1, 62.1); g.UjEl(14, 5, 97.4); g.UjEl(14, 17, 41.7); g.UjEl(15, 1, 109.8); g.UjEl(15, 3, 68.3); g.UjEl(16, 17, 127.5); g.UjEl(16, 19, 78.2); g.UjEl(17, 18, 69.1); g.UjEl(18, 11, 137.6); g.UjEl(18, 14, 46.3); g.UjEl(19, 1, 278.5); g.UjEl(19, 4, 207.2); g.UjEl(19, 6, 377.9); g.UjEl(19, 12, 92.7); 61 utvonal(g, g.GetPont("Szombathely"), g.GetPont("Szeged"));

Tesztelés

V 1.0


62




V 1.0


63

Kruskal algoritmus • Fa: körmentes (aciklikus), összefüggő gráf • Feszítőfa: a gráf összes csúcsát tartalmazó fa, amelynek élei a gráf éleinek részhalmazát alkotják, n csúcs esetén n-1 élből áll • Minimális feszítőfa: a feszítőfák közül a legkisebb összsúlyú

V 1.0


64

"Nem alakul ki kör" ? • Útvonalkereséssel (lassabb, talán könnyebben érthető) : Egy listába berakjuk az X csúcsból a feszítőfa meglévő élein keresztül elérhető összes csúcsot (tetszőleges bejárással: szélességi/mélységi). Ha a listában benne van az Y, akkor az X csúcsból a feszítőfa élein keresztül már elérhető az Y, vagyis X és Y egy komponensben van nem adható hozzá a feszítőfához az XY él, mert az kört hozna létre • Komponensek használatával (ezt fogjuk implementálni) : Minden csúcshoz komponens-azonosítót rendelünk. Az él nem hoz létre kört, ha külön komponensben lévő csúcsokat köt össze: X és Y csúcs összeköthető éllel, ha a komponens-azonosítójuk különböző. Ezután minden csúcshoz azonos komponens-azonosítót kell rendelni, ami az X vagy az Y csúcs komponensében volt. V 1.0


65

Kruskal algoritmus – példa

V 1.0


66


V 1.0


67


V 1.0


68


V 1.0


69


V 1.0


70


V 1.0


71


V 1.0


72


V 1.0


73

Kruskal algoritmus – megoldási elv 1. Definiáljuk a komponensek tömböt, ahol komponensek[i] az i. csúcs komponens-azonosítóját jelzi. Kezdetben minden tömbelem egyedi [0..X] nincs él a feszítőfában 2. double FSulyok[,] List Elek (GrafEl = {kezdőpont, végpont, súly}) 3. GrafEl rendezése súly szerint növekvő sorrendbe 4. Ciklus, amíg nincs kész a feszítőfa és nem fogynak el az élek a) Akt = sorrendben a következő él, ahol a kezdőpont és a végpont különböző komponensben van b) Ha van ilyen él, akkor az él hozzáadása a feszítőfához c) Ha van ilyen él, akkor az él kezdőpontjának és végpontjának a komponenseit egyesíteni kell 5. public List Kruskal() V 1.0


74

Tesztelés (Ctrl+C, Ctrl+V) g = new Graf(8); g.UjCimke(0, "#1"); g.UjCimke(1, "#2"); g.UjCimke(2, "#3"); g.UjCimke(3, "#4"); g.UjCimke(4, "#5"); g.UjCimke(5, "#6"); g.UjCimke(6, "#7"); g.UjCimke(7, "#8"); g.UjEl(g.GetPont("#1"), g.GetPont("#2"), 1); g.UjEl(g.GetPont("#1"), g.GetPont("#6"), 3); g.UjEl(g.GetPont("#2"), g.GetPont("#6"), 4); g.UjEl(g.GetPont("#2"), g.GetPont("#3"), 2); g.UjEl(g.GetPont("#2"), g.GetPont("#7"), 5); g.UjEl(g.GetPont("#6"), g.GetPont("#7"), 8); g.UjEl(g.GetPont("#3"), g.GetPont("#7"), 6); g.UjEl(g.GetPont("#3"), g.GetPont("#4"), 4); g.UjEl(g.GetPont("#4"), g.GetPont("#7"), 7); g.UjEl(g.GetPont("#7"), g.GetPont("#8"), 1); g.UjEl(g.GetPont("#4"), g.GetPont("#8"), 6); g.UjEl(g.GetPont("#4"), g.GetPont("#5"), 7); g.UjEl(g.GetPont("#5"), g.GetPont("#8"), 8); kruskal(g);

V 1.0


75

Tesztelés

V 1.0


76

Programozási Paradigmák és Technikák Láncolt Lista

Generikus osztályok Láncolt Lista megvalósítása

Bináris keresőfa (BST)

BST megvalósítása

Gráfok

V 1.0

Dijkstra algoritmus Kruskal algoritmus


77

Képek forrásai •

• • • • • • •

V 1.0

http://people.ksp.sk/~kuko/bak/ (megjegyzés: a fenti oldal nagyon jó, de kicsit más a BST, mint az előadáson ismertetett: törlés-C esetnél (amikor mindkét gyermekeleme létezik a törlendő elemnek) nem a bal oldali részfa legjobboldalibb elemét, hanem a jobb oldali részfa legbaloldalibb elemét használja) http://en.wikipedia.org/wiki/Linked_List http://en.wikipedia.org/wiki/Dijkstra's_algorithm http://en.wikipedia.org/wiki/Kruskal's_algorithm http://people.inf.elte.hu/fekete/docs_2/grafalg/grafalg.htm http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml http://students.ceid.upatras.gr/~papagel/project/pseukrus.htm http://www.cs.usask.ca/classes/371/projects/99group8/tutorial/advanced/prim/prim_kruskal.ht ml


80

Programozási Paradigmák. és Technikák

Recommend Documents