Virtual Labs

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

a: It connects all vertices in the graph Explanation

Explanation

b: It has exactly (V-1) edges for V vertices Explanation

Explanation

c: It contains the shortest path between any two vertices Explanation

Explanation

d: It has no cycles Explanation

Explanation

In which scenario would a graph NOT have a spanning tree?

a: When the graph has weighted edges Explanation

Explanation

b: When the graph is disconnected Explanation

Explanation

c: When the graph has negative edge weights Explanation

Explanation

d: When the graph has more than 10 vertices Explanation

Explanation

What is the minimum possible weight of a spanning tree in a graph with edges: XY(2), XZ(5), YZ(1), YW(3), ZW(4)?

a: 6 Explanation

Explanation

b: 8 Explanation

Explanation

c: 10 Explanation

Explanation

d: 15 Explanation

Explanation

In Prim's algorithm, which edge is chosen at each step?

a: The globally minimum weight edge not yet selected Explanation

Explanation

b: The minimum weight edge that connects the current tree to a new vertex Explanation

Explanation

c: Any edge that doesn't create a cycle Explanation

Explanation

d: The maximum weight edge to ensure optimal selection Explanation

Explanation

Given a graph with vertices {A, B, C, D, E} and edges: AB(1), AC(4), BC(2), BD(3), CD(1), DE(2), CE(5), what is the total weight of the Minimum Spanning Tree if we use Kruskal's algorithm?

a: 5 Explanation

Explanation

b: 6 Explanation

Explanation

c: 7 Explanation

Explanation

d: 8 Explanation

Explanation

What is the time complexity of Kruskal's algorithm?

a: O(V²) where V is the number of vertices Explanation

Explanation

b: O(E log E) where E is the number of edges Explanation

Explanation

c: O(V log V) where V is the number of vertices Explanation

Explanation

d: O(E) where E is the number of edges Explanation

Explanation

Consider a graph where some edges have equal weights. Which statement about MSTs is true?

a: No MST can exist when edge weights are equal Explanation

Explanation

b: There will be exactly one MST regardless of equal weights Explanation

Explanation

c: Multiple MSTs with the same total weight may exist Explanation

Explanation

d: Kruskal's and Prim's will always produce different MSTs Explanation

Explanation

Which data structure is most efficient for implementing Prim's algorithm?

a: Stack Explanation

Explanation

b: Queue Explanation

Explanation

c: Priority Queue (Min-Heap) Explanation

Explanation

d: Hash Table Explanation

Explanation

In a dense graph with V vertices and approximately V² edges, which algorithm is generally more efficient?

a: Kruskal's algorithm because it handles more edges better Explanation

Explanation

b: Prim's algorithm with a binary heap implementation Explanation

Explanation

c: Both algorithms have identical performance Explanation

Explanation

d: Neither algorithm works efficiently on dense graphs Explanation

Explanation

Minimum Spanning Trees