Minimum Spanning Tree Essentials: Kruskal and Prim’s Algorithms Quiz Quiz

Challenge your understanding of Minimum Spanning Trees and their construction through Kruskal's and Prim’s algorithms. This quiz covers foundational concepts, step-by-step processes, and key properties critical for graph algorithms and efficient network design.

1. Kruskal’s algorithm: edge selection criteria

   In Kruskal’s algorithm, which edge is chosen at each step during the construction of a minimum spanning tree in a connected, undirected graph?

   1. The edge with the least weight that does not form a cycle
   2. The edge with the highest weight available
   3. Edges are chosen randomly at each step
   4. Any edge coming from a previously used vertex

   Explanation: Kruskal’s algorithm selects the edge with the least weight that does not form a cycle to ensure the minimal total weight of the spanning tree. Choosing the highest weight would lead to a maximum, not minimum, spanning tree. Selecting edges from previously used vertices or choosing randomly does not guarantee minimum weight or tree structure. The avoidance of cycles is crucial to preserve tree properties.

2. Prim’s algorithm: starting node effect

   When using Prim’s algorithm on a weighted graph, what impact does the starting vertex have on the final minimum spanning tree?

   1. The starting vertex always changes the minimum total cost of the spanning tree
   2. The result depends solely on the order in which vertices are numbered
   3. Prim’s algorithm does not require a starting vertex
   4. The starting vertex can affect the resulting spanning tree if there are edges with the same minimal weight

   Explanation: For graphs with multiple edges of equal minimal weights, the choice of starting vertex may lead to different, yet still minimum weight, spanning trees. The total cost, however, remains the same. The order of numbering does not matter, and Prim's algorithm specifically requires a starting vertex. Therefore, only the first option accurately describes the impact.

3. Cycle prevention in Kruskal’s algorithm

   Why is cycle detection necessary in Kruskal's algorithm when building a minimum spanning tree?

   1. To minimize the number of edges used
   2. To ensure all vertices are reached more than once
   3. To ensure the resulting subgraph remains a tree structure
   4. To maximize the total cost of the tree

   Explanation: Kruskal's algorithm must avoid cycles to maintain the tree property: a connected, acyclic graph spanning all vertices. The goal is not minimizing edge count (since a tree has exactly n-1 edges by definition) nor to maximize cost. Spanning trees never require reaching vertices more than once.

4. Prim’s algorithm: edge selection process

   During each iteration, how does Prim’s algorithm select the next edge to add to the growing minimum spanning tree?

   1. It selects any edge that forms a cycle with current vertices
   2. It chooses the next unvisited vertex regardless of weight
   3. It selects the maximum weight edge from the graph
   4. It picks the minimum weight edge connecting a vertex inside the tree to a vertex outside the tree

   Explanation: Prim's algorithm always extends the tree by adding the minimum-weight edge that connects to a new vertex outside the current tree. Selecting maximum weight edges, ignoring weights, or forming cycles does not ensure minimum total weight or valid tree formation, so only the first option correctly describes the process.

5. Definition of a minimum spanning tree (MST)

   Which statement best defines a minimum spanning tree in an undirected, connected weighted graph?

   1. It is the shortest path between any two vertices
   2. It is a subgraph connecting all vertices with the minimum possible total edge weight and no cycles
   3. It connects only some vertices of the graph
   4. It includes all edges of the graph regardless of cycles

   Explanation: A minimum spanning tree must connect all vertices (spanning), have minimum total edge weight, and must not contain cycles. It is not a partial connection or concerned with the shortest path between only two nodes, and it never includes all edges if that creates cycles.

6. Algorithm output uniqueness for MSTs

   If all the edge weights of a connected graph are distinct, what is true about the minimum spanning tree produced by Kruskal’s and Prim’s algorithms?

   1. Both algorithms will yield the same unique minimum spanning tree
   2. Prim’s algorithm cannot work on graphs with distinct edge weights
   3. Kruskal’s may produce multiple different trees, but Prim’s will be unique
   4. Both algorithms always yield multiple spanning trees

   Explanation: When all edge weights are distinct, there can only be one minimum spanning tree; both Kruskal's and Prim's algorithms will produce this same MST. The uniqueness derives from the fact that no ties exist for selecting edges. Both alternative choices stating multiple trees or algorithm incompatibility are inaccurate.

7. Use of greedy strategy

   Why are Kruskal’s and Prim’s algorithms considered greedy algorithms when constructing minimum spanning trees?

   1. They ignore the weight of edges until the end
   2. They solve the problem by using recursion and backtracking
   3. They make the locally optimal choice at each step hoping to find a global optimum
   4. They examine all possible spanning trees before selecting the best one

   Explanation: Both algorithms greedily pick the next best option available by local criteria (minimum weight edge) without considering future consequences, aiming for a globally minimum cost. They do not try all possible trees, nor do they use recursive or backtracking methods, and they consider edge weights throughout the process.

8. Time complexity comparison

   For a graph with V vertices and E edges, what is the typical time complexity of Kruskal’s algorithm using a sorting-based approach?

   1. O(E log E)
   2. O(V^2)
   3. O(E + V)
   4. O(V log V)

   Explanation: Kruskal’s algorithm mainly spends time sorting the edges, which takes O(E log E) time. O(V^2) is typical for adjacency-matrix-based Prim's implementations. O(E + V) applies to simpler traversal algorithms, and O(V log V) is not sufficient for edge-dominated processes.

9. Handling disconnected graphs in MST algorithms

   What result do Kruskal’s and Prim’s algorithms produce when given an undirected graph that is not connected?

   1. They build a minimum spanning forest connecting each component separately
   2. They create a cycle covering all vertices
   3. They combine the graph into a single connected tree by adding imaginary edges
   4. They cannot process the graph and always produce an error

   Explanation: With disconnected graphs, both algorithms create a minimum spanning forest, generating a separate minimum spanning tree for each connected component. They do not form cycles across all vertices, neither will they always error, nor can they add imaginary edges to artificially connect the graph.

10. Detecting cycles in Kruskal’s algorithm

    Which data structure is commonly used in Kruskal’s algorithm to efficiently keep track of connected components and detect cycles?

    1. Heap or priority queue
    2. Disjoint-set (Union-Find) structure
    3. Adjacency matrix
    4. Binary search tree

    Explanation: The disjoint-set, also called Union-Find, lets Kruskal’s algorithm quickly determine if two vertices belong to the same tree, preventing cycles when adding edges. Binary search trees organize elements but do not manage components. Heaps/priority queues are more relevant to Prim’s selection process. An adjacency matrix represents graph connectivity but is inefficient for cycle detection.