{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm{{ algorithmLabel }} Graph{{ graphSizeLabel }} Step{{ stepLabel }}
Choose the structural question before selecting an algorithm.
{{ algorithmHelp }}
Representative graphs:
One to ten unique labels, for example A, B, C, D.
Use A -> B, one edge per line. Leave blank for an edgeless graph.
{{ playback_delay }} ms
The neutral default is 700 ms between transitions.

The chart renderer is unavailable. The vertex ledger and transition log remain available.

VertexCurrent stateAlgorithm evidenceCopy
{{ row.label }}{{ row.state }}{{ row.evidence }}
StepTransitionActive vertexFrontierCopy
{{ row.step }}{{ row.message }}{{ row.active }}{{ row.frontier }}
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
Minimum Spanning Tree Algorithm Simulator Compare Kruskal and Prim on weighted graphs with deterministic edge decisions, cycle rejections, and minimum spanning forest results.
Network Flow Algorithm Simulator Simulate Edmonds-Karp or Dinic on an editable capacity network and verify the maximum flow with residual traces and a minimum-cut certificate.
Recursion & Backtracking Simulator Trace four recursion and backtracking presets step by step with synchronized call stacks, branch choices and clear return and undo events.

Direction changes what a connection means. In a prerequisite graph, an arrow from A to B says A must come before B. In a call graph, it may mean A invokes B. Following arrows can reveal a valid order, a dependency loop, or a cluster whose members can all reach one another.

Topological order
A sequence in which every directed edge points from an earlier vertex to a later one. It exists only for a directed acyclic graph.
Directed cycle
A path that follows arrow direction and returns to its starting vertex. Even one cycle makes a topological order impossible.
Strongly connected component
A maximal group in which every vertex can reach every other vertex by directed paths.

These questions support different decisions. Topological ordering is useful for prerequisite planning, dependency builds, and task sequencing. Cycle evidence explains why no precedence order can satisfy every edge. Strongly connected components compress mutual dependencies into groups, making the larger one-way structure easier to inspect.

A graph may have more than one valid topological order. Choosing a different zero-indegree vertex or visiting edges in another order can change the sequence without changing its validity. Component membership is more stable, although the order in which components or their members are reported can still vary.

A small graph trace teaches the mechanism, but it does not establish what an arrow should mean in a real system. Missing vertices, reversed edges, or a dependency recorded at the wrong level can produce a mathematically correct answer to the wrong graph. Verify the graph model before acting on its order or component partition.

How to Use This Tool:

Choose the structural question first. The available algorithms change with the workflow because ordering and component analysis maintain different evidence.

  1. Select Topological order to test for a precedence sequence or Strongly connected components to partition mutual reachability.
  2. Choose Kahn or DFS topological for ordering, or Tarjan or Kosaraju for components. A representative graph can provide a quick starting case.
  3. Enter one to ten unique Vertices, then add up to 24 Directed edges as A -> B, one per line. List isolated vertices explicitly; self-loops are valid, but duplicates and unknown endpoints are rejected.
  4. Select Start trace, then step, play, pause, or finish. Playback delay changes only the time between transitions.
  5. Read the final order, cycle witness, or component partition, then inspect the vertex evidence and transition log when the conclusion is not obvious from the drawing.

Interpreting Results:

A reported topological order is one valid answer, not necessarily the only one. Check that each entered edge points forward in the sequence. If a cycle witness appears, follow its arrows back to the first label; that closed path is enough to prove that no topological ordering exists.

For component analysis, every vertex belongs to exactly one reported strongly connected component. A one-vertex component is normal, and it may contain a self-loop or no cycle at all. Compare Tarjan and Kosaraju by component membership rather than by component number or display order.

The trace is deterministic for the entered vertex and edge order. Reordering equivalent input can change which valid topological sequence or cycle witness is found first, so use the same input order for a step-by-step algorithm comparison.

Technical Details:

A directed graph consists of vertices and ordered edges. Reachability follows edge direction, so A → B does not imply B → A. The four supported methods answer one of two structural questions and expose the state that justifies each transition.

Rule Core:

AlgorithmMechanismCompletion evidence
KahnCompute indegrees, queue vertices at indegree 0, emit one, and decrement its outgoing neighbors.All vertices emitted gives an order; an early empty queue leaves a cycle.
DFS topologicalColor vertices during depth-first search and append each vertex after all outgoing edges finish.Reverse finish order unless an edge reaches a gray recursion-stack vertex.
TarjanAssign discovery indices and low-link values while maintaining one active DFS stack.A vertex whose low link equals its index closes one strongly connected component.
KosarajuRecord finish order, transpose every edge, then search the transpose in reverse finish order.Each second-pass search tree forms one strongly connected component.

Mechanism Core:

Kahn's indegree is the number of incoming edges that have not yet been removed. Only a zero-indegree vertex can be emitted without violating a predecessor edge. DFS uses three conceptual colors: white is unvisited, gray is active on the recursion stack, and black is finished. An edge to gray is a back edge and closes a directed cycle.

Tarjan's low-link value is the smallest discovery index reachable through the current DFS subtree while remaining within the active stack rules. When a root cannot reach an earlier stacked vertex, popping through that root yields a maximal component. Kosaraju reaches the same partition with two passes because reversing every edge preserves membership inside a strongly connected component while reversing the one-way links between components.

Determinism and bounds:

Vertices are visited in input order, and outgoing edges retain their entered order. Labels begin with a letter and may contain letters, digits, underscores, or hyphens. The bounded model accepts at most 10 vertices, 24 distinct directed edges, and 300 recorded frames. An edgeless graph is valid: every vertex can appear in a topological order and each vertex forms its own strongly connected component.

Worked Examples:

Several valid prerequisite orders

With vertices A, B, C and edges A → C and B → C, both A → B → C and B → A → C satisfy every edge. Kahn's queue and the entered vertex order determine which one appears first; neither sequence is more correct.

A loop blocks ordering but forms a component

With A → B, B → C, and C → A, topological analysis returns a cycle witness and no order. Component analysis places A, B, and C together because each label can reach the other two.

References: