Kruskal’s Algorithm

jdanray

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) Add the shortest edge to the tree.

(3) If it connects two vertices not already connected by previous edges, add the next shortest edge.

(4) Go to (3).

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…

View original post 31 mots de plus

Publicités

Laisser un commentaire

Choisissez une méthode de connexion pour poster votre commentaire:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s