Virtual Labs

Minimum Spanning Tree using Boruvka's Algorithm

Which statement accurately describes a Minimum Spanning Tree (MST)?

a: It is a subgraph that is a tree and connects all the vertices together. Explanation

Explanation

b: It is a path that visits every vertex exactly once. Explanation

Explanation

c: It is a collection of the heaviest edges that keep the graph connected. Explanation

Explanation

d: It is a tree that includes all possible edges from the graph. Explanation

Explanation

Under which condition is the Minimum Spanning Tree of a graph guaranteed to be unique?

a: If the graph is connected. Explanation

Explanation

b: If all edge weights are distinct. Explanation

Explanation

c: If the graph has more vertices than edges. Explanation

Explanation

d: If the graph is disconnected. Explanation

Explanation

Which of these algorithms is NOT used for finding MST?

a: Kruskal's Algorithm Explanation

Explanation

b: Prim's Algorithm Explanation

Explanation

c: Boruvka's Algorithm Explanation

Explanation

d: Dijkstra's Algorithm Explanation

Explanation

What is the initial state of the graph components in Boruvka's algorithm?

a: One single component containing all vertices. Explanation

Explanation

b: A forest where each vertex is its own component. Explanation

Explanation

c: Two components, split randomly. Explanation

Explanation

d: The algorithm starts with a complete MST and removes edges. Explanation

Explanation

When does Boruvka's algorithm terminate?

a: When all edges have been considered Explanation

Explanation

b: When there is only one component left Explanation

Explanation

c: After V-1 iterations Explanation

Explanation

d: When a cycle is detected Explanation

Explanation

The edges added in one iteration of Boruvka's algorithm are selected based on:

a: The cheapest edge from each vertex Explanation

Explanation

b: The cheapest edge from each component Explanation

Explanation

c: The globally cheapest edge Explanation

Explanation

d: A random edge Explanation

Explanation

Boruvka's algorithm is particularly well-suited for:

a: Dense graphs Explanation

Explanation

b: Sparse graphs Explanation

Explanation

c: Parallel and distributed computation Explanation

Explanation

d: Graphs with negative edge weights Explanation

Explanation

If a graph is disconnected, what does Boruvka's algorithm find?

a: A Minimum Spanning Tree Explanation

Explanation

b: A Minimum Spanning Forest Explanation

Explanation

c: It fails and returns an error Explanation

Explanation

d: A single path connecting two of the components Explanation

Explanation

The number of iterations in Boruvka's algorithm is at most:

a: V Explanation

Explanation

b: E Explanation

Explanation

c: log V Explanation

Explanation

d: V/2 Explanation

Explanation