# Decompositor Tarjan de componentes fortemente conexas, pontes e pontos de articulação com ordem topológica Informe uma lista de arestas (a b / a -> b, com peso opcional) ou adjacência (a: b c): o algoritmo iterativo de Tarjan (1972) e o passe duplo de Kosaraju decompõem as componentes fortemente conexas com verificação cruzada; saída: pontos de articulação e pontes, DAG de condensação com ordem topológica de Kahn, relatório de ciclos e travessias BFS/DFS com profundidade limitada. > Página canônica: https://elysiatools.com/pt/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer - **Categoria:** Development - **Palavras-chave:** Tarjan, componentes fortemente conexas, Kosaraju, pontos de articulação, pontes, condensação, ordenação topológica, detecção de ciclos ## Visão geral O SCC de Tarjan é iterativo com pilha explícita (arrays disc/low, coleta ao desempilhar); Kosaraju ordena por tempo de término e coleta no grafo invertido — ambos devem coincidir componente a componente (verificação mútua). Pontes e pontos de articulação seguem o low-link na vista não dirigida: low[v] > disc[u] ⟹ ponte; raiz com ≥2 subárvores ou low[v] ≥ disc[u] ⟹ articulação. A condensação constrói o DAG de componentes, Kahn dá a ordem topológica; ordem completa existe se e só se acíclico (nós em ciclos = SCC de tamanho > 1 ∪ autolaços). BFS por camadas e DFS com pilha explícita, limitados por maxDepth. Complexidade O(V+E). ## Entradas - **Grafo (lista de arestas ou adjacência, uma por linha)** (textarea): a -> b b -> c c -> a d -> c - **Grafo dirigido** (checkbox) - **Nó inicial** (text): a - **Profundidade máxima** (number): 4 ## Quando usar - Identificar ciclos e componentes fortemente conexas em grafos de dependências de módulos ou pacotes. - Localizar pontos únicos de falha e conexões críticas (pontos de articulação e pontes) em topologias de rede. - Obter a ordem topológica de execução e escalonamento a partir do DAG condensado de componentes. ## Como funciona - Insira as arestas (como 'a -> b' ou 'a b') ou listas de adjacência ('a: b c') e configure o direcionamento, nó inicial e limite de profundidade. - O motor executa a análise iterativa de Tarjan e a verificação cruzada com Kosaraju para encontrar CFCs, pontes e pontos de articulação via cálculo de low-link. - A ferramenta gera a condensação em DAG, calcula a ordem topológica de Kahn, quantifica nós em ciclos e traça as travessias BFS e DFS limitadas por profundidade. ## Casos de uso - Detecção e resolução de dependências circulares em arquiteturas de microsserviços e bibliotecas de código. - Mapeamento de vulnerabilidades estruturais e redundâncias em infraestruturas de rede e transporte. - Planejamento de fluxo de tarefas e etapas de compilação ordenadas por dependência em pipelines de software. ## Perguntas frequentes ### Como é feita a validação das componentes fortemente conexas? O sistema executa o algoritmo de Tarjan e o método de Kosaraju em duas etapas, comparando os resultados componente a componente para garantir consistência. ### Qual é a diferença entre ponto de articulação e ponte? Uma ponte é uma aresta cuja desconexão divide o grafo, enquanto um ponto de articulação é um vértice cuja remoção desconecta o grafo. ### O grafo precisa ser acíclico para obter a ordenação topológica? O grafo original só possui ordem topológica completa se for acíclico, mas o DAG de condensação de componentes sempre produz uma ordenação topológica via Kahn. ### Quais formatos de entrada de texto são suportados? São suportadas listas de arestas com flecha ('a -> b'), pares simples ('a b', com peso opcional) e listas de adjacência ('a: b c'), uma por linha. ### O que faz o parâmetro de profundidade máxima? Ele limita o número de níveis explorados a partir do nó inicial nas travessias BFS por camadas e DFS com pilha explícita. ## Ferramentas relacionadas - [Visualizador de Expressoes Cron](https://elysiatools.com/pt/tools/cron-expression-visualizer): Analisa agendamentos cron, valida sintaxe cron padrao ou Quartz e visualiza as proximas execucoes em uma linha do tempo e calendario agrupado - [Sincronizador de paleta Tailwind](https://elysiatools.com/pt/tools/tailwind-color-palette-sync): Insira HEX, escolha o esquema de nomes (escala 50–950 / nome único / aninhamento) e gere o fragmento theme.extend.colors do tailwind.config.ts com níveis WCAG AA/AAA. Dark mode opcional. - [Explicador de Expressões Cron](https://elysiatools.com/pt/tools/cron-expression-explainer): Analisa uma expressão cron (5/6 campos ou Quartz) em uma descrição em linguagem natural, detalha os campos e lista as próximas N execuções em qualquer zona IANA, com explicação por IA - [Simulador de jobs cron](https://elysiatools.com/pt/tools/cron-job-simulator): Simula as proximas execucoes de uma ou duas expressoes cron de 5 partes, destacando sobreposicoes e agendamentos densos. - [Testador de mutacao de contrato API](https://elysiatools.com/pt/tools/api-contract-mutation-tester): Aplica mutacoes semanticas a campos OpenAPI e opcionalmente as envia para o backend real para medir a validacao defensiva - [Cirurgião de linhas CSV malformadas](https://elysiatools.com/pt/tools/csv-malformed-row-surgeon): Repara cirurgicamente linhas CSV malformadas uma a uma: aspas não escapadas (perdidas), delimitadores mistos (tabulação/ponto e vírgula/vírgula no mesmo arquivo), cabeçalhos com BOM, finais de linha CRLF/CR e linhas vazias. O cirurgião analisa de forma tolerante, mostra um diff vermelho/verde linha por linha de cada mudança feita (antes → depois, com o motivo do reparo marcado), lista as linhas aceitas sem alteração e emite o CSV limpo. O reparo opcional por IA pode revisar linhas suspeitas após a etapa determinística. Complementa o Validador CSV (que apenas relata problemas) reparando de fato as linhas danificadas. - [Visualizador do fluxo OAuth 2.0 / OIDC com código de autorização e PKCE](https://elysiatools.com/pt/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Simula de ponta a ponta o fluxo de código de autorização com PKCE: geração de verifier/challenge, URL de autorização, troca de token, checklist de validação do ID Token e demonstração de ataque de interceptação. - [Construtor de art direction responsiva Picture / srcset](https://elysiatools.com/pt/tools/responsive-picture-srcset-art-direction-builder): Gera marcação completa com recortes de art direction: elementos por breakpoint, candidatas 1x/2x ou descritores de largura por modelo {w}, camadas AVIF/WebP opcionais, tratamento de sizes, width/height anti-CLS e sabores HTML e JSX com notas de lint baseadas na especificação. ## Exemplos - [Amostras de Áudio FLAC Livres de Direitos Autorais](https://elysiatools.com/pt/samples/flac-samples): Coleção de áudio FLAC sem perdas para testes e desenvolvimento, incluindo sons da natureza e música de meditação - [Amostras de Áudio WAV Livres de Direitos Autorais](https://elysiatools.com/pt/samples/wav-samples): Coleção de áudio WAV sem compressão para testes e desenvolvimento, incluindo sons da natureza e música de meditação - [Exemplos de Processamento de Imagem Android Java](https://elysiatools.com/pt/samples/android-image-processing-java): Exemplos de processamento de imagem Android Java incluindo leitura/escrita, dimensionamento e conversão de formato - [Exemplos de Processamento de Imagem Android Kotlin](https://elysiatools.com/pt/samples/android-image-processing-kotlin): Exemplos de processamento de imagem Android Kotlin incluindo leitura/escrita, dimensionamento e conversão de formato