Kruskal’s Algorithm

Kruskal’s algorithm is a popular algorithm for finding minimum spanning trees. Here is an outline of it:

(1) Start with an empty tree.

(2) If the current shortest edge connects two vertices and no edge that you’ve already added to the tree connects them, then add the current shortest edge to the tree.

(3) Go to (2).

Here is my Python implementation of Kruskal’s algorithm.

Kruskal’s algorithm is a greedy algorithm. Put simply, a greedy algorithm always does what’s best at that moment. You might think that all algorithms should do that, but sometimes locally optimal decisions don’t lead to global optima. Fortunately, they do in this case.

Like I said in my post on disjoint-set data structures, Kruskal’s algorithm uses a disjoint-set data structure. You assign each vertex a number from 0 to N – 1, where N is the number of vertices. Then you can use subset membership within the disjoint-set data structure to represent connection between vertices. Specifically, if the numbers for two vertices belong to the same subset, then the vertices are connected. This representation makes executing step (2) easy.

Sources:

http://www.cs.cornell.edu/~wdtseng/icpc/notes/graph_part4.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s