Bästa svaret
En starkt ansluten komponent (SCC) i en riktad graf är antingen en cykel eller en enskild toppunkt.
Vi tillämpar DFS på grafen och håller reda på två egenskaper för varje nod i DFS-träd som produceras: 1. Dess tid (eller ordning) för att först upptäckas i DFS. ( säg p1) 2. Ordningen på äldsta förfader som den kan nå. (säg p2) Initialt är båda lika för varje nod. Medan den första egenskapen förblir konstant, kan den andra uppdateras under rekursiva DFS-samtal och användas för att hitta bakre kanter till förfäder. För varje toppunkt om båda är desamma efter rekursivt DFS-samtal till alla dess intilliggande hörn är det antingen 1. Ett enskilt toppunkt som inte ingår i någon cykel. ELLER 2. En del av en cykel och så kan alla dess ättlingar (i DFS-träd produceras) nå den (kan inte nå sina förfäder). Med andra ord kan vi börja från och sluta vid denna nod. I det andra fallet kan vi hålla reda på alla nedstammande att skriva ut.
denna animation hjälper till att förstå förklaringen (första heltal är p1, andra är p2):
@ Fil: Tarjan ”s Algorithm Animation.gif
Detaljerad förklaring och c ++ implementering: Tarjan” s Algoritm för att hitta starkt anslutna komponenter – GeeksforGeeks
PS: Denna algoritm liknar mycket att hitta artikulationspunkter, broar och tvåanslutna diagram. Så att lära dig dessa först kan hjälpa dig att få bättre intuition för 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 riktad graf som inmatning och producerar en partition av grafens hörn i grafens starkt anslutna komponenter. Varje toppunkt i diagrammet visas i exakt en av de starkt anslutna komponenterna. Varje toppunkt som inte är på en riktad cykel bildar en starkt ansluten komponent helt av sig själv: till exempel ett toppunkt vars in- eller utgrad är 0 eller någon toppunkt i en acyklisk graf.
Grundidén med algoritmen är denna: en djup-första-sökning börjar från en godtycklig startnod (och efterföljande djup-första-sökningar utförs på alla noder som ännu inte hittats). Som vanligt med djup-först-sökning besöker sökningen varje nod i diagrammet exakt en gång, och avböjer att återgå till alla noder som redan har undersökts. Således är samlingen av sökträd en omfattande skog i diagrammet. De starkt anslutna komponenterna kommer att återvinnas som vissa underträd i denna skog. Rötterna till dessa underträd kallas ”rötterna” för de starkt anslutna komponenterna. Vilken nod som helst av en starkt ansluten komponent kan fungera som rot om det råkar vara den första noden för komponenten som upptäcks av sökningen.