Legjobb válasz
Az irányított gráfban erősen összekapcsolt komponens (SCC) vagy egy ciklus vagy egy egyedi csúcs.
DFS-t alkalmazunk a grafikonon, és két tulajdonságot követünk az előállított DFS-fa minden egyes csomópontjánál: 1. Időjét (vagy sorrendjét) először fedezték fel a DFS-ben. mondjuk p1) 2. A legrégebbi ősök sorrendje, amelyet elérhet. (mondjuk p2) Kezdetben mindkettő minden csomópontnál megegyezik. Míg az 1. tulajdonság állandó marad, a második a rekurzív DFS-hívások során frissíthető, és felhasználható az ősök hátsó éleinek felkutatására. Bármely csúcs esetén, ha a rekurzív DFS minden szomszédos csúcsára hívás után mindkettő megegyezik, akkor ez vagy 1. Egyetlen csúcs, amely nem része egyetlen ciklusnak sem. VAGY 2. A ciklus egy része, és így leszármazottja (az előállított DFS-fában) el tudja érni (nem érheti el őseit). Más szavakkal, ebből a csomópontból indulhatunk ki és véget is érhetünk. 2. esetben nyomon követhetjük az összes leszármazottat, amelyet kinyomtatunk.
Ez az animáció segít megérteni a magyarázatot (az első egész szám p1, a második p2):
@ Fájl: Tarjan algoritmusa Animation.gif
Részletes magyarázat és c ++ megvalósítás: Tarjan “s Algoritmus az erősen összekapcsolt alkatrészek megkeresésére – GeeksforGeeks
PS: Ez az algoritmus nagyon hasonlít az artikulációs pontok, hidak és két összekapcsolt grafikonok megtalálásához. Tehát ezek első megtanulása segíthet abban, hogy jobb intuíciót kapjon az algoritmushoz. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Válasz
Az algoritmus egy irányított gráfot vesz bemenetként, és a grafikon csúcsainak partícióját hozza létre a gráf erősen összekapcsolt komponenseihez. A grafikon minden csúcsa pontosan az egyik erősen összekapcsolt komponensben jelenik meg. Bármely csúcs, amely nem egy irányított cikluson van, önmagában erősen összekapcsolt komponenst alkot: például egy csúcsot, amelynek in- vagy out-foka 0, vagy egy aciklusos gráf bármely csúcsát.
A Az algoritmus alapgondolata a következő: a mélység-első keresés egy tetszőleges kezdő csomópontból indul (és az ezt követő mélység-első kereséseket minden olyan csomóponton elvégzik, amelyet még nem találtak meg). A mélység-első kereséshez hasonlóan a keresés a grafikon minden csomópontját pontosan egyszer keresi fel, elutasítva a már feltárt csomópontok újbóli felkeresését. Így a kereső fák gyűjteménye a grafikon átívelő erdője. Az erősen összekapcsolt alkotóelemek az erdő bizonyos részfáiként kerülnek helyre. Ezeknek az alfáknak a gyökereit az erősen összekapcsolt alkotóelemek “gyökereinek” nevezzük. Bármely erősen összekapcsolt összetevő csomópontja szolgálhat gyökérként, ha véletlenül ez az első csomópontja a keresésnek.