Algorithm for finding strongly connected components using DFS

What is the time complexity of Tarjan SCC?

The time complexity of Tarjan SCC is O(V + E).

What are the applications of Tarjan SCC?

Tarjan SCC is commonly used for: Social network analysis, Compiler optimization, Web crawling.

What difficulty level is Tarjan SCC?

Tarjan SCC is considered advanced level in graph theory and algorithms.

learngraphtheory.org

Apprentissage interactif de la théorie des graphes

learngraphtheory.org

Apprentissage interactif de la théorie des graphes

Guest User

Using app without sign in

Sélection d'Algorithme

Cet algorithme nécessite un graphe dirigé. Vérifiez l'onglet Paramètres pour configurer.

Catégorie d'Algorithme :

Choisir un Algorithme :

CFC de Tarjan

Trouve les composantes fortement connexes en utilisant DFS

Temps: O(V + E)

Espace: O(V)

Cas d'usage: Trouver les CFC, analyse de dépendances, optimisation de compilateur

Nœud de Départ :

Lecture automatiqueAfficher la complexité

Exécution d'Algorithme

Sélectionnez un algorithme et générez les étapes pour commencer la visualisation

À propos de CFC de Tarjan

Trouve les composantes fortement connexes en utilisant DFS.

Cas d'usage: Trouver les CFC, analyse de dépendances, optimisation de compilateur

Lire l'article complet: Graph Algorithms and Their Complexity

Algorithmes associés: CFC de Kosaraju, Recherche en Profondeur (DFS), Tri Topologique

Contrôles de Graphe Interactifs

Actions de Base :

• Double-clic → Ajouter un nœud

• Glisser → Déplacer les nœuds

• Maj+clic → Connecter

• Clic droit → Menu contextuel

Avancé :

• Ctrl+clic → Multi-sélection

• Supprimer → Supprimer la sélection

• Double-clic arête → Modifier le poids

• Ctrl+glisser → Panoramique

Contrôles de Zoom

Ctrl + / -

100%

Zoom:Ctrl + / -

Réinitialiser:Ctrl + 0

Basculer:Ctrl + Shift + Z

Nœuds: 4

Arêtes: 4

Info NœudFlux d'ArêteDésencombrement Intelligent