Minimum Spanning Tree Kruskal'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 Kruskal's Algorithm?

Kruskal's Algorithm builds the MST by sorting all edges by weight and adding the smallest edge to the MST if it doesn't create a cycle, repeating until all vertices are connected.

intermediate

Why do we use a Union-Find (Disjoint Set) data structure in Kruskal's Algorithm?

Union-Find helps efficiently check if adding an edge creates a cycle by tracking which vertices are in the same connected component, allowing quick union and find operations.

intermediate

What is the time complexity of Kruskal's Algorithm?

The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Union-Find operations are almost constant time.

beginner

In Kruskal's Algorithm, what happens if adding an edge creates a cycle?

If adding an edge creates a cycle, the edge is skipped and not added to the MST to keep the tree structure without loops.

What is the first step in Kruskal's Algorithm?

A Sort all edges by their weight

B Pick any vertex as the starting point

C Create adjacency list

D Remove all cycles from the graph

Kruskal's Algorithm starts by sorting all edges from smallest to largest weight.

Which data structure is commonly used to detect cycles in Kruskal's Algorithm?

A Stack

B Union-Find (Disjoint Set)

C Queue

D Binary Search Tree

Union-Find efficiently tracks connected components to detect cycles.

What does Kruskal's Algorithm produce at the end?

A A shortest path tree

B A maximum spanning tree

C A cycle graph

D A minimum spanning tree

Kruskal's Algorithm produces a minimum spanning tree connecting all vertices with minimum total edge weight.

If an edge connects two vertices already in the same set, what should Kruskal's Algorithm do?

A Skip the edge to avoid cycle

B Add the edge to MST

C Remove one vertex

D Restart the algorithm

Adding such an edge would create a cycle, so it is skipped.

What is the main reason sorting edges is important in Kruskal's Algorithm?

A To find the longest path

B To build adjacency matrix

C To ensure the MST has minimum total weight

D To detect cycles faster

Sorting edges by weight ensures we pick the smallest edges first to minimize total MST weight.

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

Think about sorting edges and checking cycles before adding.

Describe the role of the Union-Find data structure in Kruskal's Algorithm and why it is important.

Focus on cycle detection and grouping vertices.