Guide complet de 23+ algorithmes essentiels de graphes avec analyse de complexité, cas d'usage et visualisations interactives.
Essayer la Plateforme InteractiveExplore le graphe niveau par niveau, visitant tous les voisins avant d'aller plus profond. Utilise une file pour maintenir l'ordre d'exploration.
Explore aussi profondément que possible dans chaque branche avant de revenir en arrière. Utilise une pile (ou récursion) pour suivre le chemin d'exploration.
Ordonnancement linéaire des sommets dans un graphe acyclique orienté (DAG) où chaque sommet apparaît avant tous les sommets vers lesquels il pointe.
Trouve un chemin qui visite chaque arête exactement une fois dans un graphe non orienté. Existe quand le graphe a exactement 0 ou 2 sommets de degré impair.
Trouve les plus courts chemins d'un sommet source vers tous les autres sommets dans un graphe pondéré avec des poids d'arêtes non négatifs.
Trouve les plus courts chemins depuis un sommet source et détecte les cycles de poids négatif. Fonctionne avec des poids d'arêtes négatifs.
Trouve les plus courts chemins entre toutes les paires de sommets en utilisant la programmation dynamique avec des sommets intermédiaires.
Construit l'arbre couvrant minimal en croissant depuis un seul sommet, ajoutant toujours l'arête de poids minimal qui se connecte à un nouveau sommet.
Construit l'arbre couvrant minimal en triant toutes les arêtes et en utilisant Union-Find pour éviter les cycles tout en ajoutant les arêtes de poids minimal.
Construit l'arbre couvrant minimal en utilisant une approche parallèle basée sur les composants, adaptée aux environnements de calcul distribué.
Trouve les composantes fortement connexes dans les graphes orientés en utilisant DFS avec des valeurs low-link et une pile.
Finds strongly connected components using two DFS passes: one on the original graph and one on the transpose graph.
Finds vertices whose removal would increase the number of connected components in an undirected graph.
Finds edges whose removal would increase the number of connected components in an undirected graph.
Determines if a graph can be colored with exactly two colors such that no adjacent vertices share the same color.
Detects the presence of cycles in both directed and undirected graphs using various techniques like DFS and Union-Find.
Finds a path that visits every vertex exactly once using backtracking and dynamic programming techniques.
Finds the shortest possible route that visits every city exactly once and returns to the starting point.
Assigns colors to vertices such that no two adjacent vertices share the same color, using the minimum number of colors.
Finds the largest complete subgraph where every pair of vertices is connected by an edge.
Determines if a graph is chordal (every cycle of length 4 or more has a chord - an edge connecting two non-adjacent vertices in the cycle).
Finds the maximum flow from a source to a sink in a flow network using algorithms like Ford-Fulkerson with augmenting paths.
Finds the minimum capacity cut that separates the source from the sink, closely related to maximum flow by the max-flow min-cut theorem.
Experience interactive visualizations and step-by-step execution of all these algorithms.
Lancer la Plateforme Interactive