Category:Kruskal's Algorithm

This category contains pages concerning Kruskal's Algorithm:

The purpose Kruskal's Algorithm is to produce a minimum spanning tree for any given weighted graph $G$.

Step 1: Start with the edgeless graph $T$ whose vertices correspond with those of $G$.

Step 2: Choose an edge $e$ of $G$ such that:

a): Adding $e$ to $T$ would not make a cycle in $T$;

b): $e$ has the minimum weight of all the edges remaining in $G$ that fulfil the condition in a).

Step 3: Add $e$ to $T$.

Step 4: If $T$ spans $G$, stop. Otherwise, go to Step 2.

Source of Name

This entry was named for Joseph Bernard Kruskal.