**DOWNLOAD FREE PDF** **<<CLICK HERE>>**

## Kruskal's Algorithm Multiple choice Questions and Answers (MCQs)

Congratulations - you have completed *Kruskal's Algorithm Multiple choice Questions and Answers (MCQs)*.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%

Your answers are highlighted below.

Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

Kruskal's algorithm is used to .....

find minimum spanning tree | |

find single source shortest path | |

find all pair shortest path algorithm | |

traverse the graph |

Question 1 Explanation:

The Kruskal's algorithm is used to find the minimum spanning tree of the connected graph. It construct the MST by finding the edge having the least possible weight that connects two trees in the forest.

Question 2 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

Kruskal's algorithm is a .....

divide and conquer algorithm | |

dynamic programming algorithm | |

greedy algorithm | |

approximation algorithm |

Question 2 Explanation:

Kruskal's algorithm uses a greedy algorithm approach to find the MST of the connected weighted graph. In the greedy method, we attempt to find an optimal solution in stages.

Question 3 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

Consider the given graph.

What is the weight of the minimum spanning tree using the Kruskal's algorithm?

24 | |

23 | |

15 | |

19 |

Question 3 Explanation:

Kruskal's algorithm constructs the minimum spanning tree by constructing by adding the edges to spanning tree one-one by one. The MST for the given graph is,

So, the weight of the MST is 19.

Question 4 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

What is the time complexity of Kruskal's algorithm?

O(log V) | |

O(E log V) | |

O(E ^{2}) | |

O(V log E) |

Question 4 Explanation:

Kruskal's algorithm involves sorting of the edges, which takes O(E logE) time, where E is a number of edges in graph and V is the number of vertices. After sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires O(logV) time. So, overall Kruskal's algorithm requires O(E log V) time.

Question 5 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER] |

Consider the following graph. Using Kruskal's algorithm, which edge will be selected first?

GF | |

DE | |

BE | |

BG |

Question 5 Explanation:

In Krsuskal's algorithm the edges are selected and added to the spanning tree in increasing order of their weights. Therefore, the first edge selected will be the minimal one. So, correct option is BE.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect.

There are 5 questions to complete.