Greedy Algorithms Questions Medium
Kruskal's algorithm is a greedy algorithm used to find a minimum spanning tree in a connected weighted graph. The algorithm works as follows:
1. Sort all the edges of the graph in non-decreasing order of their weights.
2. Create an empty set called the "minimum spanning tree" (MST).
3. Iterate through the sorted edges in the increasing order of their weights.
4. For each edge, check if adding it to the MST creates a cycle. If not, add the edge to the MST.
5. Repeat step 4 until there are (V-1) edges in the MST, where V is the number of vertices in the graph.
The algorithm starts by sorting all the edges based on their weights. Then, it iterates through the sorted edges and checks if adding each edge to the MST creates a cycle. This is done by using a disjoint set data structure, such as Union-Find, to keep track of the connected components in the graph.
If adding an edge to the MST does not create a cycle, it means that the edge connects two different components of the graph. In this case, the edge is added to the MST. This process continues until the MST contains (V-1) edges, where V is the number of vertices in the graph. At this point, the MST is a minimum spanning tree of the original graph.
Kruskal's algorithm is efficient and has a time complexity of O(E log E), where E is the number of edges in the graph. It is widely used for finding minimum spanning trees in various applications, such as network design and clustering.