Name: 50 Algos in 50 Weeks: Implementing Kruskal's algorithm
Start: 2012-06-14T19:00:00-04:00
End: 2012-06-14T22:00:00-04:00
Location: Pivotal Labs

Kruskal's algorithm is a greedy algorithm (http://en.wikipedia.org/wiki/Greedy_algorithm) in graph theory (http://en.wikipedia.org/wiki/Graph_theory) that finds a minimum spanning tree (http://en.wikipedia.org/wiki/Minimum_spanning_tree) for a connected (http://en.wikipedia.org/wiki/Connectivity_(graph_theory)) weighted graph (http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Weighted_graphs_and_networks). This means it finds a subset of theedges (http://en.wikipedia.org/wiki/Edge_(graph_theory)) that forms a tree that includes every vertex (http://en.wikipedia.org/wiki/Vertex_(graph_theory)), where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds aminimum spanning forest (a minimum spanning tree for each connected component (http://en.wikipedia.org/wiki/Connected_component_(graph_theory))).

This algorithm first appeared in Proceedings of the American Mathematical Society (http://en.wikipedia.org/wiki/Proceedings_of_the_American_Mathematical_Society), pp. 48–50 in 1956, and was written by Joseph Kruskal (http://en.wikipedia.org/wiki/Joseph_Kruskal).

Other algorithms for this problem include Prim's algorithm (http://en.wikipedia.org/wiki/Prim%27s_algorithm), Reverse-Delete algorithm (http://en.wikipedia.org/wiki/Reverse-Delete_algorithm), and Borůvka's algorithm (http://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm).

Algorithms and Data Structures

Technology

Professional Development

Java

Algorithms and Data Structures

50 Algos in 50 Weeks: Implementing Kruskal's algorithm

Algorithms and Data Structures

Details

Members are also interested in