Cheapest Link and Kruskal's Algorithms

The Cheapest-Link and Kruskal's are similar algoritms that perform dissimilar tasks on weighted graphs. A weighted graph is a graph whose edges have been assigned numbers - their weights. Any weighted graph, in particular, a subgraph of a weighted graph, is also assigned weight - the sum of weights of all its edges.

The Cheapest-Link Algorithm

  1. On every step mark the cheapest unmarked edge.
  2. See that the marked edges
    1. do not form circuits, except when algorithm has stopped,
    2. do not converge three at a vertex.
  3. Repeat 1 and 2 while possible.

Kruskal's Algorithm

  1. On every step mark the cheapest unmarked edge.
  2. See that the marked edges do not form circuits.
  3. Repeat 1 and 2 while possible.

The Cheapest-Link algorithm leads to a Hamilton circuit, if any exists.

Kruskal's algorithm always leads to a minimum spanning tree of the given graph. A graph is a tree if (1) it's connected and (2) it has no circuits. A spanning tree of a graph is any of its subgraphs that contains all its vertices and is also a tree. A minimum spanning tree has the least weight among all spanning trees of the given graph.

(In the examples below, always click on the cheapest remaining unmarked edge.)

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

|Activities| |Contact| |Front page| |Contents| |Games|

Copyright © 1996-2018 Alexander Bogomolny

73356900