Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

6. fejezet - Gráfelméleti algoritmusok

6. fejezet - Gráfelméleti algoritmusok

6.1. A szélességi keresés

  1. éleit vizsgálja és rátalál minden -ből elérhető csúcsra.

  2. Kiszámítja az elérhető csúcsok legrövidebb (legkevesebb élből álló) távolságát -től.

  3. Létrehoz egy gyökerű ,,szélességi fát”, amelyben az -ből elérhető csúcsok vannak.

  4. A csúcsoknak szint tulajdonít (fehér, szürke, fekete). Kezdetben minden csúcs fehér, kivéve -et, amely szürke. Szürke lesz egy csúcs, ha elértük és fekete, ha megvizsgáltuk az összes belőle kiinduló élt.

  5. A szélességi fa kezdetben az csúcsból áll. Ez a gyökér.

  6. Ha egy fehér csúcshoz értünk az csúcsból, akkor azt felvesszük a fába éllel és lesz a szülője.

Attributumok

: az csúcs színe

: az csúcs elődje

táv : az távolsága -től

: a szürke csúcsok sora

6.1. Definíció. jelölje a legrövidebb úthosszat -ből -be, ha létezik út -ből -be, egyébként (s,v) legyen .

6.2. Lemma. Legyen digráf vagy gráf és tetszőleges csúcs. Ekkor bármely él esetén .

6.3. Lemma. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés által kiszámított táv értékek minden csúcsra kielégítik a táv[v] egyenlőtlenséget.

6.4. Lemma. Tegyük fel, hogy a szélességi keresést alkalmaztuk a gráfra és a futás során a sor a csúcsokat tartalmazza. ( az első, az utolsó). Ekkor táv táv és táv táv bármely értékre.

6.5. Tétel. Legyen gráf és tegyük fel, hogy a szélességi keresés algoritmust alkalmaztuk egy kezdőcsúccsal. Ekkor a szélességi keresés minden -ből elérhető csúcsot elér és befejezéskor táv , . Továbbá bármely -ből elérhető csúcsra az -ből -be vezető legrövidebb utak egyikét megkapjuk, ha az -ből -be vezető legrövidebb utat kiegészítjük a () éllel.

6.6. Definíció. fát előd részfának nevezzük, ha

és

6.7. Definíció. A előd részfa szélességi fa, ha elemei az -ből elérhető csúcsok és bármely csúcsra egyetlen egyszerű út vezet -ből -be -ben

6.8. Lemma. A szélességi keresés olyan értékeket határoz meg, amelyekre a előd részfa egy szélességi fa.

Eljárás az -ből -be vezető legrövidebb út csúcsai kiírására: