Cel mai bun răspuns
O componentă puternic conectată (SCC) într-un grafic direcționat este fie un ciclu sau un vârf individual.
Aplicăm DFS pe grafic și ținem evidența a două proprietăți pentru fiecare nod din arborele DFS produs: 1. Timpul său (sau ordinea) de a fi descoperit pentru prima dată în DFS. ( spune p1) 2. Ordinea celui mai vechi strămoș pe care o poate atinge. (spune p2) Inițial ambele sunt aceleași pentru fiecare nod. În timp ce prima proprietate rămâne constantă, a doua poate fi actualizată în timpul apelurilor DFS recursive și utilizată pentru a găsi marginile din spate ale strămoșilor. Pentru orice vârf, dacă ambele sunt aceleași după apeluri DFS recursive către toate vârfurile adiacente, atunci este fie 1. Un vârf individual care nu face parte din niciun ciclu. SAU 2. Parte a unui ciclu și astfel toată descendența sa (în arborele DFS produs) o poate atinge (nu poate ajunge la strămoșii săi). Cu alte cuvinte, putem începe de la și încheia la acest nod. În al doilea caz, putem urmări tot descendentul de imprimat.
această animație ajută la înțelegerea explicației (primul număr întreg este p1, al doilea este p2):
@ Fișier: Tarjan „s Algorithm Animation.gif
Explicații detaliate și implementarea c ++: Tarjan” s Algoritm pentru a găsi componente puternic conectate – GeeksforGeeks
PS: Acest algoritm este foarte asemănător cu găsirea punctelor de articulare, a punților și a graficelor biconectate. Deci, învățarea acestora mai întâi vă poate ajuta să obțineți o intuiție mai bună pentru algoritm. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Răspuns
Algoritmul ia un grafic direcționat ca intrare și produce o partiție a vârfurilor graficului în componentele puternic conectate ale graficului. Fiecare vârf al graficului apare exact în una dintre componentele puternic conectate. Orice vârf care nu se află pe un ciclu direcționat formează o componentă puternic conectată de la sine: de exemplu, un vârf al cărui grad sau în afara este 0 sau orice vârf al unui grafic aciclic.
ideea de bază a algoritmului este următoarea: o căutare la adâncime-întâi începe de la un nod de pornire arbitrar (iar căutările ulterioare la adâncime-întâi sunt efectuate pe orice noduri care nu au fost încă găsite). Ca de obicei cu căutarea în profunzime, căutarea vizitează fiecare nod al graficului exact o dată, refuzând să revizuiască orice nod care a fost deja explorat. Astfel, colecția de copaci de căutare este o pădure care se întinde pe grafic. Componentele puternic conectate vor fi recuperate ca anumite subarburi ale acestei păduri. Rădăcinile acestor subarburi sunt numite „rădăcinile” componentelor puternic conectate. Orice nod al unei componente puternic conectate ar putea servi drept rădăcină, dacă se întâmplă să fie primul nod al componentei descoperite de căutare.