# Décomposeur Tarjan de composantes fortement connexes, ponts et points d'articulation avec ordre topologique Saisissez une liste d'arêtes (a b / a -> b, poids facultatif) ou une adjacence (a: b c) : l'algorithme itératif de Tarjan (1972) et le double passage de Kosaraju décomposent les composantes fortement connexes avec contre-vérification ; sortie : points d'articulation et ponts, DAG de condensation avec ordre topologique de Kahn, rapport de cycles et parcours BFS/DFS à profondeur limitée. > Page canonique: https://elysiatools.com/fr/tools/tarjan-scc-tarjan-bridge-and-strongly-connected-components-topological-order-graph-decomposer - **Catégorie:** Development - **Mots-clés:** Tarjan, composantes fortement connexes, Kosaraju, points d'articulation, ponts, condensation, tri topologique, détection de cycles ## Présentation Le SCC de Tarjan est itératif à pile explicite (tableaux disc/low, collecte au dépilage) ; Kosaraju trie par temps de fin puis collecte sur le graphe inversé — les deux doivent concorder composante par composante (contre-vérification). Ponts et points d'articulation suivent le low-link sur la vue non orientée : low[v] > disc[u] ⟹ pont ; racine à ≥2 sous-arbres ou low[v] ≥ disc[u] ⟹ articulation. La condensation construit le DAG des composantes, Kahn donne l'ordre topologique ; un ordre complet existe ssi le graphe est acyclique (nœuds sur cycles = SCC de taille > 1 ∪ boucles). BFS par couches et DFS à pile explicite, bornés par maxDepth. Complexité O(V+E). ## Entrées - **Graphe (liste d'arêtes ou adjacence, une par ligne)** (textarea): a -> b b -> c c -> a d -> c - **Graphe orienté** (checkbox) - **Nœud de départ** (text): a - **Profondeur maximale** (number): 4 ## Quand l'utiliser - Pour identifier des dépendances circulaires dans un projet logiciel ou un ordonnanceur de tâches. - Pour repérer les points de défaillance uniques (ponts et points d'articulation) dans une topologie de réseau. - Pour obtenir l'ordre topologique d'exécution d'un DAG ou après la condensation des cycles d'un graphe orienté. ## Fonctionnement - Saisissez la topologie du graphe sous forme de liste d'arêtes (`a -> b`, `a b`) ou de liste d'adjacence (`a: b c`), puis définissez si le graphe est orienté ou non. - L'outil exécute simultanément l'algorithme itératif de Tarjan et celui de Kosaraju pour valider par double vérification la décomposition en composantes fortement connexes. - L'analyse low-link calcule les ponts et points d'articulation sur la vue non orientée, tandis que l'algorithme de Kahn ordonne les composantes du DAG de condensation. - Le rapport affiche la liste des CFC, l'état des cycles, l'ordre topologique calculé et le détail des parcours BFS/DFS selon le nœud de départ et la profondeur maximale configurés. ## Cas d'usage - Analyse de robustesse d'infrastructure réseau pour repérer les liens critiques isolant un sous-réseau en cas de panne. - Résolution de graphes de compilation ou d'ordonnancement de tâches pour séquencer l'exécution et isoler les boucles de dépendance. - Étude académique et vérification d'algorithmes de théorie des graphes (Tarjan, Kosaraju, Kahn, BFS/DFS). ## Questions fréquentes ### Quels formats d'entrée de graphe sont acceptés ? Vous pouvez saisir des listes d'arêtes avec flèches (`a -> b`), avec espaces (`a b`, avec poids optionnel) ou des listes d'adjacence (`a: b c`), à raison d'une entrée par ligne. ### Pourquoi exécuter à la fois Tarjan et Kosaraju ? L'outil effectue une contre-vérification automatique : les composantes fortement connexes obtenues par Tarjan sont confrontées à celles de Kosaraju pour garantir l'exactitude du résultat. ### Comment sont identifiés les ponts et points d'articulation ? Ils sont déterminés sur la vue non orientée du graphe via les valeurs de découverte et de low-link calculées lors du parcours DFS. ### Quand un ordre topologique complet est-il possible sur le graphe d'origine ? Un ordre complet n'est possible que si le graphe est strictement acyclique (aucun cycle ni boucle) ; sinon, l'ordre topologique s'applique au DAG de condensation. ### À quoi servent les paramètres 'Nœud de départ' et 'Profondeur maximale' ? Ils définissent l'origine et la limite d'exploration pour générer les parcours BFS par couches et DFS à pile explicite. ## Outils associés - [Visualiseur d Expressions Cron](https://elysiatools.com/fr/tools/cron-expression-visualizer): Analyse des plannings cron, valide la syntaxe cron standard ou Quartz et visualise les prochaines executions sur une chronologie et un calendrier groupe - [Sync de palette Tailwind](https://elysiatools.com/fr/tools/tailwind-color-palette-sync): Entrez des HEX, choisissez le schéma de noms (échelle 50–950 / nom unique / imbrication) et générez le fragment theme.extend.colors de tailwind.config.ts avec les niveaux WCAG AA/AAA. Dark mode optionnel. - [Explorateur d’Expressions Cron](https://elysiatools.com/fr/tools/cron-expression-explainer): Analyse une expression cron (5/6 champs ou Quartz) en description en langage naturel, détaille les champs et liste les N prochaines exécutions dans tout fuseau IANA, avec une explication IA - [Simulateur de taches cron](https://elysiatools.com/fr/tools/cron-job-simulator): Simule les prochaines executions dun ou deux cron a 5 champs, met en evidence les chevauchements et les frequences trop denses. - [Testeur de mutation de contrat API](https://elysiatools.com/fr/tools/api-contract-mutation-tester): Applique des mutations semantiques aux champs OpenAPI et peut les envoyer a un backend reel pour mesurer la validation defensive - [Chirurgien des lignes CSV malformées](https://elysiatools.com/fr/tools/csv-malformed-row-surgeon): Répare chirurgicalement les lignes CSV malformées une à une : guillemets non échappés (parasites), délimiteurs mixtes (tabulation/point-virgule/virgule dans le même fichier), en-têtes préfixés par un BOM, fins de ligne CRLF/CR et lignes vides. Le chirurgien analyse toléramment, affiche un diff rouge/vert ligne par ligne de chaque changement effectué (avant → après, avec la raison de la réparation étiquetée), liste les lignes acceptées sans changement et émet le CSV nettoyé. La réparation IA optionnelle peut relire les lignes suspectes après le passage déterministe. Il complète le Validateur CSV (qui ne fait que signaler) en réparant réellement les lignes endommagées. - [Visualiseur du flux OAuth 2.0 / OIDC à code d’autorisation avec PKCE](https://elysiatools.com/fr/tools/oauth-oidc-authorization-code-pkce-flow-visualizer): Simule de bout en bout le flux à code d’autorisation avec PKCE : génération verifier/challenge, URL d’autorisation, échange de token, liste de validation de l’ID Token et démonstration d’attaque par interception. - [Constructeur d'art direction responsive Picture / srcset](https://elysiatools.com/fr/tools/responsive-picture-srcset-art-direction-builder): Génère un balisage complet avec recadrages art direction : éléments par point d'arrêt, candidates 1x/2x ou descripteurs de largeur par modèle {w}, couches AVIF/WebP optionnelles, gestion de sizes, width/height anti-CLS, et déclinaisons HTML et JSX avec notes de lint fondées sur la spécification. ## Exemples - [Échantillons Audio FLAC Libres de Droits](https://elysiatools.com/fr/samples/flac-samples): Collection audio FLAC sans perte pour tests et développement, incluant sons de la nature et musique de méditation - [Échantillons Audio WAV Libres de Droits](https://elysiatools.com/fr/samples/wav-samples): Collection audio WAV non compressé pour tests et développement, incluant sons de la nature et musique de méditation - [Exemples de Traitement d'Images Android Java](https://elysiatools.com/fr/samples/android-image-processing-java): Exemples de traitement d'images Android Java incluant lecture/écriture, mise à l'échelle et conversion de format - [Exemples de Traitement d'Images Android Kotlin](https://elysiatools.com/fr/samples/android-image-processing-kotlin): Exemples de traitement d'images Android Kotlin incluant lecture/écriture, mise à l'échelle et conversion de format