Comment lancer une requête 01 Chargez un graphe. Le préréglage DAG est un graphe orienté acyclique à 7 nœuds ; le préréglage Bridge a un triangle non orienté plus une chaîne ; le préréglage Cycle C₅ plus le commutateur Directed forme un seul anneau orienté. 02 Choisissez un algorithme dans l'onglet Order & connectivity. Topological sort refuse d'emblée les graphes non orientés et explique pourquoi. 03 Lisez les lignes. Topological sort imprime l'ordre, le nombre de couches et une ligne par couche ; les algorithmes de connectivité impriment des listes de composantes, des sommets d'articulation, des ponts ou un nombre de composantes d'arêtes. 04 Suivez le parcours. Topological sort avance par degrés entrants et retraits ; Cycle detection surligne l'arête de fermeture dans le canevas.
Relevés calculés
Graphe · algorithme
Relevé
Préréglage DAG · Topological sort
ordre A → B → C → D → E → F → G ; couches 5 — L1 A , L2 B, C , L3 D , L4 E, F , L5 G
Préréglage Bridge · Cut vertices & bridges
sommets d'articulation B, D, E ; ponts D–E, B–D ; composantes d'arêtes 3 — A, B, C · D · E, F, G
Cycle C₅ + Directed · Strongly connected
nombre de composantes 1 , contenant E, D, C, B, A
Préréglage DAG · Strongly connected
nombre de composantes 7 , un singleton par nœud
Graphe par défaut · Cycle detection
cycle présent Yes ; cycle A → B → C → A ; raison Back edge C – A
Préréglage DAG · Cycle detection
cycle présent No ; raison No back edge ⇒ directed acyclic graph
Les couches du DAG sont un plan d'ordonnancement : A d'abord, puis B et C dans n'importe quel ordre, puis D, puis E et F, puis G. Le préréglage Bridge montre pourquoi un seul pont peut scinder le graphe en trois : B–D et D–E sont les seules liaisons entre le triangle A–B–C, le nœud isolé D et le triangle E–F–G.
Pourquoi la bascule change la réponse Le graphe par défaut contient le triangle A–B–C, et Cycle detection signale A → B → C → A avec la raison Back edge C – A . Activez Directed et les trois mêmes arêtes ne pointent plus que vers l'avant (A→B, B→C, A→C) : le détecteur répond désormais No , raison No back edge ⇒ directed acyclic graph , et Topological sort — qui renvoyait auparavant "Topological sort is defined for directed graphs only — switch the graph to directed first" — réussit avec l'ordre A → B → C → D → E → F en 6 couches. Une bascule, deux verdicts opposés ; le sens des arêtes est toute la question.
Limites
Topological sort est réservé aux graphes orientés. Il refuse l'entrée non orientée plutôt que de deviner une orientation. La connexité forte est définie pour les graphes orientés elle aussi ; sur un graphe non orienté, Components du même panneau répond à la question d'atteignabilité. Les ponts relèvent de la connexité 2-arêtes, pas de la n-connexité. Le panneau signale les sommets d'articulation, les ponts et le nombre de groupes 2-connexes par arêtes ; il ne calcule ni la connexité de sommets, ni les coupes minimales, ni la planarité — les coupes minimales vivent dans Flow & matching , les comptages structurels dans Metrics & centrality .
Ce qu'il ne fait pas. Il n'ordonnance pas de tâches pondérées, ne colore pas de graphes et ne produit pas plusieurs ordres topologiques ; le canevas montre un ordre valide, et modifier les arêtes est le moyen d'en explorer d'autres.
Où cela sert Ordre de build et de dépendances Le préréglage DAG se lit comme un petit plan de build ; les lignes de couches indiquent ce qui peut tourner en parallèle (B, C , puis E, F ) et ce qui est sérialisé derrière (D , puis G ). Si une nouvelle dépendance ferme une boucle, Cycle detection nomme l'arête de retour au lieu de renvoyer un ordre cassé.
Revue de fragilité Sur le préréglage Bridge, perdre B–D ou D–E déconnecte trois groupes, et le nœud isolé D devient inatteignable. Lancez Components sur un graphe avec un nœud isolé pour voir l'autre mode de défaillance : construisez le graphe par défaut, ajoutez un nœud, et le nombre de composantes lit 2 avec la plus grande composante à 6 — le panneau Traversal liste le même nœud comme inatteignable depuis A.
Confidentialité Tout le travail d'ordre et de connectivité s'exécute dans votre navigateur ; le graphe ne quitte jamais la page.
Références
Wikipedia, Topological sorting , en.wikipedia.org (访问日期:2026-10-07)— ordres de DAG et découpage en couches.
Wikipedia, Strongly connected component , en.wikipedia.org (访问日期:2026-10-07)— atteignabilité mutuelle dans les graphes orientés.
Wikipedia, Biconnected component , en.wikipedia.org (访问日期:2026-10-07)— sommets d'articulation, ponts et composantes d'arêtes.
Wikipedia, Cycle detection , en.wikipedia.org (访问日期:2026-10-07)— arêtes de retour comme témoins de cycle.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07