Minimum spanning tree (Prim's) in Data Structures Theory - 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 tree to a vertex outside the tree until all vertices are included.

beginner

How does Prim's algorithm choose the next edge to add?

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

intermediate

Why does Prim's algorithm always produce a minimum spanning tree?

Because it always picks the smallest possible edge that expands the tree without creating cycles, ensuring the total weight is minimized.

intermediate

What data structure is commonly used to efficiently implement Prim's algorithm?

A priority queue (or min-heap) is used to quickly select the edge with the smallest weight at each step.

What does Prim's algorithm start with?

A An empty graph

B All edges

C The heaviest edge

D Any single vertex

Prim's algorithm begins from any single vertex and grows the MST by adding edges.

Which of the following best describes the edge selection in Prim's algorithm?

A Smallest edge connecting the MST to a new vertex

B Random edge from the graph

C Largest edge in the graph

D Edges that form cycles

Prim's algorithm always picks the smallest edge that connects the current MST to a new vertex.

What type of graph is required for Prim's algorithm to work correctly?

A Disconnected graph

B Directed graph

C Connected weighted graph

D Graph with no edges

Prim's algorithm requires a connected weighted graph to find a minimum spanning tree.

What is the main goal of Prim's algorithm?

A Find the shortest path between two vertices

B Find a minimum spanning tree

C Find a cycle in the graph

D Sort all edges by weight

Prim's algorithm is designed to find a minimum spanning tree.

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

A Priority queue (min-heap)

B Queue

C Stack

D Linked list

A priority queue or min-heap allows quick access to the smallest edge.

Explain how Prim's algorithm builds a minimum spanning tree step-by-step.

Think about growing the tree one edge at a time.

Why is a priority queue useful in Prim's algorithm?

Consider how to find the minimum edge fast.