# Descompositor Tarjan de componentes fuertemente conexas, puentes y puntos de articulación con orden topológico Introduce una lista de aristas (a b / a -> b, con peso opcional) o adyacencia (a: b c): el algoritmo iterativo de Tarjan (1972) y el doble pase de Kosaraju descomponen las componentes fuertemente conexas con verificación cruzada; se muestran puntos de articulación y puentes, el DAG de condensación con orden topológico de Kahn, el informe de ciclos y recorridos BFS/DFS con profundidad limitada. > Página canónica: https://elysiatools.com/es/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer - **Categoría:** Development - **Palabras clave:** Tarjan, componentes fuertemente conexas, Kosaraju, puntos de articulación, puentes, condensación, orden topológico, detección de ciclos ## Descripción general Tarjan SCC se implementa de forma iterativa con pila explícita (arrays disc/low, recolección al vaciar); Kosaraju ordena por tiempo de finalización y recolecta en el grafo invertido: ambos deben coincidir componente a componente (verificación mutua). Puentes y puntos de articulación se deciden con low-link sobre la vista no dirigida: low[v] > disc[u] ⟹ puente; raíz con ≥2 subárboles o low[v] ≥ disc[u] ⟹ articulación. La condensación construye el DAG de componentes y Kahn da el orden topológico; el grafo original admite orden completo si y solo si es acíclico (los nodos en ciclos se cuentan como SCC de tamaño > 1 ∪ autoprocles). BFS por capas y DFS con pila explícita, ambos limitados por maxDepth. Complejidad O(V+E). ## Entradas - **Grafo (lista de aristas o adyacencia, una por línea)** (textarea): a -> b b -> c c -> a d -> c - **Grafo dirigido** (checkbox) - **Nodo inicial** (text): a - **Profundidad máxima** (number): 4 ## Cuándo usarlo - Al auditar dependencias de módulos de software para identificar ciclos y determinar el orden óptimo de compilación o inicialización. - Para evaluar la resiliencia de redes detectando enlaces críticos (puentes) y nodos de fallo único (puntos de articulación). - Cuando se necesita transformar un grafo cíclico en su DAG condensado y calcular una ordenación topológica válida. ## Cómo funciona - Parsea listas de aristas (`a -> b`, `a b`) o listas de adyacencia (`a: b c`) según la orientación definida. - Ejecuta de manera iterativa los algoritmos de Tarjan y Kosaraju para clasificar los componentes fuertemente conexos y validar la coincidencia mutua. - Calcula los tiempos de descubrimiento y valores low-link en la vista no dirigida para reportar puentes y puntos de articulación. - Construye el DAG de condensación, aplica el algoritmo de Kahn para el orden topológico y procesa recorridos BFS/DFS acotados por la profundidad máxima. ## Casos de uso - Detección y resolución de dependencias circulares en sistemas de paquetes y arquitecturas de microservicios. - Evaluación de redundancia y puntos críticos de corte en topologías de telecomunicaciones. - Pruebas y verificación académica de algoritmos fundamentales de teoría de grafos. ## Preguntas frecuentes ### ¿Por qué se ejecutan conjuntamente Tarjan y Kosaraju? Ambos algoritmos resuelven componentes fuertemente conexas con estrategias distintas y su ejecución paralela permite verificar la exactitud del resultado. ### ¿Qué formatos de entrada admite la herramienta? Acepta pares de nodos (`a b`), flechas dirigidas (`a -> b`, con peso opcional) y listas de adyacencia (`a: b c`), uno por línea. ### ¿Cómo se detectan los puentes y puntos de articulación? Se analizan en la representación no dirigida evaluando si el valor de retorno (low-link) de un subárbol no puede alcanzar a los ancestros del nodo evaluado. ### ¿Es posible obtener un orden topológico en grafos con ciclos? El grafo original no admitirá orden topológico completo si contiene ciclos, pero la herramienta genera el orden topológico sobre el DAG de condensación resultante. ### ¿Qué efecto tiene el parámetro de profundidad máxima? Restringe la cantidad de niveles explorados durante los recorridos BFS por capas y DFS por pila a partir del nodo inicial indicado. ## Herramientas relacionadas - [Visualizador de Expresiones Cron](https://elysiatools.com/es/tools/cron-expression-visualizer): Analiza horarios cron, valida sintaxis cron estandar o Quartz y visualiza las proximas ejecuciones en una linea de tiempo y calendario agrupado - [Sincronizador de paleta Tailwind](https://elysiatools.com/es/tools/tailwind-color-palette-sync): Introduce HEX, elige esquema de nombres (escala 50–950 / nombre único / anidamiento) y genera el fragmento theme.extend.colors de tailwind.config.ts con niveles WCAG AA/AAA por color. Modo oscuro opcional. - [Explicador de Expresiones Cron](https://elysiatools.com/es/tools/cron-expression-explainer): Analiza una expresión cron de 5/6 campos o Quartz en una descripción en lenguaje natural, desglosa los campos y lista las próximas N ejecuciones en cualquier zona IANA, con una explicación natural generada por IA - [Simulador de trabajos cron](https://elysiatools.com/es/tools/cron-job-simulator): Simula una o dos expresiones cron de 5 partes, resalta solapamientos y alerta sobre programaciones densas. - [Probador de mutacion de contrato API](https://elysiatools.com/es/tools/api-contract-mutation-tester): Aplica mutaciones semanticas a campos OpenAPI y opcionalmente las envia al backend real para medir su validacion defensiva - [Cirujano de filas CSV malformadas](https://elysiatools.com/es/tools/csv-malformed-row-surgeon): Repara quirúrgicamente filas CSV malformadas una a una: comillas no escapadas (sueltas), delimitadores mixtos (tabulador/punto y coma/coma en el mismo archivo), encabezados con BOM, finales de línea CRLF/CR y líneas vacías finales. El cirujano analiza de forma tolerante, muestra un diff rojo/verde fila por fila de cada cambio realizado (antes → después, con la razón de la reparación etiquetada), lista las filas aceptadas sin cambios y emite el CSV limpio. La reparación opcional con IA puede revisar las filas sospechosas después de la pasada determinista. Complementa al Validador CSV (que solo reporta problemas) reparando realmente las filas dañadas. - [Visualizador del flujo OAuth 2.0 / OIDC con código de autorización y PKCE](https://elysiatools.com/es/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Simula de extremo a extremo el flujo de código de autorización con PKCE: generación de verifier/challenge, URL de autorización, intercambio de tokens, lista de validación del ID Token y demostración de ataque de interceptación. - [Constructor de art direction responsive Picture / srcset](https://elysiatools.com/es/tools/responsive-picture-srcset-art-direction-builder): Genera marcado completo con recortes art-directed: elementos por breakpoint, candidatas 1x/2x o descriptores de ancho con plantilla {w}, capas AVIF/WebP opcionales, manejo de sizes, width/height anti-CLS, y sabores HTML y JSX con notas de lint basadas en la especificación. ## Ejemplos - [Muestras FLAC Sin Derechos de Autor](https://elysiatools.com/es/samples/flac-samples): Colección de audio FLAC sin pérdidas para pruebas y desarrollo, incluyendo sonidos de la naturaleza y música de meditación - [Muestras WAV Sin Derechos de Autor](https://elysiatools.com/es/samples/wav-samples): Colección de audio WAV sin compresión para pruebas y desarrollo, incluyendo sonidos de la naturaleza y música de meditación - [Ejemplos de Procesamiento de Imágenes Android Java](https://elysiatools.com/es/samples/android-image-processing-java): Ejemplos de procesamiento de imágenes Android Java incluyendo lectura/escritura, escalado y conversión de formato - [Ejemplos de Procesamiento de Imágenes Android Kotlin](https://elysiatools.com/es/samples/android-image-processing-kotlin): Ejemplos de procesamiento de imágenes Android Kotlin incluyendo lectura/escritura, escalado y conversión de formato