Kosarajujev algoritem

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Kosaraju's algoritem je eden izmed treh algoritmov, ki nam pomagajo poiskati močno povezane komponente v usmerjenem grafu.
Kako algoritem deluje, bom opisala na primeru.


Slika:Sl1.png

                     Slika 1: Graf G
  • Najprej na grafu G obrnemo usmerjene povezave v obratno smer.
  • Nato pa na obrnjenem grafu naredimo pregled v globino - DFS (Depth first search).

Slika:Sl2.png

                     Slika 2: Graf G_1, ki ima obratno usmerjene povezave.
  • Algoritem začnemo z grafom G_1.
  • Na desni strani bomo risali drevo, za katerega se na koncu izkaže, da dobimo gozd.
  • Vozlišča obarvana sive barve lahko obravnavamo kot, da jih NI.
  • Na koncu pa napišemo še tabelo indeksov (obratni pregled drevesa).

Slika:Sl3.png

  • Poiščemo vozlišče z najmanjšo številko.
  • Torej, začnemo z vozliščem 0.
  • Vozlišče 0 gre lahko samo do vozlišča 2.
  • Na desni strani v drevesu narišemo vozlišče 0, ki gre v vozlišče 2.

Slika:Sl4.png

  • * Iz vozlišča 2, gremo lahko v vozlišče 3 ali 4.
  • Če imamo na kakšnem koraku več izbir vozlišč, izberemo tistega, ki ima najmanjšo številko.
  • Tudi v našem koraku je tako, zato izberemo vozlišče 3.
  • Vozlišče 4 ne smemo izbrati (v drevesu je obarvan sive barve).

Slika:Sl5.png

  • Iz vozlišča 3 gremo lahko v vozlišče 2 ali vozlišče 4.
  • Če imamo med postopkom možnost priti v vozlišče, ki smo ga že obiskali, ga še enkrat ne smemo. Zato to vozlišče ne smemo še enkrat obravnavati v postopku.
  • V našem koraku imamo vozlišče 2 že obiskano, zato ga ne smemo izbrati. Izberemo vozlišče 4.
  • Vozlišče 2 v drevesu obarvamo sive barve.

Slika:Sl6.png

  • Iz vozlišča 4 gremo lahko v vozlišče 5 ali vozlišče 6.
  • Izbrati moramo vozlišče 5, saj je manjše od vozlišča 6 in še ni obravnavano.

Slika:Sl7.png

  • Iz vozlišča 5 gremo lahko v vozlišče 0 ali vozlišče 3. Nobenega od njiju ne smemo vzeti, saj sta bila že oba obravnavana. Zato končamo in se vrnemo eno vozlišče nazaj.
  • To je vozlišče 4, pogledamo če imamo še kakšno možnost iz tega vozlišča.
  • Vozlišče 0 in vozlišče 3 obarvamo v drevesu sive barve.

Slika:Sl8.png

  • Iz vozlišča 4 pa sedaj lahko gremo samo v vozlišče 6, saj je hkrati še edino ne obiskano.

Slika:Sl9.png

  • Iz vozlišča 6 imamo dve izbiri. Ali vozlišče 0 ali vozlišče 7.
  • Vozlišče 0 je že bilo obiskano, zato ga ne smemo vzeti, v drevesu ga obarvamo sive barve.
  • Zato izberemo vozlišče 7, saj je najmanjše ne obiskano vozlišče.

Slika:Sl10.png

  • Iz vozlišča 7 gremo lahko samo v vozlišče 8.
  • Ker to vozlišče še ni bilo obiskano, gremo v to vozlišče.

Slika:Sl11.png

  • Iz tega vozlišča gremo lahko v vozlišče 7.
  • To vozlišče je bilo že obiskano, zato gremo eno vozlišče nazaj, to je vozlišče 7. Iz tega ne moremo nikamor, zato gremo še eno vozlišče nazaj, to je vozlišče 6.
  • Iz vozlišča 6 tudi ne moremo iti nikamor, zato gremo spet eno vozlišče nazaj, to je vozlišče 4.
  • ...
  • Pregledamo vse do prvega začetnega vozlišča v drevesu, to je v našem primeru vozlišče 0, če imamo še kakšno možnost do ne obiskanega vozlišča.

Slika:Sl12.png

  • Prišli smo do koraka, kamor ne moremo iti nikamor več nazaj.
  • Zato končamo. Našli smo prvo drevo.
  • Sedaj pogledamo prvo najmanjše ne obiskano vozlišče v grafu in začnemo delati drugo drevo.
  • To je vozlišče 1.

Slika:Sl13.png

  • Iz vozlišča 1 gremo lahko samo v vozlišče 0.
  • To vozlišče je bilo že obiskano zato ga ne smemo izbrati.
  • Ker nimamo nobenega drugega ne obiskanega vozlišča, kamor bi lahko šli iz vozlišča 1, končamo.
  • Imamo drugo drevo.

Slika:Sl14.png

  • Poiščemo najmanjše ne obiskano vozlišče v grafu.
  • To je vozlišče 9.

Slika:Sl15.png

  • Iz tega vozlišča gremo lahko v vozlišča 6, 8 ali 12.
  • Vozlišči 6 in 8 sta že bili obiskani, zato ju ne smemo izbrati.
  • Izberemo vozlišče 12.

Slika:Sl16.png

  • Iz vozlišča 12 gremo lahko samo v vozlišče 10.
  • Ker to vozlišče še ni bilo obiskano, ga lahko vzamemo.

Slika:Sl17.png

  • Iz vozlišča 10 gremo lahko samo v vozlišče 9.
  • To vozlišče je že bilo obiskano in ga ne smemo vzeti.
  • Zato se vrnemo eno vozlišče nazaj, to je vozlišče 12.
  • Vozlišče 9 obarvamo sive barve.

Slika:Sl18.png

  • Iz vozlišča 12 obstaja povezava do vozlišča 11, ki še ni bilo obiskano.
  • Vzamemo torej vozlišče 11.

Slika:Sl19.png

  • Iz vozlišča 11 gremo lahko v vozlišči 4 ali 9.
  • Ker sta obe vozlišči že obiskani ju ne smemo vzeti.
  • Vrnemo se eno vozlišče nazaj in pogledamo če obstaja kakšna povezava do vozlišča, ki še ni bilo obiskano.
  • V našem primeru smo obdelali vsa vozlišča, zato končamo.
  • Dobili smo 3 drevesa v gozdu.

Slika:Sl20.png

  • Ko obiščemo vsa vozlišča, naredimo obratni pregled.
  • Dobimo ga iz dreves, ki predstavljajo pregled v globino.
  • Obratni pregled je: levi sin, desni sin, oče.
  • Nato se vrnemo na prvotni graf, graf G, ter delamo postopek naprej.
  • Na koncu tega pregleda grafa pa bomo dobili našo rešitev grafa, ki jo iščemo.
  • To so močno povezane komponente.

Slika:Sl21.png

  • V tem grafu pa glede katero začetno vozlišče vzamemo, gledamo tisto vozlišče, ki ima v obratnem pregledu v tabeli največji indeks.
  • Če imamo iz enega vozlišča več možnosti za izbiro ne obiskanega vozlišča, lahko poljubno izberemo katero ne obiskano vozlišče bomo vzeli.
  • Na desni bomo risali drevesa, ki nam bodo na koncu dala rešitev – močno povezane komponente v grafu.

Slika:Sl22.png

  • Pogledamo v tabelo – obratni pregled.
  • V našem primeru ima največji indeks vozlišče 9.
  • Zato začnemo z vozliščem 9.
  • Pogledamo, kam gremo lahko iz vozlišča 9.
  • Gremo lahko v vozlišči 10 ali 11.
  • Odločimo se za vozlišče 11.

Slika:Sl23.png

  • Iz vozlišča 11 gremo lahko samo v vozlišče 12.
  • Ker je to še ne obiskano vozlišče, vzamemo vozlišče 12.

Slika:Sl24.png

  • Iz vozlišča 12 gremo lahko samo v vozlišče 9.
  • Vozlišče 9 je že bilo obiskano, zato ga ne smemo vzeti (v grafu je obarvan sive barve).
  • Vrnemo se eno vozlišče nazaj, na vozlišče 11.
  • Iz vozlišča 11 nimamo nobene povezave do ne obiskanega vozlišča, zato se vrnemo še eno vozlišče nazaj, na vozlišče 9.

Slika:Sl25.png

  • Iz vozlišča 9 pa imamo še eno povezavo, ki nas pripelje do ne obiskanega vozlišča.
  • To je vozlišče 10.

Slika:Sl26.png

  • Iz vozlišča 10 gremo lahko samo do vozlišča 12.
  • To vozlišče je že bilo obiskano, zato ga ne smemo vzeti.
  • Vrnemo se eno vozlišče nazaj. Na vozlišče 9.
  • Iz vozlišča 9 ne nimamo nobene več povezave do ne obiskanega vozlišča.
  • Iz tega vozlišča se ne moremo pomakniti eno povezavo nazaj, saj je prvo vozlišče s katerim smo začeli.

Slika:Sl27.png

  • Sedaj pogledamo v tabelo indeksov.
  • Gledamo od desne proti levi.
  • Vzamemo prvo vozlišče, ki še ni bilo zasedeno.
  • Torej, vozlišča 9, 12, 11, 10 smo že obiskali (v tabeli obarvane zelene barve).
  • Vozlišče 1 še ni bilo obiskano, zato ga vzamemo in začnemo delati drugo drevo – drugo močno povezano komponento.

Slika:Sl28.png

  • Iz vozlišča 1 vidimo, da nikamor ne moremo iti.
  • Zato tudi tukaj končamo.
  • Iz tabele indeksov pa pogledamo s katerim vozliščem bomo sedaj začeli.
  • Torej, začnemo z vozliščem 0.

Slika:Sl29.png

  • Iz vozlišča 0 gremo lahko v vozlišči 5 ali 1.
  • Vozlišče 1 je že bilo obiskano, zato gremo v vozlišče 5.
  • Vozlišče 1 obarvamo sive barve.

Slika:Sl30.png

  • Iz vozlišča 5 gremo lahko samo v vozlišče 4.
  • Ker vozlišče 4 še ni obiskano, ga vzamemo.

Slika:Sl31.png

  • Iz vozlišča 4 gremo lahko v vozlišča 2 , 3 ali 11.
  • Vozlišče 11 je že obiskano, zato ga barvamo sive barve.
  • Vozlišči 2 in 3 pa nista še obiskani, zato si enega izberemo.
  • Izberemo vozlišče 3.

Slika:Sl32.png

  • Iz vozlišča 3 gremo lahko v vozlišče 5 ali vozlišče 2.
  • Vozlišče 5 je že bilo obiskano, zato ga ne smemo vzeti. V grafu ga obarvamo sive barve.
  • Vozlišče 2 še ni bilo obiskano, zato ga vzamemo.

Slika:Sl33.png

  • Iz vozlišča 2 gremo lahko v vozlišči 0 ali 3.
  • Ker sta bili že obe vozlišči obiskani, ju ne smemo vzeti.
  • Obarvamo ju sive barve.
  • Vrnemo se eno vozlišče nazaj, v vozlišče 3.
  • Tukaj nimamo nobene povezave, ki bi nas pripeljala do ne obiskanega vozlišča, zato se vrnemo še eno vozlišče nazaj.
  • Vozlišče 4 ima povezave 3, 2 in 11, ki pa so že vse obiskane. Vozlišče 2 obarvamo sive barve.
  • Vrnemo se po vozliščih nazaj, da pogledamo če lahko pridemo še do kakšnih ne obiskanih vozlišč. Vračamo se dokler ne pridemo do začetnega vozlišča.

Slika:Sl34.png

  • V vozlišču 0 vidimo, da gremo lahko še do vozlišča 6, ki še ni bilo obiskano.
  • Zato vzamemo vozlišče 6.

Slika:Sl35.png

  • Iz vozlišča 6 gremo lahko do vozlišča 4 ali 9. Oba vozlišča sta že obiskana, zato ju ne smemo vzeti.
  • Vrnemo se vozlišče nazaj do vozlišča 0. Iz tega vozlišča nimamo nobene več povezave do ne obiskanega vozlišča. Tukaj končamo.
  • Sedaj gremo pogledati v tabelo indeksov, katero vozlišče je prvo nezasedeno, ki ima največji indeks.

Slika:Sl36.png

  • Iz tabele je razvidno, da je prvo ne obiskano vozlišče z največjim indeksom vozlišče 7.
  • Zato začnemo z vozliščem 7.

Slika:Sl37.png

  • Iz vozlišča 7 gremo lahko v vozlišča 6 ali 8.
  • Vozlišče 6 je že bilo obiskano, zato ga ne smemo vzeti.
  • Vozlišče 8 še ni bilo obiskano, zato ga lahko vzamemo.
  • Vzamemo vozlišče 8.

Slika:Sl38.png

  • Iz vozlišča 8 gremo lahko v vozlišče 7 ali vozlišče 9.
  • Oba vozlišča sta že obiskana, zato ju ne smemo vzeti.
  • Vrnemo se vozlišče nazaj. V vozlišče 7.
  • Iz vozlišča 7 ne obstaja nobena več povezava do ne obiskanega vozlišča.
  • Tudi v grafu vidimo, da smo obiskali vsa njegova vozlišča.
  • Prišli smo do konca algoritma.

Slika:Sl39.png

  • Sedaj samo še v tabelo napišemo močno povezane komponente.
  • Pogledamo v drevesa, ki smo jih pridobili iz Grafa G. To so drevesa močno povezanih komponent.
  • Pogledamo drevesa iz leve proti desni.
  • Jaz sem jih oštevilčila:
  • Prvo drevo : 0 – 1. močno povezana komponenta
  • Drugo drevo: 1 - 2. močno povezana komponenta
  • Tretje drevo: 2 - 3. močno povezana komponenta
  • Četrto drevo: 3 - 4. močno povezana komponenta
  • V prvi vrstici tabele imamo naša vozlišča, od 0 do 12.
  • Drugo vrstico tabele pa izpolnimo tako, da vsem vozliščem iz prvega drevesa dodamo 0, vsem vozliščem iz drugega drevesa dodamo 1, …
  • Prišli smo do konca našega algoritma.
  • Naš rezultat je, da smo dobili 4 močno povezane komponente.
Osebna orodja