Kruskal's Minimum Spanning Tree Algorithm

Lesson 7 of 10 • 1 upvotes • 5:53mins

Rakesh Naga Chinta

Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. Given a connected and undirected graph, aspanning tree of that graph is a subgraph that is a tree and connects all the vertices together.  A single graph can have many different spanning trees.  A minimum spanning tree (MST) or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.