| Summary: | Kruskal's algorithm is a minimum-spanning-tree algorithm which finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.<br/><br/>1. create a forest F (a set of trees), where each vertex in the graph is a separate tree<br/>2. create a set S containing all the edges in the graph<br/>3. while S is nonempty and F is not yet spanning remove an edge with minimum weight from S<br/>4. if the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree<br/><br/>At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.
|
|---|
