{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Algorithm {{ algorithmLabel }} Accepted {{ resultsReady ? computation.values.accepted_count : '—' }} Components {{ resultsReady ? computation.values.component_count : '—' }}

Topology visual unavailable.

Both algorithms use ascending weight and source-row order to break ties.
One edge per line: A B 4. Use one label alone for an isolated vertex.
Samples replace the edge list and keep the selected algorithm.
The final minimum weight is unchanged, but tied decision order can differ.
Accepted-only mode shortens the ledger; the forest and chart remain unchanged.
Forest result
{{ row.label }} {{ row.display }}
{{ edge.id }} · {{ edge.source }}—{{ edge.target }} · {{ edge.weight }}

The chart renderer is unavailable. The same edge decisions remain available in the trace table.

Step Edge Endpoints Weight Decision Reason Copy
{{ row.step }} {{ row.id }} {{ row.source }}—{{ row.target }} {{ row.weight }} {{ row.decision }} {{ row.reason }}
Pathfinding Algorithm Simulator Compare four pathfinding algorithms on an editable weighted grid and inspect route cost, exploration order, diagonal rules and no-path outcomes.
Directed Graph Algorithms Simulator Trace topological ordering and cycle evidence or find strongly connected components with four classic directed-graph algorithms step by step.
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.
Heap Operations Simulator Build min or max heaps and trace insert, peek, and extract operations with synchronized array and tree views plus comparison and swap counts.

Connecting every site in a weighted network does not require keeping every possible link. A spanning tree reaches all vertices in one connected component without a cycle, and a minimum spanning tree chooses such a connection with the smallest total edge weight.

Weights can represent cable length, construction cost, delay, or any other additive quantity. They need not be physical distances, and they may be zero or negative. The result minimizes the sum under the supplied weights; it does not automatically minimize the longest individual edge, travel distance between every pair, or resilience after an edge fails.

  • Tree: a connected set of edges with no cycle.
  • Spanning: every vertex in the component is included.
  • Minimum: no other spanning tree for that component has a smaller total weight.
  • Forest: one tree per connected component when the graph is disconnected.

Kruskal and Prim are greedy algorithms, but their local choices differ. Kruskal considers edges globally from lightest to heaviest and rejects an edge that closes a cycle. Prim starts from a vertex and repeatedly adds the lightest edge crossing from the visited set to an unvisited vertex.

Equal weights can produce several valid minimum trees. A deterministic tie rule makes one trace repeatable, but a different tied edge set can be just as optimal. Comparing only the accepted edge identities can therefore be misleading; total weight, component coverage, and the absence of cycles matter too.

How to Use This Tool:

Describe one undirected weighted graph, then run Kruskal and Prim against the same rows.

  1. Choose Kruskal or Prim.
  2. Enter one edge per line as A B 4. A line containing one vertex label declares an isolated vertex; blank lines and lines beginning with # are ignored.
  3. Keep the graph within 2 to 10 vertices and 1 to 24 distinct undirected edges. Self-loops and repeated endpoint pairs are rejected; weights must be integers from -1,000,000 to 1,000,000.
  4. For Prim, select the start vertex. Both algorithms break equal-weight ties by the source-row order.
  5. Choose all edge decisions or accepted edges only, then compare the forest, total weight, component count, and decision reasons. Trace detail changes the ledger length, not the computed forest.

Interpreting Results:

Total weight is the sum of accepted edge weights. A connected graph should produce one minimum spanning tree with V − 1 accepted edges; a disconnected graph produces a minimum spanning forest with one tree per component.

  • Accepted identifies edges chosen for the forest. Rejected identifies edges that would create a cycle or whose endpoints are already connected.
  • Components greater than 1 means the input graph is disconnected. No edge selection can join components when no source edge crosses between them.
  • Negative weights are valid and should be favored when they can be added without a cycle.
  • Tied weights may change accepted edge identities or decision order. Recheck total weight and coverage before treating a different tree as a contradiction.
  • Prim’s start vertex can change the trace and tied choices, but not the minimum total for a fixed graph.

Technical Details:

The cut property supports both algorithms: for a partition of the vertices, a lightest eligible edge crossing that cut can extend a minimum solution. Kruskal applies the idea across a growing forest; Prim applies it at the boundary of one growing tree at a time.

Formula Core:

For an accepted forest edge set F, total weight is the exact integer sum of its edge weights. With V vertices and C connected components, a spanning forest contains V − C accepted edges.

Weight(F) = ∑e∈Fw(e) |F| = V−C

No rounding is applied. Source-row order resolves equal weights, so repeated runs with unchanged input are deterministic.

Rule Core:

Algorithm Candidate order Accept rule Disconnected graph behavior
Kruskal All edges sorted by ascending weight, then source-row order. Accept when the endpoints belong to different components; union those components. The remaining components become separate trees in the forest.
Prim Edges crossing from visited to unvisited vertices, sorted by ascending weight then source-row order. Accept the first crossing edge and visit its unvisited endpoint. When no frontier remains, begin again at the first unvisited vertex.

Kruskal’s component test uses union by rank with path compression. Prim rebuilds the eligible frontier after each accepted edge. Those structures explain the trace, while the public result remains the accepted forest and its exact weight.

References: