Paras vastaus
Voimakkaasti kytketty komponentti (SCC) suunnatussa kaaviossa on joko sykli tai yksittäinen kärkipiste.
Käytämme DFS: ää kaaviossa ja seuraamme kahta ominaisuutta kullekin tuotetulle DFS-puun solmulle: 1. Sen aika (tai järjestys) löydettiin ensimmäisen kerran DFS: ssä. ( sano p1) 2. Vanhimman esi-isän järjestys, jonka se voi saavuttaa (sanoa p2) Aluksi molemmat ovat samat jokaiselle solmulle. Vaikka 1. ominaisuus pysyy vakiona, toinen voidaan päivittää rekursiivisten DFS-puheluiden aikana ja käyttää sitä etureiden etureunojen etsimiseen. Jos molemmat pisteet ovat samat rekursiivisten DFS-kutsujen jälkeen kaikkiin sen vierekkäisiin pisteisiin, se on joko 1. Yksittäinen kärkipiste, joka ei ole osa mitään sykliä. TAI 2. Osa syklistä ja siten kaikki sen jälkeläiset (tuotetussa DFS-puussa) voivat saavuttaa sen (ei pääse esivanhempiinsa). Toisin sanoen voimme aloittaa ja päättyä tästä solmusta. Toisessa tapauksessa voimme seurata kaikkia tulostettavia jälkeläisiä.
tämä animaatio auttaa ymmärtämään selitystä (ensimmäinen kokonaisluku on p1, toinen on p2):
@ Tiedosto: Tarjanin algoritmianimaatio.gif
Yksityiskohtainen selitys ja c ++ -toteutus: Tarjan ”s Algoritmi vahvasti kytkettyjen komponenttien löytämiseksi – GeeksforGeeks
PS: Tämä algoritmi on hyvin samanlainen kuin nivelpisteiden, siltojen ja kaksinkytkettyjen kaavioiden löytäminen. Joten näiden oppiminen ensin voi auttaa sinua saamaan paremman intuition algoritmille. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Vastaus
Algoritmi ottaa suunnatun kaavion syötteeksi ja tuottaa osion kuvaajan pisteistä kaavion vahvasti liitettyihin komponentteihin. Kaavion kukin kärki näkyy täsmälleen yhdessä vahvasti liitetyistä komponenteista. Mikä tahansa kärkipiste, joka ei ole suunnatussa syklissä, muodostaa itsestään vahvasti kytketyn komponentin: esimerkiksi kärkipisteen, jonka in- tai out-aste on 0, tai minkä tahansa asyklisen kuvaajan kärkipisteen.
algoritmin perusajatus on seuraava: syvyyshaku alkaa mielivaltaisesta aloitussolmusta (ja seuraavat syvyyshaut suoritetaan kaikille solmuille, joita ei ole vielä löydetty). Kuten syvyys-ensimmäisen haun yhteydessä, haku käy kaavion jokaisessa solmussa tarkalleen kerran, kieltäytymällä käymästä uudelleen jo tutkittuja solmuja. Etsintäpuiden kokoelma on siis kuvaajan ulottuva metsä. Voimakkaasti kytketyt komponentit otetaan talteen tietyinä tämän metsän osapuina. Näiden alipuiden juuria kutsutaan voimakkaasti kytkettyjen komponenttien ”juuriksi”. Mikä tahansa vahvasti yhdistetyn komponentin solmu voi toimia juurena, jos se sattuu olemaan haun löytämä komponentin ensimmäinen solmu.