Virtual Labs

Minimum Spanning Tree using Boruvka's Algorithm

What is the primary goal of a Minimum Spanning Tree algorithm?

a: To find the shortest path between two vertices Explanation

Explanation

b: To find a tree that connects all vertices with minimum total edge weight Explanation

Explanation

c: To find a cycle that visits all vertices Explanation

Explanation

d: To find the vertex with the highest degree Explanation

Explanation

Which of the following is NOT a property of a Minimum Spanning Tree?

a: It is a tree Explanation

Explanation

b: It connects all vertices Explanation

Explanation

c: It has cycles Explanation

Explanation

d: It has the minimum possible total edge weight Explanation

Explanation

In a graph with V vertices, how many edges does a Minimum Spanning Tree have?

a: V Explanation

Explanation

b: V-1 Explanation

Explanation

c: V+1 Explanation

Explanation

d: It depends on the graph Explanation

Explanation

Boruvka's algorithm is a type of:

a: Greedy algorithm Explanation

Explanation

b: Divide and conquer algorithm Explanation

Explanation

c: Dynamic programming algorithm Explanation

Explanation

d: Brute force algorithm Explanation

Explanation

What does Boruvka's algorithm do in each iteration?

a: Adds the cheapest edge in the entire graph Explanation

Explanation

b: Adds the cheapest edge from each component to another component Explanation

Explanation

c: Removes the most expensive edge from a cycle Explanation

Explanation

d: Finds the shortest path from a source vertex Explanation

Explanation

How does Boruvka's algorithm handle parallel edges between two components?

a: It adds all of them Explanation

Explanation

b: It adds the one with the minimum weight Explanation

Explanation

c: It adds the one with the maximum weight Explanation

Explanation

d: It ignores them Explanation

Explanation

What is the time complexity of Boruvka's algorithm for a graph with V vertices and E edges?

a: O(E log V) Explanation

Explanation

b: O(V^2) Explanation

Explanation

c: O(E + V log V) Explanation

Explanation

d: O(log V) Explanation

Explanation

In each iteration of Boruvka's algorithm, the number of components decreases by at least half.

a: True Explanation

Explanation

b: False Explanation

Explanation

c: Both true and false depending on the graph Explanation

Explanation

d: Cannot be determined without more information Explanation

Explanation

Boruvka's algorithm can be parallelized.

a: True Explanation

Explanation

b: False Explanation

Explanation

c: Only for dense graphs Explanation

Explanation

d: Only for graphs without parallel edges Explanation

Explanation