Kruskal's Algorithm

Preview

1. What is Kruskal’s Algorithm and what is its purpose in finding a minimum spanning tree?
2. How does Kruskal’s Algorithm determine the set of edges to be included in the minimum spanning tree?
3. Can Kruskal’s Algorithm be used to find a maximum spanning tree? If not, why?
4. What is the time complexity of Kruskal’s Algorithm and how does it compare to other minimum spanning tree algorithms?
5. How can Kruskal’s Algorithm be modified to handle disconnected graphs?

Explain

Kruskal’s Algorithm is a greedy algorithm used for finding the minimum spanning tree (MST) of a connected, weighted graph. The MST is the tree that spans all the nodes in the graph with the minimum possible total edge weight.

The Kruskal’s Algorithm works as follows:

1. Sort all the edges in non-decreasing order of their weight.
2. Create a forest of trees where each tree consists of one vertex (i.e., n disjoint sets).
3. Loop through each edge in the sorted list of edges and check if the two vertices of the edge belong to different sets (i.e., different trees). If yes, join the two trees and add the edge to the MST.
4. Continue until all the edges have been checked and the MST is obtained.

Example:
Consider the following graph with 6 vertices and 9 edges, where each edge is weighted as follows:

A ----- 4 ----- B
|               |

2| 5|
| |
C —– 3 —– D
\ /
1\ /2
\ /
\ /
\ /
E

To find the MST using Kruskal’s Algorithm, we first sort the edges in non-decreasing order of their weight:

Edges: (C, E) (A, C) (C, D) (A, B) (B, D) (D, E) (B, E) (A, D) (B, C)
Weights: 1 2 3 4 5 2 5 6 7

Next, we create a forest of trees consisting of each vertex as a separate tree:

A       B       C       D       E

Then, we start checking the edges in the sorted order and adding them to the MST if they connect different trees. The first edge (C, E) joins tree C to tree E:

A       B       C       D   
                        |   
                        E   

The second edge (A, C) joins tree A to tree C:

B       C      
|               
A               
              D                 
              |   
              E   

The third edge (C, D) joins tree C to tree D:

B       C      
|               
A       D           
              |         
              E   

The fourth edge (A, B) joins tree A to tree B:

    A           
   /|\           
    |            
    C           
    |            
    B           
              D                 
              |         
              E   

The fifth edge (B, D) joins tree B to tree D:

    A               
   /|\             
    |              
    C             
    |              
    B               
    |              
    D                
    |                
    E               

The sixth edge (D, E) joins tree D to tree E:

    A               
   /|\             
    |              
    C             
   /|\            
    |             
    B               
    |              
    D  --- E        

The seventh edge (B, E) cannot be added as it would create a cycle.

The eighth edge (A, D) cannot be added as it connects two nodes already in the same tree.

The ninth edge (B, C) cannot be added as it connects two nodes already in the same tree.

Therefore, the MST consists of the edges (C, E), (A, C), (C, D), (A, B), (B, D), and (D, E), with a total edge weight of 17.

Keypoint

1. Kruskal’s Algorithm is used to solve minimum spanning tree (MST) problems in a weighted graph.
2. The algorithm starts by considering each vertex as a separate tree, and then it iteratively merges the trees until only one tree remains, which is the MST.
3. To merge the trees, Kruskal’s Algorithm initially sorts all the edges in the graph by weight.
4. It then selects the edge with the lowest weight, and checks whether it forms a cycle or not. If the edge forms a cycle, it is discarded, else it is added to the MST.
5. This process is repeated until all the vertices are connected in a single tree, and the MST is obtained.
6. Kruskal’s Algorithm is optimal and efficient, with a run-time complexity of O(E log E), where E is the number of edges in the graph.
7. It is widely used in various applications, such as network design, clustering, and machine learning.

Review

1. What is Kruskal’s Algorithm used for?
   Answer: Kruskal’s Algorithm is a popular algorithm used to find the minimum spanning tree of a graph.

2. What is the basic idea behind Kruskal’s Algorithm?
   Answer: Kruskal’s Algorithm works by sorting the edges of a graph according to their weights and then adding them to the minimum spanning tree in increasing order of their weights.

3. How does Kruskal’s Algorithm ensure that the minimum spanning tree is found?
   Answer: Kruskal’s Algorithm ensures that the minimum spanning tree is found by keeping track of the edges added to the tree and ensuring that they do not form a cycle.

4. What is the time complexity of Kruskal’s Algorithm?
   Answer: The time complexity of Kruskal’s Algorithm is O(E log E), where E is the number of edges in the graph.

5. What is the difference between Kruskal’s Algorithm and Prim’s Algorithm?
   Answer: Kruskal’s Algorithm and Prim’s Algorithm are both used to find the minimum spanning tree of a graph, but Kruskal’s Algorithm is based on sorting the edges of the graph and adding them to the tree in increasing order, while Prim’s Algorithm is based on starting with a single vertex and adding the closest unvisited vertex to the tree at each step.