Minimum spanning tree (Kruskal'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 Kruskal's algorithm?

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

intermediate

How does Kruskal's algorithm check for cycles when adding edges?

It uses a data structure called Union-Find (Disjoint Set) to efficiently check if two vertices belong to the same connected component, preventing cycles.

beginner

Why does Kruskal's algorithm sort edges by weight first?

Sorting edges by weight ensures that the algorithm always picks the smallest available edge, which helps build the MST with the minimum total weight.

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 the edges. Union-Find operations are almost constant time.

What does Kruskal's algorithm use to avoid cycles when adding edges?

A Depth-first search

B Stack

C Breadth-first search

D Union-Find data structure

Kruskal's algorithm uses the Union-Find data structure to efficiently check if adding an edge creates a cycle.

What is the first step in Kruskal's algorithm?

A Create a cycle

B Pick a random vertex

C Sort all edges by weight

D Remove the heaviest edge

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

Which of the following best describes the output of Kruskal's algorithm?

A A tree connecting all vertices with minimum total edge weight

B A path visiting all vertices exactly once

C A graph with maximum number of edges

D A disconnected set of vertices

The output is a minimum spanning tree connecting all vertices with the smallest total edge weight.

If adding an edge creates a cycle, what does Kruskal's algorithm do?

A Skips that edge

B Adds the edge anyway

C Removes a vertex

D Restarts the algorithm

Kruskal's algorithm skips edges that would create cycles to maintain a tree structure.

What type of algorithm is Kruskal's algorithm?

A Dynamic programming

B Greedy algorithm

C Divide and conquer

D Backtracking

Kruskal's algorithm is a greedy algorithm because it picks the smallest edge available at each step.

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

Think about sorting edges and avoiding cycles.

Describe why the Union-Find data structure is important in Kruskal's algorithm.

Consider how to know if two vertices are already connected.