Algoritam za nalaženje komponenti povezanosti

U teoriji grafova, komponente povezanosti usmerenog grafa mogu biti nađene koristeći algoritam koji vrši pretragu u dubinu u kombinaciji sa dva steka: jedan koji pamti čvorove u datoj komponenti (povezanosti) i drugi koji pamti čvorove u tekućoj pretrazi u dubinu. Neke verzije algoritma predložili su Purdom 1970, Munro 1971, Dijkstra 1976, Cheriyan & Mehlhorn 1996, i Gabow 2000; od ovih, Dijkstrin algoritam je bio prvi koji je postigao linearno vreme.

Opis

Algoritam prvo uradi pretragu u dubinu datog grafa G, koristeći dva steka S i P. Stek S sadrži sve čvorove koji još uvek nisu pripisani nijednoj komponenti povezanosti, u poretku u kom ih pretraga u dubinu smešta na stek. Stek P sadrži čvorove za koje još nije utvrđeno da pripadaju različitim komponentama povezanosti. Takođe koristi brojač S- broj do sada smeštenih čvorova, koji koristi da bi utvrdio brojeve čvorova u preorder obilasku.

Kada pretraga u dubinu dođe do čvora v, algoritam radi sledeće:

1. Postavlja S na broj čvora v pre uređivanja i inkrementira S.
2. Stavlja v na stek S i P.
3. Za svaki čvor u koji je sused čvora v:
   • Ako čvoru u još uvek nije postavljen broj po preorder obilasku, rekurzivno pretraži u;
   • Inače, ako u još uvek nije pridružen komponenti povezanosti:
     • Skida čvor sa steka R sve dok se na vrhu steka pojavi element koji ima preorder broj manji ili jednak preorder broju čvora u.
4. Ako je v najviši element steka R:
   • Skida element sa steka S sve dok ne skine čvor v i skinute čvorove pridružuje novoj komponenti povezanosti.
   • Skida v sa steka R.

Glavni algoritam sastoji se od petlje koja obilazi čvorove grafa i poziva ovu rekurzivnu pretragu za svaki čvor kome još uvek nije dodeljen broj dobijen preorder obilaskom.

Povezani algoritmi

Kao i gore pomenuti, Tarjanov algoritam za nalaženje komponenti povezanosti, takođe koristi pretragu u dubinu zajedno sa stekom koji pamti koji čvorovi još uvek nisu dodeljeni nijednoj komponenti povezanosti, i koji pridružuje ove čvorove novoj komponenti kada se trenutna komponenta ne može više proširiti. Međutim, umesto drugog steka, Tarjanov algoritam koristi niz prethodno uređenih brojeva, pomoću kog određuje kad treba formirati novu komponentu.

Literatura

• Cheriyan, J.; Mehlhorn, K. (1996), „Algorithms for dense graphs and networks on the random access computer”, Algorithmica, 15: 521—549, doi:10.1007/BF01940880 .
• Dijkstra, Edsger (1976), A Discipline of Programming, NJ: Prentice Hall, Ch. 25 .
• Gabow, Harold N. (2000), „Path-based depth-first search for strong and biconnected components”, Information Processing Letters, 74 (3-4): 107—114, MR 1761551, doi:10.1016/S0020-0190(00)00051-X .
• Munro, Ian (1971), „Efficient determination of the transitive closure of a directed graph”, Information Processing Letters, 1: 56—58 .
• Purdom, P., Jr. (1970), „A transitive closure algorithm”, BIT, 10: 76—94 .
• Sedgewick, R. (2004), „19.8 Strong Components in Digraphs”, Algorithms in Java, Part 5 – Graph Algorithms (3rd izd.), Cambridge MA: Addison-Wesley, str. 205—216 .