Kruskal's Algorithm picks the next edge simply by picking the lightest edge. Doesn't that make breaking ties alphabetically impossible? If I had a graph where two edges a -> b and a -> c existed. If a -> c has a lighter edge weight, wouldn't Kruskal's Algorithm add the a -> c edge over the a -> b edge?
Maybe I am just confused on what breaking ties alphabetically means.
Any clarification would be greatly appreciated!
Best Answer
Kruskal's algorithm wants to add minimum-weight edges at each step (while avoiding circuits). "Ties" specifically mean the case where two edges have the same weight. In that case, we usually assume that the earlier alphabetically-identified edge is chosen.
This models the computational implementation that the vertices will necessarily be stored in some order in memory, and the standard find-lowest algorithm will record the earlier-encountered one as the minimal choice.