Kruskal's algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. 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. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
Pseudo Code for Kruskal’s Algorithm:
==============================
==============================
1. T (the final spanning tree) is defined to be the empty set;
2. For each vertex v of G, make the empty set out of v;
3. Sort the edges of G in ascending (non-decreasing) order;
4. For each edge (u, v) from the sored list of step 3.
If u and v belong to different sets
Add (u,v) to T;
Get together u and v in one single set;
5. Return T
2. For each vertex v of G, make the empty set out of v;
3. Sort the edges of G in ascending (non-decreasing) order;
4. For each edge (u, v) from the sored list of step 3.
If u and v belong to different sets
Add (u,v) to T;
Get together u and v in one single set;
5. Return T
No comments:
Post a Comment