Gabow algoritem

Iz MaFiRaWiki

(Preusmerjeno iz Gabow's algoritem)
Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Ker iščemo močno povezane komponente v usmerjenem grafu, imamo na začetku graf, ki ima usmerjene povezave.

Slika:slika1.png


Poljubno si izberemo začetno vozlišče, nato nadaljujemo z gradnjo drevesa v globino. Seveda ni nujno, da bomo zgradili dvojiško drevo, lahko je poljubno, ali še več, lahko zgradimo več takih dreves, ki nimajo skupnih vozlišč, temu pravimo gozd. V našem primeru bomo začeli z 0. Pogledamo, kam lahko gremo iz vozlišča 0. Vidimo, da je možnih povezav, ki vodijo iz vozlišča 0 več (do 5, 1 ali do 6), ker pa vrstni red izbire ni pomemben, si bomo izbrali povezavo, ki nas pripelje do vozlišča 5.

Slika:slika2.png


Iz vozlišča 5 lahko nadaljujemo pot do vozlišča 4.

Slika:slika3.png


Iz vozlišča 4 lahko pridemo do vozlišča 3, iz 3 pa do vozlišča 5 in do 2, a vozlišče 5 je bilo že obiskano, zato ga tokrat ne obiščemo. Iz 2 bi lahko nadeljevali do vozlišči 0 in 3, a ker sta bili že obe prej obiskani, se vrnemo nazaj do vozlišča 4. Od tu lahko nadaljujemo pot do vozlišča 11.

Slika:slika4.png


Iz 11 obstaja povezava samo do vozlišča 12, iz 12 pa lahko pridemo samo do vozlišča 9. Od tu bi lahko prišli do vozlišča 11, a smo tam že bili, zato nam ne preostane drugega kot povezava do vozlišča 10. Iz vozlišča 10 bi lahko obiskali vozlišče 12, a smo tam že bili. Vrnemo se nazaj do vozlišča 4, kjer opazimo, iz vozlišča 4 obstaja še povezava do vozlišča 2, a je ni potrebno prehoditi, ker je bilo vozlišče 2 že obiskano preko vozlišča 3.

Slika:slika5.png


Vrnemo se nazaj, vse do vozlišča 0, iz katerega lahko obiščemo še vozlišče 1. Ker iz vozlišča 1 ne obstaja nobene povezave, se vrnemo nazaj do vozlišča 0. Pogledamo, če od 0 vodi še katera povezava do vozlišča, ki ga še nismo obiskali. Opazimo, da lahko pridemo do vozlišča 6. Od tu lahko pridemo do 4 in 9, a sta bili že obe vozlišči obiskani.

Slika:slika6.png


Ostane nam še vozlišče 7. Iz vozlišča 7 lahko obiščemo vozlišče 6, ki pa smo ga že obiskali ter vozlišče 8. Od vozlišča 8 vodijo povezavi do vozlišča 7 in 9, a smo pri obeh že bili.

Slika:slika7.png

Zgradili smo gozd, ki ga sestavlja eno poljubno drevo in eno dvojiško drevo.

Sedaj naredimo premi pregled gozda. Torej, premi pregled dvojiškega drevesa je pregled, kjer najprej obiščemo koren (oče), potem levo poddrevo (levi sin) in nato še desno poddrevo (desni sin). Ker ni nujno, da gozd sestavljajo samo dvojiška drevesa, premi pregled izgleda približno enako kot pri dvojiških drevesih, le da tukaj obiščemo vse sinove v smeri iz leve proti desni. Torej, če ima vozlišče naprimer tri sinove, obiščemo najprej skrajno levega, nato sredinskega in kasneje še skrajno desnega sina. Rdeče številke, zraven vozlišč so indeksi, ki nam povedo katero po vrsti je bilo obiskano posamezno vozlišče (pre), te zapišemo v tabelo, ki smo si jo predhodno pripravili.

Slika:slika8.png


Slika:slika9.png


Kako deluje Gabow algoritem za iskanje močno povezanih komponent?

Najprej iz usmerjenega grafa naredimo drevo, ki je lahko poljubno. Ker pa je lahko teh poljubnih dreves tudi več, pravimo, da gradimo gozd. Nato naredimo premi pregled drevesa in si indekse, ki nam določijo vrstni red obiska posameznega vozlišča, zapišemo v tabelo. To je prikazano zgoraj.

Nato si pripravimo sklada S in P, kjer bo vsa stvar potekala. In sicer. Vrstni red vozlišč imamo določen, določimo si ga s premim pregledom. Začnemo z vozliščem, ki smo ga obiskali kot prvega in ga damo v oba sklada. In tako nadaljujemo po vrsti. Ko pridemo do situacije, da ima vozlišče, ki ga obdelujemo za soseda vozlišče, ki je bilo že obiskano, moramo iz sklada P odstraniti vsa tista vozlišča, ki imajo večji indeks od indeksa tistega vozlišča, ki je bilo že obiskano. Ko pa bomo naleteli do vozlišča, ki nima sosedov, ki bi jih lahko obdelali se vprašamo, ali je to vozlišče v tem trenutku na vrhu sklada P. Če je odgovor ne, potem se vrnemo nazaj do vozlišča, ki je bil obiskan pred njim. Zopet se vprašamo isto vprašanje. To ponavljamo, dokler ne dobimo pritrdilnega odgovora. Takrat smo našli močno povezano komponento. Torej, ko je enkrat odgovor da, moramo iz sklada S odstraniti vsa tista vozlišča, ki so za tem vozliščem, ki je bil tisti hip na vrhu sklada P, vključno z njim. Ta vozlišča predstavljajo močno povezano komponento, zato jim v tabeli predpišemo isto število. Ko najdemo nasljednjo močno povezano komponento, tistim vozliščem, ki jo predstavljajo, to število povečamo za ena.

Poglejmo to še na našem konkretnem primeru.

Začnemo z 0 in ga damo v oba sklada. Nadaljujemo z vozliščem 5, tudi 5 damo v oba sklada. Nasljednje vozlišče, ki smo ga obiskali je vozlišče 4, tudi to vozlišče dodamo v oba sklada. Naslednje je vozlišče 3, ki ga pravtako dodamo v oba sklada. Do sedaj se ni zgodilo še nič posebnega, le vozlišča smo dodajali v oba sklada po tistem vrstnem redu, kot so bili obiskani. Torej sklada po teh korakih izgledata takole:

Slika:slika10.png


Sedaj smo pri sosedih vozlišča 3. Vidimo, da bi lahko iz vozlišča 3 prišli do vozlišča 5. Torej naleteli smo na situacijo, ko moramo iz sklada P odstraniti vsa tista vozlišča, ki imajo večji indeks kot je indeks vozlišča 5. Pri premem pregledu drevesa, smo vozlišče 5 obiskali kot prvega po vrsti. Torej, vozlišče 5 ima indeks 1, kar je lepo vidno iz tabele. Iz sklada P moramo odstraniti vsa tista vozlišča, ki imajo večji indeks od 1. Pa poglejmo, vozlišče 3 je bilo obiskano kot tretje po vrsti, torej ima indeks 3, ker je ta večji od indeksa vozlišča 5, ki je 1, moramo vozlišče 3 odstraniti iz sklada P. Nadaljujemo po istem postopku. Naslednje vozlišče, ki je sedaj na vrhu sklada P je vozlišče 4, njen indeks je 2, ki je še vedno večji od indeksa vozlišča 5, zato tudi vozlišče 4 odstranimo iz sklada P.Odstranili smo vozlišče 3 in 4. Sklad S ne spreminjamo. Stanje v skladih je sedaj takšno:

Slika:slika11.png


Na vrsti je vozlišče 2. Dodamo ga v oba sklada.

Slika:slika12.png


Ker bi iz vozlišča 2 lahko prišli do vozlišča 0, moramo iz sklada P odstraniti vsa vozlišča, ki imajo večji indeks od indeksa vozlišča 0, ki je 0. Odstranimo vozlišče 2, ki ima indeks 4, ter vozlišče 5, ki ima indeks 1. Sklada S ne spreminjamo.

Slika:slika13.png


Ko pregledamo vse sosede vozlišča, se pravi, da ne moremo več naprej v globino, se vprašamo ali je to vozlišče, v našam primeru vozlišče 2, na vrhu sklada P. Ker vidimo, da ni, se vrnemo nazaj do vozlišča 3. Tud tokrat si postavimo isto vprašanje. Ali je 3 na vrhu sklada P? Ne. Vrnemo se nazaj do vozlišča 4. Tukaj pa se ne moremo vprašati istega vprašanja kot prej, ker ima vozlišče 4 še sosede, ki jih še nismo obdelali. Zato nadaljujemo z vozliščem 11, ki ga dodamo v oba sklada. Ker gremo iz vozlišča 11 lahko samo do vozlišča 12, pravtako 12 dodamo v oba sklada. Enako se zgodi z vozliščem 9, do katerega pridemo samo iz vozlišča 12. Torej, dodamo ga v sklad S in sklad P. Po teh korakih sklada izgledata tako:

Slika:slika14.png


Vidimo, da iz vozlišča 9 lahko pridemo do vozlišča 11. Zato moramo iz sklada P odstaniti vsa tista vozlišča, ki imajo večji indeks kot je indeks vozlišča 11. Torej, vozlišče 9 je bilo obiskano sedmo po vrsti, torej ima indeks 7, vozlišče 11 pa je bilo obiskano peto po vrsti, ker je 7 > 5, moramo vozlišče 9 iz vrha sklada P odstraniti. Naslednje vozlišče, ki pravtako izpolnjuje pogoj za odstranitev iz sklada P, je vozlišče 12, saj je bilo vozlišče 12 obiskano za vozliščem 11. Sklad S ostane nespremenjen.

Slika:slika15.png


Naslednje vozlišče, ki ga še nismo obiskali in je sosed od vozlišča 9, je vozlišče 10, ki ga dodamo v oba sklada.

Slika:slika16.png


Ker opazimo, da bi iz vozlišča 10 lahko prišli do vozlišča 12, pa je ta že bil obiskan, moramo zopet iz sklada P odstraniti tista vozlišča, ki imajo večji indeks od vozlišča 12. Se pravi, odstranimo vozlišče 10. Trenutno stanje v skladih je sledeče:

Slika:slika17.png


Ker vozlišče 10 nima več sosedov, ki jih še nismo obdelali, se zopet vprašamo, ali je 10 na vrhu sklada P, ker ni, se vrnemo nazaj, torej do vozlišča 9. Ali je 9 na vrhu sklada P? Ne. Vrnemo se nazaj, do vozlišča 12. Ali je 12 na vrhu sklada P? Tudi ne, zato se vrnemo nazaj do vozlišča 11. Ali je 11 na vrhu sklada P? Da. Ker je 11 vozlišče, ki ga obdelujemo in je hkrati na vrhu sklada P, sledi, da vsa vozlišča, ki so v skladu S za vozliščem 11 in vključno z 11 predstavljajo močno povezano komponento.

Slika:slika17a.png


Odstranimo jih iz sklada S ter jim določimo število, ki določa v katero močno povezano komponento spadajo.

Slika:slika13.png


Ker smo našli prvo močno povezano komponento jim določimo število 0. V tabelo, ki jo imamo še od prej dopolnimo s tem podatkom.

Slika:slika18.png


Nadaljujemo s pregledovanjem sosedov vozlišča 4. Opazimo, da je tudi vozlišče 2 njen sosed. Kaj sledi? Iz sklada P moramo odstraniti vsa vozlišča, ki imajo večji indeks od indeksa vozlišča 2, ker pa takih vozlišč ni, stanje v skladih ostane isto, zato se vrnemo nazaj do vozlišča 5. Ker vozlišče 5 nima drugih neobiskanih sosedov, se vrnemo nazaj do vozlišča 0. Stanje v skladih S in P je še vedno isto. In sicer:

Slika:slika13.png


Pregledujemo sosede vozlišča 0. Sosed, ki ga še nismo obdelali je vozlišče 1 in ga dodamo v oba sklada.

Slika:slika19.png


Ker iz vozlišča 1 ne moremo nikamor, se vprašamo, ali je vozlišče 1 na vrhu sklada P. Ker je odgovor da, smo zopet našli močno povezano komponento. Torej iz sklada S odstanimo vsa vozlišča, ki so bila dodana za vozliščem 1 vključno z vozliščem 1.

Slika:slika19a.png


Iz sklada jih odstranimo.

Slika:slika13.png


V tabeli jim predpišemo število 1.

Slika:slika20.png


Vozlišče 0 ima še enega neobiskanega soseda, to je vozlišče 6. Zato ga dodamo v sklad S in sklad P.

Slika:slika21.png


Ker iz vozlišča 6 lahko pridemo do vozlišča 4, a je bilo to vozlišče že obiskano, moramo v skladu P odstraniti vsa tista vozlišča, ki smo jih dodali za vozliščem 4. Torej odstranimo samo 6, saj vozlišča iz sklada P odstranjujemo toliko časa, dokler je izpolnjen pogoj, torej, toliko časa, dokler je indeks (pre) vozlišča, ki je trenutno na vrhu sklada P večji od indeksa (pre) vozlišča, ki ga tisti trenutek obdelujemo.

Slika:slika22.png


Ker vozlišče 6 nima sosedov, ki še niso bili obiskani, si postavimo vprašanje, ali je 6 na vrhu sklada P. Ni, torej se vrnemo nazaj do vozlišča 0. Zopet se vprašamo, ali je 0 na vrhu sklada P? Da. Našli smo tretjo močno povezano komponento. Torej, iz sklada S odstranimo vsa vozlišča, ki so za vozliščem 0, vključno z 0.

Slika:slika22a.png


Sklada ostaneta prazna.

Slika:slika24a.png


V tabeli, vsem tem vozliščem, ki predstavljajo tretjo močno povezano komponento določimo število 2.

Slika:slika23.png


Ostane nam še vozlišče 7, ki ga dodamo v oba sklada.

Slika:slika24.png


Iz vozlišča 7 bi lahko obiskali vozlišče 6, a je ta že bil obiskan, zato pride na vrsto pregled indeksov, ker pa ima vozlišče 6 manjši indeks kot vozlišče 7, ne naredimo nič drugega, kot da pogledamo še neobiskane sosede vozlišča 7. To je vozlišče 8 in ga dodamo v oba sklada.

Slika:slika25.png


Ker bi lahko iz vozlišča 8 prišli do vozlišča 7, a je to vozlišče že bilo obiskano, moramo iz sklada P odstraniti vsa vozlišča, ki imajo večji indeks od vozlišča 7. Torej iz sklada P odstranimo vozlišče 8. Sklada S ne spreminjamo.

Slika:slika26.png


Ker ima vozlišče 8 še za soseda vozlišče 9, a smo ga že obiskali, je na vrsti vprašanje, ki si ga zastavimo, ko vozlišče nima sosedov. Ali je 8 na vrhu sklada P? Odgovor je ne, zato se vrnemo nazaj, do vozlišča 7. Ponovno se vprašamo, ali je 7 na vrhu sklada P? Ker pa je tokrat odgovor da, smo našli še četrto močno povezano komponento. Kaj sledi. Iz sklada S odstranimo vsa vozlišča, ki so za vozliščem 7, vključno z njim.

Slika:slika26a.png


Sklada ostaneta prazna. V tabeli pa dopolnimo še manjkajoče. In sicer, vozliščem, ki predstavljajo četrto močno povezano komponento, predpišemo število 3.

Slika:slika27.png


S tem je končan naš algoritem za iskanje močno povezanih komponent v usmerjenem grafu, po verziji Gabowa.

Osebna orodja