Beste svaret
En sterkt koblet komponent (SCC) i en rettet graf er enten en syklus eller et individuelt toppunkt.
Vi bruker DFS på grafen og holder rede på to egenskaper for hver node i produsert DFS-tre: 1. Dens tid (eller rekkefølge) for først å bli oppdaget i DFS. ( si p1) 2. Rekkefølgen til den eldste forfedren den kan nå. (si p2) Opprinnelig er begge like for hver node. Mens den første egenskapen forblir konstant, kan den andre oppdateres under rekursive DFS-samtaler og brukes til å finne bakkanter til forfedre. For ethvert toppunkt hvis begge er like etter rekursive DFS-anrop til alle de tilstøtende toppunktene, er det enten 1. Et individuelt toppunkt som ikke er en del av noen syklus. ELLER 2. En del av en syklus og slik at hele dens etterkommere (i produsert DFS-tre) kan nå den (kan ikke nå sine forfedre). Med andre ord kan vi starte fra og slutte ved denne noden. I andre tilfelle kan vi holde oversikt over alle etterkommere som skal skrives ut.
denne animasjonen hjelper til med å forstå forklaringen (første heltall er p1, andre er p2):
@ Fil: Tarjan «s Algorithm Animation.gif
Detaljert forklaring og c ++ implementering: Tarjan» s Algoritme for å finne sterkkoblede komponenter – GeeksforGeeks
PS: Denne algoritmen er veldig lik å finne artikulasjonspunkter, broer og to koblede grafer. Så å lære disse først kan hjelpe deg med å få bedre intuisjon for algoritmen. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Svar
Algoritmen tar en rettet graf som inngang, og produserer en partisjon av grafens hjørner inn i grafens sterkt sammenkoblede komponenter. Hvert toppunkt i grafen vises i nøyaktig en av de sterkt koblede komponentene. Ethvert toppunkt som ikke er på en rettet syklus, danner en sterkt koblet komponent av seg selv: for eksempel et toppunkt hvis inn- eller utgrad er 0, eller et hvilket som helst toppunkt i en asyklisk graf.
grunnleggende ideen om algoritmen er dette: et dybdesøk begynner fra en vilkårlig startnode (og påfølgende dybde-første søk utføres på noder som ennå ikke er funnet). Som vanlig med dybde-første-søk, besøker søket hver node i grafen nøyaktig en gang, og avviser å gå tilbake til en hvilken som helst node som allerede er utforsket. Dermed er samlingen av søketrær en omfattende skog i grafen. De sterkt tilkoblede komponentene vil bli gjenopprettet som visse undertrær i denne skogen. Røttene til disse undertrærne kalles «røttene» til de sterkt koblede komponentene. Enhver node av en sterkt tilkoblet komponent kan tjene som rot, hvis det tilfeldigvis er den første noden til komponenten som blir oppdaget av søket.