Componentă puternic conectată
O componentă puternic conectată a unui grafic direct G este un subgraf maxim al lui G în care există o cale orientată între fiecare pereche de noduri care îi aparțin.
Componentele puternic conectate formează o partiție a lui G deoarece un nod nu poate fi simultan în două componente puternic conectate, prin urmare un grafic direct este puternic conectat dacă și numai dacă are o singură componentă conectată.
Două vârfuri ale lui G sunt puternic conectate dacă și numai dacă fac parte din același ciclu orientat.
Algoritmi pentru calculul componentelor puternic conectate
Definirea problemei
Având în vedere un grafic orientat ciclic, este necesar să se identifice componentele puternic conectate și ordinea lor topologică
Algoritmul lui Tarjan
Algoritmul lui Tarjan pentru componentele puternic conectate este unul dintre cei mai eficienți algoritmi pentru căutarea structurilor puternic conectate într-un grafic. De fapt, operează cu complexitate liniară la numărul de arce și vârfuri O (| V | + | E |) .
Algoritmul Kosaraju
Algoritmul Kosaraju-Sharir constă în efectuarea unei vizite de adâncime a graficului și o vizită ulterioară de adâncime a graficului transpus , în care arcurile sunt inversate, alegând nodurile în ordinea vizitei finale obținute în timpul primei vizite de adâncime. În acest fel este posibil să se identifice componentele puternic conectate ale graficului în timp Θ (V + E) . Prin urmare, este mai simplu de implementat, dar mai puțin eficient decât algoritmii lui Tarjan și Gabow, care efectuează o singură vizită aprofundată a graficului.
Algoritmul lui Gabow
Algoritmul Cheriyan - Mehlhorn / Gabow constă în efectuarea unei singure căutări profunde pe grafic, folosind o stivă pentru a urmări vârfurile care nu au fost încă atribuite unei componente. La fel ca algoritmul lui Tarjan, o singură căutare se face în profunzime.
Bibliografie
- ( EN ) Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introducere în algoritmi , ediția a doua. MIT Press și McGraw-Hill, 2001. ISBN 0-262-03293-7 . Capitolul 22.5, pp. 552-557.
- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi și structuri de date , McGraw-Hill, 2004, ISBN 9788838661617 . Capitolul 11.5, pp. 289-293
