Jaké dobré vysvětlení pro Tarjanův algoritmus silně propojených komponent?


Nejlepší odpověď

Silně připojená komponenta (SCC) v orientovaném grafu je buď cyklus nebo jednotlivý vrchol.

Aplikujeme DFS na graf a sledujeme dvě vlastnosti pro každý uzel ve vytvořeném stromu DFS: 1. Jeho čas (nebo pořadí) prvního objevení v DFS. ( řekněme p1) 2. Pořadí nejstaršího předka, kterého může dosáhnout. (řekněme p2) Zpočátku jsou oba stejné pro každý uzel. Zatímco první vlastnost zůstává konstantní, druhá může být aktualizována během rekurzivních volání DFS a použita k hledání zpětných hran předků. Pro libovolný vrchol, pokud jsou oba stejné po rekurzivních voláních DFS na všechny jeho sousední vrcholy, je to buď 1. Individuální vrchol, který není součástí žádného cyklu. NEBO 2. Část cyklu, a tak se k němu může dostat všechen jeho potomek (ve vytvořeném stromu DFS) (nemůže dosáhnout ke svým předkům). Jinými slovy můžeme v tomto uzlu začínat a končit. Ve druhém případě můžeme sledovat všechny potomky, které se mají tisknout.

Tato animace pomáhá porozumět vysvětlení (první celé číslo je p1, druhé je p2):

@ Soubor: Tarjanův algoritmus Animation.gif

Podrobné vysvětlení a implementace v jazyce C ++: Tarjan Algoritmus pro vyhledání silně propojených komponent – GeeksforGeeks

PS: Tento algoritmus je velmi podobný hledání artikulačních bodů, mostů a biconnected grafů. Pokud se tedy naučíte první, pomůže vám to získat lepší intuici algoritmu. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/

Odpověď

Algoritmus převezme jako vstup směrovaný graf a vytvoří rozdělení vrcholů grafu do silně propojených komponent grafu. Každý vrchol grafu se objevuje přesně v jedné ze silně propojených komponent. Jakýkoli vrchol, který není v řízeném cyklu, tvoří sám o sobě silně spojenou součást: například vrchol, jehož vnitřní nebo vnější stupeň je 0, nebo jakýkoli vrchol acyklického grafu.

základní myšlenka algoritmu je tato: vyhledávání od hloubky začíná od libovolného počátečního uzlu (a následné hloubkové prohledávání se provádí u všech uzlů, které dosud nebyly nalezeny). Jak je obvyklé u hloubkového vyhledávání, navštíví vyhledávání každý uzel grafu přesně jednou a odmítne znovu navštívit jakýkoli uzel, který již byl prozkoumán. Sbírka vyhledávacích stromů je tedy překlenujícím lesem grafu. Silně propojené komponenty budou obnoveny jako určité podstromy tohoto lesa. Kořeny těchto podstromů se nazývají „kořeny“ silně propojených komponent. Jakýkoli uzel silně propojené komponenty může sloužit jako kořenový adresář, pokud se stane prvním uzlem komponenty, který je objeven vyhledáváním.

Tarjanův algoritmus silně propojených komponentů

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *