L17 (MST, Kruksal's Algorithm)

Question 1

What’s the definition of a MST (Minimum Spanning Tree)? How many edges does an MST have in it?

Answer 1

A minimum spanning tree is a tree that spans all vertices in an undirected, connected, and weighted graph, such that the sum of the edge weights is minimized.

An MST has exactly |V| - 1 edges, where |V| is the number of vertices in the graph. There can be multiple MSTs for a given graph, but they will always have the same total weight.

Question 2

What is the Unique Edge Weights property of an MST?

Answer 2

Unique Edge Weights:
If all edge weights in the graph are distinct (no two edges have the same value), then the MST is unique (there is only one possible MST).

Question 3

What is Kruksal’s algorithm?

Answer 3

Kruskal’s algorithm is a greedy algorithm for finding the MST of an undirected, connected, and weighted graph. The algorithm sorts the edges by weight and iteratively adds edges to the MST while ensuring that no cycles are formed.

Question 4

What is the cycle property of an MST?

Answer 4

Cycle Property: The heaviest edge in any cycle of the graph cannot be part of the MST.

Question 5

What is the cut property of an MST?

Answer 5

Cut Property: Given a cut (partition) of the graph’s vertices into two sepatate non-empty sets, the lightest edge crossing the cut (the two sets) must be part of the MST

Question 6

Describe Kruksal’s Algorithm step-by-step. Input is a weighted graph G=(V,E,L)

Answer 6

1. Sort all edges by their weights in non-decreasing order.
2. Initialize an empty set for the MST and a disjoint set data structure for cycle detection.
3. For each edge (u, v) in the sorted list, perform the following steps:
   a. Check if the edge (u, v) would create a cycle using the disjoint set data structure.
   b. If no cycle is formed, add the edge (u, v) to the MST and union the sets containing u and v in the disjoint set data structure.
4. Continue until the MST contains exactly |V| - 1 edges.

Question 7

What’s the time complexity of Kruksal’s algorithm?

Answer 7

Kruskal’s Algorithm: O(|E| * log(|E|)) with a binary heap or O(|E| * log(|V|)) with a Fibonacci heap, where |E| is the number of edges and |V| is the number of vertices.

The dominating factor is the sorting of edges, while the disjoint set data structure operations contribute a nearly constant time factor (amortized) per edge.

Question 8

Kruskal’s algorithm uses the disjoint set data structure (also known as union-find). Describe this data structure.

What does it ensure in terms of time complexity with kruksal’s algorithm?

Answer 8

Union find is used in kruskal’s algorithm to efficiently detect cycles and maintain vertex connectivity.

In addition to “makeset”, this data structure enables two main operations: “find”, which identifies the set containing a specific element, and “union”, which merges two sets containing different elements.

The disjoint set data structure ensures that the cycle detection step in Kruskal’s algorithm runs in nearly constant time (amortized).

Question 9

What does a vertex’s “rank” mean in union find? what is the maximum rank of a given vertex?

Answer 9

• The “rank” of a vertex is the height of the subtree below that vertex
• The maximum rank of a vertex is O(log V )