Melhor resposta
Um componente fortemente conectado (SCC) em um gráfico direcionado é um ciclo ou um vértice individual.
Nós aplicamos o DFS no gráfico e monitoramos duas propriedades para cada nó na árvore DFS produzida: 1. Seu tempo (ou ordem) de primeiro ser descoberto no DFS. ( diga p1) 2. A ordem do ancestral mais antigo que ele pode alcançar. (diga p2) Inicialmente, ambos são iguais para todos os nós. Enquanto a 1ª propriedade permanece constante, a 2ª pode ser atualizada durante chamadas DFS recursivas e usada para encontrar as bordas posteriores dos ancestrais. Para qualquer vértice, se ambos forem iguais após chamadas DFS recursivas para todos os seus vértices adjacentes, então será 1. Um vértice individual que não faz parte de nenhum ciclo. OU 2. Parte de um ciclo e assim todos os seus descendentes (na árvore DFS produzida) podem alcançá-lo (não pode alcançar seus ancestrais). Em outras palavras, podemos começar e terminar neste nó. No segundo caso, podemos rastrear todos os descendentes para imprimir.
esta animação ajuda a entender a explicação (o primeiro inteiro é p1, o segundo é p2):
@ Arquivo: Tarjan “s Algorithm Animation.gif
Explicação detalhada e implementação de c ++: Tarjan” s Algoritmo para encontrar componentes fortemente conectados – GeeksforGeeks
PS: Este algoritmo é muito semelhante a encontrar pontos de articulação, pontes e gráficos bicconectados. Portanto, aprendê-los primeiro pode ajudá-lo a obter uma melhor intuição para o algoritmo. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ http://www.geeksforgeeks.org/bridge-in-a-graph/
Resposta
O algoritmo pega um gráfico direcionado como entrada e produz uma partição dos vértices do gráfico nos componentes fortemente conectados do gráfico. Cada vértice do gráfico aparece exatamente em um dos componentes fortemente conectados. Qualquer vértice que não esteja em um ciclo direcionado forma um componente fortemente conectado por si só: por exemplo, um vértice cujo grau de entrada ou saída é 0, ou qualquer vértice de um gráfico acíclico.
O A ideia básica do algoritmo é esta: uma pesquisa em profundidade começa a partir de um nó inicial arbitrário (e pesquisas subsequentes em profundidade são conduzidas em quaisquer nós que ainda não foram encontrados). Como de costume com a pesquisa em primeiro lugar, a pesquisa visita cada nó do gráfico exatamente uma vez, recusando-se a revisitar qualquer nó que já tenha sido explorado. Portanto, a coleção de árvores de pesquisa é uma floresta abrangente do gráfico. Os componentes fortemente conectados serão recuperados como certas subárvores desta floresta. As raízes dessas subárvores são chamadas de “raízes” dos componentes fortemente conectados. Qualquer nó de um componente fortemente conectado pode servir como raiz, se acontecer de ser o primeiro nó do componente descoberto pela pesquisa.