5. A gráf, mint adatstruktúra Gráfelméleti bevezető

5. A gráf, mint adatstruktúra 5.1. Gráfelméleti bevezető Definíció:

Az irányított gráf (digráf) A G = (V , E ) rendezett párt irányított gráfnak (digráfnak) nevezzük. A rendezett pár elemeire tett kikötések: V véges halmaz, a G-beli csúcsok halmaza. E bináris reláció a V halmazon, az élek halmaza E = {(u, v ) rendezett pár u ∈V , v ∈V } ⊂ V × V . Hurkok megengedettek. Hurok az (a, a ) él.

Definíció:

Az irányítatlan gráf A G = (V , E ) rendezett párt irányítatlan gráfnak nevezzük. A rendezett pár elemeire tett kikötések: V véges halmaz, a G-beli csúcsok halmaza. E bináris reláció a V halmazon, az élek halmaza E = {(u, v ) rendezettlen pár u ∈V , v ∈V } ⊂ V × V . Hurok nem megengedett.

Definíció:

Az u csúcsból kiinduló és a v csúcsba mutató él digráfban Az (u, v ) él.

Definíció:

Az u csúcsból kiinduló és a v csúcsba mutató él irányítatlan gráfban Az (u, v ) él.

Definíció:

Az u csúcs szomszédja Legyen (u, v ) él egy G = (V , E ) gráfban. Ekkor a v csúcsot az u csúcs szomszédjának nevezzük

A szomszédság reláció irányítatlan gráfban szimmetrikus, digráfban nem. Definíció:

Csúcs fokszáma irányítatlan gráfban A csúcs fokszáma a belőle kiinduló élek száma.

Definíció:

Csúcs fokszáma digráfban Kimenő fokszám (kifok): a csúcsból kimenő élek száma Bemenő fokszám (befok): a csúcsba bemenő élek száma Csúcs fokszáma: kifok+befok

Definíció:

Ionizált csúcs Csúcs, melynek fokszáma zérus.

Definíció:

Az u csúcsot az u’ csúccsal összekötő k hosszúságú út Csúcsok véges sorozata: v0 , v1 ,K, vk , ahol u = v0 , u ' = vk és (vi −1 , vi ) ∈ E , i = 1, K , k .

Definíció:

Egyszerű út Út, melyben a benne szereplő csúcsok páronként különbözőek.

Adatstruktúrák, algoritmusok ahol u = v0 , u ' = vk és (vi −1 , vi ) ∈ E , i = 1, K , k . Definíció:

Út része Legyen v0 , v1 ,K, vk út. Az út része vi , vi +1 ,K, v j , ahol 0 ≤ i ≤ j ≤ k .

Definíció:

Az u’ csúcs elérhető az u csúcsból u ' ), ha Azt mondjuk, hogy az u’ csúcs elérhető az u csúcsból (jelölésben u ⎯⎯→ P van olyan út, amely az u csúcsot az u’ csúccsal összeköti.

Definíció:

Kör digráfban Út, melyre v0 = vk és az út tartalmaz legalább egy élt.

Definíció:

Egyszerű kör Kör, melynek csúcsai mind különbözőek.

Definíció:

Hurok 1 hosszúságú kör.

Definíció:

Egyszerű gráf Hurok nélküli digráf

Definíció:

Kör gráfban Egyszerű kör és k ≥ 3 , v0 = vk .

Definíció:

Körmentes gráf Gráf, amely nem tartalmaz kört..

Definíció:

Összefüggő gráf Ha bármely két csúcsa összeköthető úttal.

Definíció:

Összefüggő komponens Csúcsok alkotta ekvivalencia-osztály, ahol az ekvivalencia reláció a csúcsok közötti elérhetőség.

Definíció:

Digráf erősen összefüggő Tetszőleges két csúcs esetén mindegyik elérhető a másikból.

Definíció:

Izomorf gráfok A G = (V , E ) és a G ' = (V ' , E ') gráfok izomorfak, ha létezik olyan f : V → V ' bijekció, hogy (u, v ) ∈ E ⇔ ( f (u ), f (v )) ∈ E ' .

Definíció:

A G = (V , E ) gráf részgráfja

G ' = (V ' , E ') gráf, melyre V ' ⊂ V és E ' ⊂ E . Definíció:

A G gráf V’ által meghatározott részgráfja G ' = (V ' , E ') , ahol E ' = {(u, v ) ∈ E , u, v ∈V '}.

-2-

Adatstruktúrák, algoritmusok Definíció:

A G = (V , E ) gráfhoz tartozó digráf Az a G ' = (V ' , E ') digráf, melyre (u, v ) ∈ E ' ⇔ (u, v ) ∈ E , azaz az éleket két irányított éllel helyettesítjük).

Definíció:

A G = (V , E ) digráfhoz tartozó irányítatlan gráf Az a G ' = (V ' , E ') gráf, melyre (u, v ) ∈ E ' ⇔ u ≠ v, (u, v ) ∈ E azaz elhagyjuk a hurkokat és az irányítást.

Definíció:

Teljes gráf Irányítatlan gráf, melyben bármely két csúcs szomszédos. (Minden lehetséges él benne van.)

Definíció:

Páros gráf Irányítatlan gráf, melynél V felbontható V1, V2 diszjunkt unióra úgy, hogy (u, v )∈ E esetén vagy u ∈V1 és v ∈ V2 , vagy pedig u ∈ V2 és v ∈ V1 . (Azaz V1ben és V2-ben nincs belső él.)

Definíció:

Erdő Körmentes, irányítatlan gráf.

Definíció:

(Nyílt) fagráf Összefüggő, körmentes, irányítatlan gráf.

Tétel:

A nyílt fák tulajdonságai Legyen G = (V , E ) irányítatlan gráf. Az alábbiak ekvivalensek. 1. G nyílt fa 2. G bármely két csúcsához egyértelműen létezik egy őket összekötő egyszerű út. 3. G összefüggő, de tetszőleges élének elhagyása után a visszamaradó gráf már nem összefüggő 4. G összefüggő és E = V − 1 ⎜ 5. G körmentes és E = V − 1 6. G körmentes, de akár egyetlen éllel is bővítve E-t a kapott gráf már tartalmaz kört.

Bizonyítás 1.⇒2. bizonyítása G fa ⇒ G összefüggő. ⇒ G bármely csúcspárja között van út. Be kell látni, hogy csak egy van. Ha több lenne, akkor kettőből már kör alakítható ki, ami ellentmondás. 2.⇒3. bizonyítása G bármely két csúcsa egyértelműen köthető össze úttal. ⇒ G összefüggő. ⇒ ⇒ Tetszőleges (u,v) élt választva az él az u és v csúcsokat köti össze egyelemű útként. Ő az egyetlen út u és v között. Ha elhagyom, akkor nem lesz ott út, tehát a gráf nem lesz összefüggő. 3.⇒4. bizonyítása

-3-

Adatstruktúrák, algoritmusok

-4-

G (3) miatt összefüggő, tehát ezt nem kell bizonyítani. Másrészt ebből adódóan automatikusan ⎜E ⎜ ≥ ⎜V ⎜ - 1. Teljes indukcióval látjuk be, hogy ⎜E ⎜ ≤ ⎜V ⎜ - 1. Legyen n= ⎜V ⎜. Ha n=1 vagy 2, akkor ez igaz, mert a gráfnak n-1 éle van. Legyen most n ≥3 és minden kevesebb csúcsú gráfra teljesüljön (3). Hagyjuk el tetszőleges élét. Ezáltal k darab összefüggő komponens keletkezik, ahol k≥2. Minden komponens (3) tulajdonságú. Az élek száma legfeljebb n-k≤n-2. Az elvett élt is hozzávéve az élek száma legfeljebb n-1. 4.⇒5. bizonyítása Indirekt módon bizonyítunk. Tegyük fel, hogy van kör. Erre a körre, mint részgráfra igaz, hogy éleinek és csúcsainak száma megegyezik. Legyen ez k. Ha k< ⎜V ⎜, akkor van még csúcs a körön kívül, mely szomszédos a kör valamely csúcsával G összefüggősége miatt. Vegyük hozzá a körhöz ezt a csúcsot és az élt. Az így kapott részgráfban is a csúcsok száma és az élek száma azonos (k+1). Újabb és újabb csúcsok és élek hozzávételével az összes csúcspontot felhasználjuk. Ekkor G-re azt kapjuk, hogy ⎜E ⎜ ≥ ⎜V ⎜, ami ellentmondás 5.⇒6. bizonyítása Legyen G összefüggő komponenseinek száma k. Minden komponens fa és (1) ⇒ (5). Ezért G komponenseiben ⎜V ⎜ - k él van. ⎜E ⎜ = ⎜V ⎜ - 1 miatt k=1 és így G fa. Ekkor viszont bármely két G-beli csúcs összeköthető egyszerű úttal. Hozzávéve egy új élt a két csúcs között, az az úttal együtt kört alkot 6.⇒1. bizonyítása Azt kell belátni, hogy G összefüggő. Legyen u,v két tetszőleges csúcs. Ha szomszédosak, akkor van közöttük út. Ha nem szomszédosak, akkor vegyük fel az u,v élt. Ekkor kör keletkezik (6) miatt, A kör élei az (u,v) él kivételével G-hez tartoznak.és így utat alkotnak u és v között. Tehát G összefüggő, tehát fa. ■

5.2. Gyökeres fák Definíció:

Gyökeres fa T fagráf, amely egyik csúcsának kitüntetett a szerepe a többihez képest. Ez a csúcs a gyökér vagy gyökércsúcs (r).

Definíció:

Az x csúcs megelőzője A gyökérből x-be vezető úton fekvő bármely csúcs. (x is a saját megelőzője.)

Definíció:

y valódi megelőzője x-nek ha megelőzője x-nek, de y ≠ x.

Definíció:

x az y rákövetkezője ha y x-nek megelőzője. (x is a saját rákövetkezője.)

Adatstruktúrák, algoritmusok Definíció:

x valódi rákövetkezője y-nak ha megelőzője y-nak, de y ≠ x.

Definíció:

x-ben gyökerező részfa Az x és a rákövetkezőiből álló részgráf (fa).

Definíció:

x szülője y x úton (y,x) az utolsó él. (A gyökérnek nincs szülője T-ben.) ha az r ⎯⎯→ P

Definíció:

x az y gyereke ha y az x szülője.

Definíció:

Testvérek azok a csúcsok, amelyeknek ugyanaz a csúcs a szülője.

Definíció:

Külső csúcs vagy levél az a csúcs, amelynek nincs gyereke.

Definíció:

Belső csúcs az a csúcs, amely nem levél.

Definíció:

x fokszáma gyökeres fában az x gyerekeinek száma. (A szülő nem számít bele a fokszámba!)

Definíció:

x szintje x út hossza. az r ⎯⎯→ P

Definíció:

T magassága a T-beli csúcsok szintjei közül a legnagyobb.

Definíció:

Rendezett gyökeres fa minden csúcs gyerekei rendezettek. (Azaz van első, második,…, k-adik)

Definíció:

Bináris fa Rendezett fa, melyben minden csúcs fokszáma legfeljebb kettő. (Beszélhetünk bal gyerekről és jobb gyerekről.)

Definíció:

Null fa Üres bináris fa.

Definíció:

Teljes bináris fa Bináris fa, melyben a csúcsok fokszáma kettő, kivéve a leveleket, melyeké 0, valamint az összes levél azonos szinten helyezkedik el.

Definíció:

Súlyozott fa A csúcsok gyerekeit különböző pozitív, egész számmal indexeljük. (1,2,3,…)

Definíció:

csúcs i-dik gyereke hiányzó nincs i indexű gyereke.

Definíció:

k-adrendű fa Súlyozott fa, ahol minden csúcsnál a k-nál nagyobb indexű gyerekek hiányoznak.

-5-


-6-

(A bináris fa másodrendű.) Definíció:

k-adrendű teljes fa k-adrendű fa, melyben a levelek ugyanazon szintűek és az összes belső csúcs fokszáma k.

A h magasságú teljes k-adrendű fának kh számú levele van. Ha a levelek száma n, akkor a teljes k-adrendű fa magassága logk n. A h magasságú teljes k-adrendű fa belső csúcsainak h h −1 k −1 1 + k + k 2 + K + k h−1 = ∑ k i = . k −1 i =0 Teljes bináris fa belső csúcsainak száma: 2 h − 1

a

száma:

A gyökeres fa adatstruktúra. A fa minden csúcsa egy objektum. Az objektumok tartalmaznak kulcs mezőt és mutatókat. A T fa attribútuma: gyökér[T] egy mutató, mely a fa gyökerére mutat. Ha gyökér[T]=NIL, akkor a fa üres. Bináris fa esetén az x csúcs ábrázolható az alábbi sémával: Szülőmutató

Kulcs

Bal gyerek mutató Jobb gyerek mutató Csúcsattribútumok: szülő[x], kulcs[x], bal[x], jobb[x] Ha szülő[x]=NIL, akkor x gyökér. Ha bal[x]=NIL, vagy jobb[x]=NIL, akkor amelyik NIL, az a gyerek nincs. Ha mindkettő NIL, akkor x levél. A bináris fa mintájára k-adrendű fa esetén használható, bár memória pazarló az x csúcs ábrázolására az alábbi séma: Szülő mutató 1. gyerek mutató 2. gyerek mutató

Kulcs … k. gyerek mutató

Helyette javasolható az úgynevezett bal gyerek – jobb testvér séma, melynek memóriaigénye: Ο(n ) .

Szülőmutató

Kulcs

Bal gyerek mutató Jobb testvér mutató


-7-

NIL NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

5.2.1. Bináris kupac, kupacrendezés Definíció:

A bináris kupac (heap) A bináris kupac (heap) egy bináris gyökeres fa, amely minden szintjén kitöltött, kivéve esetleg az utolsó szintet, ahol balról jobbra haladva vannak a levelek kihagyás nélkül (a szint balra tömörített) továbbá teljesül a kupac tulajdonság, mely szerint a gyökércsúcsot kivéve minden x mutatójú csúcsra fenn kell álljon, hogy Kulcs(Szülő(x)) ≥ Kulcs(x), ha maximumkupacról beszélünk, illetve Kulcs(Szülő(x)) ≤ Kulcs(x) minimumkupac esetén,

A következőkben a maximumkupacról fogunk beszélni. Kupac attribútumok (feltételezve, hogy a kupac reprezentálása egy egyindexes A tömbbel történik, amelyben a kupacot tároljuk és amelynek indexelése 1-gyel kezdődik) a következők: a tömb fizikai maximális mérete (elemszám a tömbben). hossz[A] kupac_méret[A a kupacelemek (csúcsok) száma gyökér[T] ) A1 Az i indexű elem esetén az attribútumok: Szülő(i), Bal(i), Jobb(i) Kupac magasság = a fa magassága = h = Θ(log n ) Példa kupacra és tömbös realizációjára:


-816

14

10

8

2

4

1

14

10

8

7

9

3

2

4

1

1

2

3

4

5

6

7

8

9

10

1 SZÜLŐ( i, x ) 2 // Input paraméter: i a vizsgált index 3 // Output paraméter: x – a szülő indexe 4 5 ⎢i ⎥ x←⎢ ⎥ ⎣2⎦ 6 RETURN( x⎦ )

//

6 7 8 9 10 11

3

16

5.2.1.1. algoritmus Szülő // T (n ) = Θ(1) //

1 2 3 4 5

9

7

5.2.1.2. algoritmus Bal gyerek T (n ) = Θ(1) //

5.2.1.3. algoritmus Jobb gyerek T (n ) = Θ(1)

BAL( i, x ) // Input paraméter: i a vizsgált index // Output paraméter: x – a bal gyerek indexe

JOBB( i, x ) // Input paraméter: i a vizsgált index // Output paraméter: x – a jobb gyerek indexe

x ← 2i

x ← 2i + 1

RETURN( x⎦ )

RETURN( x⎦ )

5.2.1.4. algoritmus Kupacol ( Eljárás a kupac tulajdonság fenntartására ) T (n ) = Θ(log n )

KUPACOL ( A, i ) // Input paraméter: A - a kupacot tároló tömb // i - a vizsgálandó elem indexe // Output paraméter: A - a kupacot tároló tömb // Akkor használjuk, ha az i baloldali és jobboldali részfái ugyan kupacok, de i-ben sérülhet a kupac tulajdonság BAL( i, b ) JOBB( i, j ) IF b ≤ Kupac_méret[A] és Ab>Ai THEN legnagyobb ← b ELSE legnagyobb ← i IF j ≤ Kupac_méret[A] és Aj>Alegnagyobb


-9-

12 THEN legnagyobb ← j 13 IF legnagyobb ≠i 14 THEN csere Ai ↔ Alegnagyobb 15 KUPACOL( A, legnagyobb ) 16 RETURN (A) 5.2.1.5. algoritmus Kupacot épít (Eljárás, mely tetszőleges adatokból kupacot épít ) // T (n ) = Θ(n )

1 2 4 5 6

KUPACOT_ÉPÍT( A ) // Input paraméter: A - a kiinduló kulcsok tömbje // Output paraméter: A – az elkészült kupac tömbje

Kupac_méret[A] ←hossz[A] ⎢ hossz[ A]⎥ 7 FOR i ← ⎢ ⎥⎦ DOWNTO 1 DO 2 ⎣ 8 KUPACOL( A, i ) 9 RETURN ( A )

// 1 2 3 4 5 6 7 8 9 10

5.2.1.6. algoritmus Kupacrendezés (Eljárás, mely helyben rendez ) T (n ) = Θ(n log n )

KUPACRENDEZÉS( A ) // Input paraméter: A - a rendezendő kupac tömbje // Output paraméter: A – a rendezett kulcsok tömbje KUPACOT_ÉPÍT( A ) FOR i ← hossz[A] DOWNTO 2 DO csere A1 ↔Ai DEC ( Kupac_méret[A] ) KUPACOL( A, 1 ) RETURN ( A ) 5.2.1.7. algoritmus Kupacba beszúrás

// 1 2 3 4 5 6 7 8

T (n ) = Θ(log n )

KUPACBA_BESZÚR( A, kulcs ) // Input paraméter: A - a kupac tömbje // kulcs – a beszárandó kulcs // Output paraméter: A – a kupac a beszúrt kulccsal INC( Kupac_méret[ A ] ) i ← Kupac_méret [A] ) SZÜLŐ( i, x )


- 10 -

9 WHILE i>1 és Ax
// 1 2 3 4 5 6 7 8 9 10 11

5.2.1.8. algoritmus Kupacban maximális kulcs lekérdezése T (n ) = Θ(1)

KUPACBAN_MAX( A, max, hiba ) // Input paraméter: A - a kupac tömbje // Output paraméter: max – a maximális kulcs // hiba – jelzi a művelet sikerességét IF Kupac_méret[A]<1 THEN hiba ← „kupac alulcsordulás” RETURN ( hiba ) max ← A1 hiba ← „sikeres művelet” RETURN ( max, hiba )

5.2.1.9. algoritmus Kupacból a maximális kulcs lekérdezése eltávolítással // T (n ) = Θ(log n )

1 2 3 4 5 6 7 8 9 10 11 12 13 14

KUPACBÓL_KIVESZ_MAX ( A, max, hiba ) // Input paraméter: A - a kupac tömbje // Output paraméter: max – a maximális kulcs // hiba – jelzi a művelet sikerességét Kupac_méret[A]<1 THEN hiba ← „kupac alulcsordulás” RETURN ( hiba ) max ← A1 A1 ←AKupac_méret[A] DEC( Kupac_méret[A] ) KUPACOL( A, 1 ) hiba ← „sikeres művelet” RETURN ( max, hiba ) IF

5.2.2. Az elsőbbségi sor Definíció:

Az elsőbbségi sor (priority queue) Az elsőbbségi sor (priority queue) olyan S halmaz, amelynek minden eleméhez egy kulcs értéket rendelünk. A kulcs egy elsőbbségi értéket, prioritási értéket szimbolizál. Szolgáltatást igénybevevők sorbanállási sorában a sorrakerülő elem az lesz, amelynek a prioritása a legnagyobb (maximum prioritásos sor), vagy amelyiké a legkisebb (minimum prioritásos sor).

Adatstruktúrák, algoritmusok BESZÚR(S,x): egy elemet hozzáadunk S-hez. S ←S ∪ {x} S legnagyobb kulcsú elemének meghatározása MAXIMUM(S): KIVESZ_MAX(S): megadja és törli a maximális kulcsú elemet.

Az elsőbbségi sor célszerű realizációja a kupac. 5.2.3. A Huffman kód, a mohó algoritmus A Huffman kód egy adattömörítési célokat szolgáló eljárás. A probléma megfogalmazása: Legyen adott egy adatfile, amelyben ismert az egyes adatelemek (pl.: byte-ok) gyakorisága. A feladat olyan kódot találni az adatelemekre, amely révén a kódolt file hossza rövidebb lesz (a lehető legrövidebb), mint az eredeti hossz volt. Definíció:

Kódszó Kódszónak nevezzük az üzenet ábécé betűjéhez hozzárendelt jelek nemüres sorozatát, amelyben a kódábécé betűi szerepelhetnek.

Definíció:

Kód Kódnak nevezzük az üzenet ábécé betűit és a hozzájuk rendelt kódszavak táblázatát. (Kódtábla, kódszótár).

Definíció:

Kódolás Kódolásnak nevezzük az üzenet betűinek a helyettesítését a betűnek megfeleltetett kódszóval. A kódolás eredménye a kódolt üzenet.

Az egyszerűség kedvéért a kódoláshoz használjunk két jelet, a 0 és az 1 jeleket. Az adatelemek kódja lehet fix hosszúságú vagy lehet változó hosszúságú. A kódot egy kódfával ábrázolhatjuk, amely egy bináris fa, amelynek levelei a kódszavak. A kódszó a levélhez vezető útból olvasható ki a gyökértől indulva balra lépéskor 0, jobbra lépéskor 1 hozzáírásával a kódszóhoz. Definíció:

Dekódolás Dekódolásnak nevezzük a kódolt üzenet kódszavakra bontását.

A kódnak dekódolhatónak kell lennie, ha azt akarjuk, hogy a dekódoláskor az eredeti üzenetet kapjuk vissza. Definíció:

Dekódolható kód Dekódolhatónak nevezzük a kódot, ha minden kódolt üzenet csak egyféleképpen bontható kódszavakra.

Definíció:

Prefix kód Prefix kódnak nevezzük a kódot, ha egyik kódszó sem eleje semelyik másik kódszónak. (Semelyik kódszót sem lehet valamely másikból kódjelek hozzáírásával megkapni.)

A prefix kód dekódolható kód. Definíció:

Dekódolható kódok ekvivalenciája Két dekódolható kódot ekvivalensnek nevezünk, ha a megfelelő kódszavaik

- 11 -


- 12 -

hossza megegyezik. Bizonyítható, hogy minden dekódolható kódhoz létezik vele ekvivalens prefix kód. Példa: Betű Gyakoriság Fix hossz Változó hossz f(c) c KódszóHosszKódszó Hossz A

45

000

3

0

1

B

13

001

3

101

3

C

12

010

3

100

3

D

16

011

3

111

3

E

9

100

3

1101

4

F

5

101

3

1100

4

Megadjuk a két kód kódfáját. A téglalapok a fa levelei, a kódolandó ábécé betűi a gyakoriságokkal. A belső csúcsok körök, bennük a csúcs gyerekeinek gyakoriságösszege szerepel.

10 0

0

1

0

86

14

0

0

A:45

1

B:13

C:12

55

A:45 0

14

28 0

1

0

1

58

10 0

1

D:16

0

E:9

1

25

30

1 0

F:5

C:12

1

0

D:16

14

B:13 0

F:5

Definíció:

1

1

E:9

A fa költsége A fa költségének nevezzük a: B(T ) = ∑ f (c ) ⋅ d (c ) számot, ahol c a C ábécé c∈C

betűje, f(c) a betű gyakorisága és d(c) a betű mélysége a fában (kódszóhossz). A fa költségét leosztva a file-t alkotó betűk számával az egy betűre jutó átlagköltséget kapjuk, ami úgy is értelmezhető, mint az átlagos kódszóhossz. Ha ez kisebb, mint egy, akkor tömörítésről beszélünk. Definíció:

Optimális kód Optimális a kód, ha a fa költsége minimális.


- 13 -

Az optimális kód bináris fája mindig teljes. A Huffman-kód optimális kód. A Huffman-kód szerkesztése: Jelölje a kódolandó ábécé betűinek halmazát C és legyen a betűk száma n. A Huffman kód szerkesztési algoritmusának pszeudokódja kiindul egy prioritási sorból, amelyben a betűk a gyakoriságaik szerint vannak kulcsolva. Ezután n-1 lépésben mindig a két éppen akkor legkisebb gyakoriságú elemet összevonva felépít egy optimális kódfát. Az optimum nem egyértelmű, mert az optimális fában bármely csúcs bal és jobb gyerekét felcserélve újra optimális fát kapunk. Egy algoritmustervezési startégia a mohó algoritmus tervezése. Ezt a heurisztikát általában optimalizálásra használják. A mohó stratégia elve szerint az adott pillanatban mindig az ott legjobbnak tűnő lehetőséget választjuk a részprobléma megoldására, azaz a pillanatnyi lokális optimumot választjuk. Ez a választás függhet az előző választásoktól, de nem függ a későbbiektől. A mohó stratégia nem mindig vezet globális optimumra. A Huffman kód szerkesztési algoritmusa mohó algoritmus, mivel minden lépésben úgy von össze, hogy a költség a legkisebb mértékben növekedjen. A teljes fa költsége megegyezik az összevonási lépések költségének összegével. 5.2.3.1. algoritmus Huffman kód készítése

// 1 2 3 4 5 6

T (n ) = Θ(n log n )

HUFFMAN( C, T ) // Input paraméter: C - a kódolandó abécé a gyakoriságokkal // Output paraméter: T – a kódfa // // Jelölje ⎢C⎥ az ábécé betűinek a számát // Létrehozunk egy Q minimum prioritási sort az ábécé betűiből a gyakoriságot használva prioritásnak. A sor elemei fák lesznek, kezdetben minden fát egyetlen betű alkot. 7 Q←C 8 FOR i ← 1 TO C − 1 DO 9 PONTOT_LÉTESÍT(z) //Egy új z csomópontot hoz létre, melyet később a Q sorba be fogunk szúrni. Egy új fa gyökere lesz. 10 x ← Bal[z] ← KIVESZ_MIN(Q) //Kivesszük a Q sorból legkisebb elemet és az új z csomópont bal gyerekének nyílvánítjuk valamint elnevezzük x-nek átmenetileg 11 y ← Jobb[z] ← KIVESZ_MIN(Q) //Kivesszük a Q sorból a következő legkisebb elemet és az új z csomópont jobb gyerekének nyílvánítjuk valamint elnevezzük y-nak átmenetileg 12 f[z] ← f[x]+f[y] // Az új csomópontra meghatározzuk a gyakoriság értéket (prioritás) 13 BESZÚR(Q,z) // Az új z csomópontot beszúrjuk a Q sorba 14 KIVESZ_MIN( Q, T ) // A Q sor egyetlen elemét, mint eredményt Kivesszük a sorból


- 14 -

15 RETURN( T ) Példa: F:5

E:9

C:12

C:12

B:13

14

B:13

F:5

14

F:5

D:16

C:12

B:13

A:45

30

B:13

14

F:5

A:45

D:16

E:9

55

25

C:12

A:45

A:45

25

C:12

A:45

E:9

25

D:16

E:9

D:16

30

B:13

14

F:5

D:16

E:9


- 15 -

10 0 55

A:45

25

C:12

30

D:16

14

B:13

F:5

E:9

5.2.4. Diszjunkt halmazok adatstruktúra Definíció:

Diszjunkt halmazok adatstruktúra A diszjunkt halmazok adatszerkezet dinamikus halmazok S=(S1,S2,…,Sk) együttese. A halmazok elemei objektumok. Mindegyik halmazt egy képviselője azonosít, mely eleme a halmaznak. Általában lényegtelen, hogy melyik ez az elem.

Műveletei: HALMAZT_KÉSZÍT(x): Egy új halmazt hoz létre, melynek ez az egy x eleme lesz, amely egyúttal képviselője is. Az x-et tartalmazó Sx és az y-t tartalmazó Sy halmazokat egyesíti EGYESÍT(x,y): a két halmaz uniójává. Az eredmény az eredeti két halmaz helyére lép, azok megsemmisülnek. A közös képviselő az unió tetszőleges eleme lehet. HALMAZT_KERES(x): Visszaad egy mutatót, amely x halmazának a képviselőjére mutat.

Egy alkalmazás diszjunkt halmazokra: megkeressük egy gráf összefüggő komponenseit

// 1 2 3 4 5 6 7

5.2.4.1. algoritmus Gráf összefüggő komponenseinek megkeresése T (n ) = Θ(V + E )

ÖSSZEFÜGGŐ_KOMPONENSEK( G ) // Input paraméter: G - a gráf // Output paraméter: G – a gráf a komponens információkkal // FOR ∀ v ∈V[G] csúcsra DO HALMAZT_KÉSZÍT( v ) FOR ∀ (u,v) ∈E[G] élre DO


- 16 -

8 IF HALMAZT_KERES( u ) ≠ HALMAZT_KERES( v ) 9 THEN EGYESÍT( u, v ) 10 RETURN( G ) Két kézenfekvő módszer kínálkozik a diszjunkt halmazok adatstruktúra realizálására: 1. a listás realizáció és a 2. gyökeres fákból álló erdős realizáció. A listás realizáció esetén mindegyik halmaz egy önálló lista. A lista első elemét kinevezzük képviselőnek. Mindegyik listaelemnek van egy mutatója, amely a lista következő elemére mutat és van egy, amely a képviselőre. A képviselő is visszamutat saját magára. Az EGYESÍT eljárás ilyenkor a két lista összekapcsolását jelenti, ahol a második listában minden elemnek a képviselő mutatót le kell cserélni az első lista képviselőjére mutató mutatóra. Példa: Két halmaz, az egyik az {a,b,c,d} elemekből áll, képviselőjük az a elem. A másik az {e,f,g} elemekből áll, képviselőjük az e elem.

fej

a

b

c

d

fej

e

f

g

Az összekapcsolás eredménye: EGYESÍT( a, e )

fej

a

b

c

d

e

f

g

Ugyanezen halmazoknak a gyökeres fás erdős realizációja lehet az alábbi. Az ábrán az egyesítés műveletének az eredménye is látható. gyökér

a

b

gyökér

e

gyökér

e

d

a

f c

b g c

f

d

g


- 17 -

Diszjunkt halmaz erdőkre a pszeudokód az alábbi lehet. Megadjuk az összekapcsolás algoritmusát is, amely egy rang fogalmat használ. Minden elemhez hozzárendelünk egy nemnegatív rang számértéket. Ez kezdetben zérus, majd növekedhet. Az összekapcsolásnál a nagyobb rangú képviselő lesz az új képviselő, egyenlőség esetén a másodiknak megadott, melynek a rangját eggyel megnöveljük. Szülő[ x ] az x által mutatott elemnek a szülőjére mutató mutató, Rang[ x ] pedig az elem rang mezeje. 5.2.4.2. algoritmus Elemből halmaz készítése

// 1 2 3 4 5 6 7

T (n ) = Θ(1)

HALMAZT_KÉSZÍT ( x ) // Input paraméter: x – mutató az elemre // Output: az x mutatójú elem kiegészítve halmazinformációkkal // Szülő[ x ] ←x Rang[ x ] ←0 RETURN

//

5.2.4.3. algoritmus Két diszjunkt halmaz uniója (összekapcsolása) T (n ) = Θ(1)

1 ÖSSZEKAPCSOL( x, y ) 2 // Input paraméter: x – mutató az első halmaz képviselőjére // y - mutató a második halmaz képviselőjére 3 // Output: az összekapcsolt halmaz 4 // 5 IF Rang[ x ] > Rang[ y ] 6 THEN Szülő[ x ] ← x 7 ELSE Szülő[ x ] ← y 8 IF Rang[ x ] = Rang[ y ] 9 THEN INC (Rang[ y ]) 10 RETURN

// 1 2 3 4 5 6 7 8

5.2.4.4. algoritmus Halmaz keresése T (n ) = Θ(h ) , h a fa magassága

HALMAZT_KERES( x, y ) // Input paraméter: x – elem mutatója // Output paraméter: y – x halmaza képviselőjének mutatója // y←x IF y ≠ Szülő[ y ] THEN HALMAZT_KERES( Szülő[ y ], y) RETURN ( y ) 5.2.4.5. algoritmus Két diszjunkt halmaz egyesítése

Adatstruktúrák, algoritmusok T (n ) = Θ(h ) , h a magasabb fa magassága

// 1 2 3 4 5 6 7 8 9

- 18 -

EGYESÍT( x, y ) // Input paraméter: x – az egyik elem mutatója // y – a másik elem mutatója // Output: a két elem halmaza egyesítve // HALMAZT_KERES( x, u ) // u az x képviselője HALMAZT_KERES( y, v ) // v az y képviselője ÖSSZEKAPCSOL( u, v ) RETURN 5.2.5. Binomiális fák és binomiális kupac

Definíció:

A binomiális fa A Bk binomiális fa egy rekurzív módon rendezett fa. B0 egyetlen csúcsból áll, Bk pedig két összekapcsolt Bk-1 binomiális fából (k=1,2,3,…), ahol az egyik fa gyökércsúcsa a másik gyökerének legbaloldalibb gyereke.

Alább szemléltetjük a B0, B1, B2, B3 binomiális fákat. B0

Tétel:

B1

B2

B3

A Binomiális fák tulajdonságai Ha Bk binomiális fa, akkor 1. 2k csúcsa van 2. A magassága k ⎛k ⎞ 3. Az i-dik szinten (mélységben) pontosan ⎜⎜ ⎟⎟ (i = 0,1,2,…,k) számú csúcs ⎝i⎠ van. 4. A gyökércsúcs fokszáma k, ami nagyobb, mint bármely más csúcs fokszáma; továbbá ha a gyökércsúcs gyerekeit balról jobbra megszámozzuk k-1, k-2,…,1,0-val, akkor az i. gyerek egy Bi részfa gyökércsúcsa.

Következmény: Egy n csúcsú binomiális fa minden csúcsának fokszáma legfeljebb log2 n. Definíció:

A binomiális kupac Egy H binomiális kupac binomiális fák olyan halmaza, mely rendelkezik az alábbi úgynevezett binomiális-kupac tulajdonságokkal:


- 19 -

1. H minden binomiális fája kupac-rendezett, azaz minden csúcs kulcsa nagyobb vagy egyenlő, mint a szülőjének a kulcsa. 2. Bármilyen fokszámot tekintünk, H-ban legfeljebb egy olyan binomiális fa van, amelyikben a gyökércsúcs fokszáma a tekintett fokszám. Megjegyzés: Egy n elemű binomiális kupac legfeljebb ⎣log2 n⎦+1 binomiális fából áll. Ha felírjuk n kettes számrendszerbeli alakját, akkor a binomiális kupacban azok a binomiális fák szerepelnek, amelyeknek az indexe éppen megegyezik a szám alakjában a szereplő kettő hatvány kitevőjével. Például, ha 11 csúcs van a binomiális kupacban, akkor 11=10112, ezért a kupac három fából áll és ezek a B3, B1, B0 fák. A binomiális kupac műveletei: BINOMIÁLIS_KUPACOT_KÉSZÍT(H) BESZÚR( H, x )

Egy új üres H kupacot készít és ad vissza A H kupacba beszúr egy olyan x csúcsot, amelynek a kulcsmezője már ki van töltve Visszaad egy olyan mutatót, amely a H kupacnak a minimális kulcsú csúcsára mutat A H kupacból kiveszi azt a csúcsot, amelynek a kulcsa minimális, és visszaad egy erre a csúcsra mutató pointert Egy olyan új H kupacot készít és ad vissza, amelyik a H1 és H2 minden csúcsát tartalmazza. H1 és H2 megsemmisül A H kupac x csúcsához az új k kulcs-értéket rendeli hozzá, feltéve, hogy ez az érték nem nagyobb, mint az eredeti. A H kupacból az x csúcsot törli.

BINOMIÁLIS_KUPACBAN_MIN( H, min ) KIVESZ_MIN( H, min ) EGYESÍT( H1, H2, H ) KULCSOT_CSÖKKENT( H, x, k ) TÖRÖL( H, x )

A binomiális kupac ábrázolásakor a kupacban szereplő fákat a gyökércsúcs fokszáma szerinti növekedő sorrendnek megfelelően soroljuk fel. A gyökércsúcsokat egy listára fűzzük fel, melynek a kezdetére egy fejelem mutató mutat. Fejelem[H]

1

10

12

18

6

25

11

8

14

17

38

29

27

Kirészletezzük az egyes csúcspontok mezőit is. Minden csúcspontban az alábbi kísérő információkat tároljuk. Szülő mutató Kulcs Fokszám


- 20 Bal gyerek Jobb testvér mutató mutató

Az előző ábra ezen információkkal kirészletezve:

Fejelem[H]

nil

nil

nil

10

1

6

0

2

3

nil

nil

12

25

8

14

29

1

0

2

1

0

nil

18 0 nil

nil

11

17

38

1

0

0

nil

nil

nil

nil

27 0 nil

nil

Pszeudokódok a műveletekre.

// 1 2 3 4 5

5.2.5.1. algoritmus Binomiális kupac készítése T (n ) = Θ(1)

BINOMIÁLIS_KUPACOT_KÉSZÍT( H ) // Output paraméter: H az üres új binomiális kupac // fejelem[H] ← NIL RETURN ( H )

//

5.2.5.2. algoritmus Binomiális kupacban minimumkeresés T (n ) = Θ(log n )

1 BINOMIÁLIS_KUPACBAN_MIN( H, min ) 2 // Input paraméter: H – a binomiális kupac 3 // Output paraméter: min – mutató a minimális elemre

nil

nil

Adatstruktúrák, algoritmusok 4 5 6 7 8 9 10 11 12 13 14

// min ← NIL x ← fejelem[H] minkulcs ← ∞ WHILE x ≠ NIL DO IF kulcs[ x ] < minkulcs THEN minkulcs ← kulcs[ x ] min ← x x ← testvér[ x ] RETURN ( min )

// 1 2 3 4 5 6 7 8 9 10 11

- 21 -

5.2.5.3. algoritmus Binomiális fák összekapcsolása T (n ) = Θ(1)

BINOMIÁLIS_ÖSSZEKAPCSOLÁS ( y, z ) // Két Bk-1 y és z gyökércsúcsú fát összekapcsol // Input paraméter: y – az első fa gyökérmutatója // z – a második fa gyökérmutatója // Output paraméter: z – az eredményfa gyökérmutatója // szülő[ y ] ← z testvér[ y ] ← gyerek[ z ] gyerek[ z ] ← y INC ( fokszám[ z ] ) RETURN ( z ) 5.2.5.4. algoritmus Binomiális kupacok egyesítése

//

T (n ) = Θ(log n )

1 3 4 5 6 7

BINOMIÁLIS_KUPACOKAT_EGYESIT ( H1, H2, H ) // Input paraméter: H1 – az első kupac // H2 – a második kupac // Output paraméter: H – az eredmény kupac // // A kupacok gyökércsúcsainak listáit összefésüli növekvő fokszám szerint. Minden fokszámhoz legfeljebb két gyökércsúcs tartozhat. Ezután az azonos fokszámúakat összekapcsolja egy magasabb fokszámúvá. Átmenetileg előfordulhat, hogy azonos fokszámmal három gyökércsúcs is rendelkezik. Ilyenkor az összekapcsolást az utolsó kettőre kell elvégezni. 8 RETURN ( H ) 5.2.5.5. algoritmus Binomiális kupacba beszúrás

// 1 BINOMIÁLIS_KUPACBA_BESZÚR ( H, x )

T (n ) = Θ(log n )


- 22 -

3 4 5 6 7

// Input paraméter: H1 – a kupac // x – beszúrandó elem mutatöja // Output paraméter: H – a megváltozott kupac // // Létrehozunk egy egy csúcsból álló új binomiális kupacot, amely a beszúrandó csúcsot tartalmazza. Az új és a régi kupacot egyesítjük. (5.2.5.4. algoritmussal.) 8 RETURN ( H ) 5.2.5.6. algoritmus Binomiális kupacból minimum kivágása

//

T (n ) = Θ(log n )

1 2 3 4 5

BINOMIÁLIS_KUPACBÓL_MINIMUMOT_KIVÁG ( H ) // Input paraméter: H – a kupac // Output paraméter: H – a megváltozott kupac // // Megkeressük a gyökérlánc minimális elemét. A minimális elem fáját a gyökérlistából kiláncoljuk. A minimális elem gyerekeinek listáját megfordítjuk és létrehozunk egy binomiális kupacot, amelynek ez lesz a gyökérlistája. A két kupacot egyesítjük. 6 RETURN ( H ) 5.2.5.7. algoritmus Binomiális kupacban kulcsérték csökkentése

//

T (n ) = Θ(log n )

1 2 3 4 5 6 7

BINOMIÁLIS_KUPACBAN_KULCSOT_CSÖKKENT ( H, x, k ) // Input paraméter: H – a kupac // x – mutató a csökkentendő kulcsú elemre // k – az új kulcsérték // Output paraméter: H – a megváltozott kupac // // A csökkentett kulccsal az elemet a fájában mindaddig felfelé buborékoltatjuk cserékkel, amíg a kupac tulajdonság nem teljesül. Az elem eljuthat akár a gyökérlistáig is. 8 RETURN ( H ) 5.2.5.7. algoritmus Binomiális kupacból törlés

// 1 2 3 4 5 6 7 7

T (n ) = Θ(log n )

BINOMIÁLIS_KUPACBÓL_TÖRÖL ( H, x ) // Input paraméter: H – a kupac // x – mutató a törlendő elemre // Output paraméter: H – a megváltozott kupac // BINOMIÁLIS_KUPACBAN_KULCSOT_CSÖKKENT( H, x, - ∞ ) BINOMIÁLIS_KUPACBÓL_MINIMUMOT_KIVÁG( H ) RETURN ( H )

5. A gráf, mint adatstruktúra Gráfelméleti bevezető

Recommend Documents