Minimum Spanning Tree Prim's Algorithm in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Prim's Algorithm?

Prim's Algorithm builds the MST by starting from any vertex and repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside it until all vertices are included.

beginner

In Prim's Algorithm, how do we choose the next edge to add?

We choose the edge with the smallest weight that connects a vertex already in the MST to a vertex not yet included.

intermediate

What data structure is commonly used to efficiently select the next edge in Prim's Algorithm?

A priority queue (often implemented as a min-heap) is used to quickly find and extract the edge with the smallest weight.

intermediate

Why does Prim's Algorithm always produce a Minimum Spanning Tree?

Because it always picks the smallest edge connecting the growing MST to a new vertex, ensuring no cycles and minimal total weight by the greedy choice property.

What does Prim's Algorithm start with?

A Any single vertex

B All edges sorted by weight

C All vertices at once

D The edge with the largest weight

Prim's Algorithm starts from any single vertex and grows the MST by adding edges.

Which data structure helps Prim's Algorithm pick the next smallest edge efficiently?

A Stack

B Queue

C Priority Queue

D Linked List

A priority queue (min-heap) is used to efficiently select the smallest edge.

Prim's Algorithm is an example of which type of algorithm?

A Dynamic Programming

B Greedy

C Divide and Conquer

D Backtracking

Prim's Algorithm uses a greedy approach by always choosing the smallest edge.

What condition must the graph satisfy for Prim's Algorithm to work correctly?

A Graph must be connected

B Graph must have negative weights

C Graph must be directed

D Graph must be disconnected

Prim's Algorithm requires the graph to be connected to reach all vertices.

What does Prim's Algorithm add to the MST at each step?

A A vertex with the largest degree

B A random edge

C All edges connected to the current vertex

D An edge with the smallest weight connecting MST to a new vertex

At each step, Prim's Algorithm adds the smallest edge connecting the MST to a new vertex.

Explain how Prim's Algorithm builds a Minimum Spanning Tree step-by-step.

Think about growing the tree one edge at a time by choosing the smallest connecting edge.

Describe why Prim's Algorithm guarantees the minimum total weight for the spanning tree.

Focus on how choosing the smallest edge at each step leads to overall minimum weight.