Build the graph, pick the algorithm and follow every step of the run.
A visual lab for lectures and tutoring sessions. Draw directed or undirected vertices and edges, set weights and run the classic algorithms of the course in the same notation used in class, with tables, queues and the reasoning behind every iteration.
Edit right on the canvas
Create vertices with a click, connect them and adjust weights and direction without leaving the screen.
Directed, undirected or mixed
Each edge keeps its own direction. Algorithms check the required graph type before they run.
Step-by-step trace
Queues, stacks, dist and pred tables and distance matrices follow the animation at every iteration.
From graph search to coloring, in course order
Every run produces a full trace: vertex markings, auxiliary tables and the reasoning behind each decision.
Depth-first search
O(n + m)Always picks the marked vertex that was reached most recently, recording a discovery time d and a finish time f.
Graph search
Breadth-first search
O(n + m)Always picks the marked vertex that was reached least recently, using a queue, and assigns each vertex its level.
Graph search
Kosaraju's algorithm
O(n + m)Finds the strongly connected components with two depth-first searches: one on G and another on the reverse graph Gᴿ.
Connectivity
Fleury's algorithm
O(m² )Builds an Eulerian trail by walking through the graph and avoiding crossing a bridge while another edge is still available.
Eulerian graphs
Prim's algorithm
O(m log n)Adds vertices one by one: at each step it takes the lightest edge between V(T) and the vertices not yet selected.
Minimum spanning tree
Kruskal's algorithm
O(m log m)Adds edges, not vertices: sorts the edges by non-decreasing weight and accepts each one that does not form a cycle with those already in E(T).
Minimum spanning tree
Dijkstra's algorithm
O(n²)"Closes" one vertex per iteration, always the one with the smallest dist, and relaxes the tense edges leaving it.
Shortest paths
Bellman-Ford algorithm
O(n · m)Dynamic programming: examines every edge in each iteration, relaxing the tense ones, for |V(G)| − 1 iterations.
Shortest paths
Floyd-Warshall algorithm
O(n³)All-pairs shortest paths through dynamic programming: round k allows vertex k as an intermediate.
Shortest paths
Ford-Fulkerson method
O(m · f) with integer capacitiesWhile some augmenting path exists in G'(f), pushes the bottleneck δ along it and updates the residual network.
Maximum flow
Edmonds-Karp algorithm
O(n · m² )An efficient implementation of Ford-Fulkerson: each iteration picks the shortest augmenting path, found by breadth-first search.
Maximum flow
Dinic's algorithm
O(n² · m)Each iteration builds the level graph GL from G′(f) and finds a blocking flow in it.
Maximum flow
Kahn's algorithm
O(n + m)At each step takes a vertex with in-degree zero, appends it to the result and lowers the in-degree of its successors.
Topological sorting
Topological sort via depth-first search
O(n + m)Described by Tarjan in 1976: inserts each vertex at the front of the result only after visiting every vertex that depends on it.
Topological sorting
Edmonds' blossom algorithm
O(n² · m)Searches for M-augmenting paths between exposed vertices, contracting the blossoms that appear, until none is left.
Matching
Greedy coloring
O(n + m)Goes through the vertices in any order and gives each one the lowest-index color not used by any of its neighbors.
Coloring
Welsh-Powell algorithm
O(n² )Sorts the vertices by non-increasing degree and gives one color to every vertex not adjacent to a vertex already painted with it.
Coloring