Tarjanin algoritmi
Tarjanin algoritmi eli Tarjanin vahvasti yhtenäisten komponenttien algoritmi on syvyyssuuntaisen läpikäynnin algoritmi. Algoritmin esitti Robert Tarjan vuonna 1972. Tarjanin algoritmia ja käytetään tunnistamaan vahvasti liittyvät komponentit graafiteorian mukaisesti. Tarjanin algoritmi ja Kosarajun algoritmi ovat kaksi yleisesti käytettyä algoritmia tähän tarkoitukseen.[1][2] Toisin kuin Kosarajun algoritmissa, Tarjanin algoritmille riittää yksi kerta syvyyssuuntaiselle haulle ja tila pidetään erillisessä pinossa. Tarjanin algoritmi on suosittu nopeuden ja suhteellisen suoraviivaisen toteutuksen ansiosta. Kosarajun ja Tarjanin algoritmien heikkous on sarjamuotoinen käsittely, joka ei sovellu hyvin rinnakkaiseen käsittelyyn.[3]
Syvyyssuuntainen läpikäynti on hyödyllistä graafien analysointiin ja mahdollistaa eri ongelmien ratkaisun lineaarisessa ajassa (käytetty aika kasvaa lineaarisesti graafin koon mukaan). Vahvasti liittyvät komponentit tarkoittavat paria solmuja, jotka ovat komponentteja yhdistelmälle. Graafin sanotaan olevan vahvasti kytketty jos sillä on yksi vahvasti kytketty komponetti.[4]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ CS130 Software Engineering (PDF) courses.cms.caltech.edu. talvi 2024. Viitattu 4.6.2024. (englanniksi)
- ↑ Robert Tarjan: Depth-first search and linear graph algorithms (PDF) 2.6.1972. Arkistoitu . Viitattu 4.6.2024. (englanniksi)
- ↑ Andrew Gamble: Survey of Strongly Connected Components Algorithms (PDF) andrewgamble.com. kevät 2020. Viitattu 4.6.2024. (englanniksi)
- ↑ Depth First Search and Strong Components (PDF) cs.cmu.edu. 1.11.2018. Viitattu 4.6.2024. (englanniksi)