Nouveau graphe
Importer / exporter
Disposition
Réglages des forces
Affichage
Choisissez un algorithme puis « Lancer » (ou clic droit sur un sommet de départ).
Cliquez dans une grille : les trois remplissages partent de la même case avec la même règle (colorier la case qui sort de la structure, puis y ajouter ses voisins non coloriés dans un ordre aléatoire). Seule la structure change. La couleur indique l'ordre de remplissage.
Une arête par ligne, a b ou a b 7 avec un poids. Un nom seul crée un sommet isolé.
Les lignes orienté et pondéré fixent la nature du graphe ; # commence un commentaire.
orienté pondéré s a 7 s b 9 a b 10 c # sommet isolé
Choisissez l'algorithme et, s'il en faut un, le sommet de départ, puis « Lancer » (ou faites un clic droit sur le sommet de départ). La barre sous le dessin parcourt les étapes (← →, Espace pour la lecture). À chaque étape, le panneau de droite montre la ligne du pseudo-code exécutée, l'explication, le contenu de la structure de données (file, pile, file de priorité…) et un tableau (distances, parents, dates…).
| Famille | Algorithmes |
|---|---|
| Parcours | largeur (file), profondeur avec pile, profondeur récursif avec dates et classification des arêtes |
| Plus courts chemins | Dijkstra, Bellman-Ford (poids négatifs, détection de cycle négatif), Floyd-Warshall |
| Arbres couvrants | Prim, Kruskal (union-find) |
| Structure | tri topologique (Kahn), composantes connexes, composantes fortement connexes (Kosaraju), test de biparticité |
| Coloration | coloration gloutonne par degré décroissant (Welsh-Powell) |
Codes couleur : un sommet orange est en attente (découvert, dans la structure), un sommet vert est traité, le sommet courant est entouré de bleu. Les arêtes vertes forment l'arbre construit (ou les arêtes retenues) ; la légende sous le dessin rappelle les couleurs utilisées par l'algorithme en cours. Pour les composantes et les colorations, chaque groupe a sa couleur. Les petites étiquettes à côté des sommets sont les annotations de l'algorithme (distance, dates début/fin, degré entrant…).
Les algorithmes sont écrits en OCaml (algos.ml) et compilés en JavaScript : chaque algorithme
enregistre une trace des étapes, que la page affiche.
int list array, ou couples (voisin, poids)) et
matrice d'adjacence, prêtes à coller dans un programme.Forces recalcule une disposition par l'algorithme d'Eades (les arêtes sont des ressorts, les sommets se repoussent) ; Animer le fait tourner en continu, et on peut déplacer des sommets pendant ce temps. Cercle place les sommets sur un cercle, Mélanger au hasard.
L'onglet Remplissage compare trois remplissages d'une grille depuis la même case : avec une pile (parcours en profondeur), une file (parcours en largeur) et un tirage aléatoire. Dessinez des murs, générez un labyrinthe, puis cliquez pour lancer les trois remplissages. Les couleurs vont du rouge (premières cases) au violet (dernières) : la file progresse par fronts circulaires, la pile en longs serpentins.