Minimum Spanning Tree Prim's Algorithm in DSA Typescript - 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 select the next edge to add?

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

intermediate

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

A priority queue (or min-heap) is used to quickly find and extract the edge with the smallest weight connecting to the MST.

intermediate

What is the time complexity of Prim's Algorithm using a priority queue?

The time complexity is O(E log V), where E is the number of edges and V is the number of vertices, because each edge is processed and the priority queue operations take logarithmic time.

What does Prim's Algorithm start with?

A All edges

B The vertex with the highest degree

C Any single vertex

D The edge with the largest weight

Prim's Algorithm starts from any single vertex and grows the MST from there.

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

A Stack

B Queue

C Linked List

D Priority Queue

A priority queue (min-heap) helps select the smallest edge quickly.

What condition must an edge satisfy to be added to the MST in Prim's Algorithm?

A Connects a vertex in MST to a vertex outside MST

B Connects two vertices already in MST

C Has the largest weight

D Is the first edge in the graph

Edges must connect the MST to a new vertex outside it.

What happens if the graph is not connected when running Prim's Algorithm?

A Algorithm finds MST for all components

B Algorithm fails to include all vertices

C Algorithm runs infinitely

D Algorithm ignores disconnected vertices

Prim's Algorithm only works on connected graphs; otherwise, some vertices remain unreachable.

What is the main goal of Prim's Algorithm?

A Find the minimum spanning tree

B Find the shortest path between two vertices

C Find the maximum spanning tree

D Sort all edges by weight

Prim's Algorithm finds the minimum spanning tree of a graph.

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

Think about growing the tree one edge at a time.

Describe why a priority queue is useful in Prim's Algorithm and how it affects performance.

Consider how to quickly find the next best edge.