Kruskal’s Algorithm for Finding Minimal Spanning Trees Flashcards
What is the goal of Kruskal’s Algorithm?
To find a minimum spanning tree (MST) in a weighted undirected graph.
What is a minimum spanning tree (MST)?
A tree that connects all vertices in a graph with the minimum total edge weight and no cycles.
What data structure does Kruskal’s Algorithm use?
Union-Find (Disjoint Set Union) data structure.
What is the initial state in Kruskal’s Algorithm?
A forest of isolated nodes (each node is its own tree).
What is the main step in Kruskal’s Algorithm?
Add the next smallest edge if it connects two different trees.
When do you skip an edge in Kruskal’s Algorithm?
When it connects vertices that are already in the same tree (would form a cycle).
How are edges processed in Kruskal’s Algorithm?
Edges are sorted in ascending order of weights and processed in that order.
What is the time complexity of edge sorting?
O(E log E), where E is the number of edges.
What is the efficient time complexity of Kruskal’s Algorithm?
O(E log E + E * α(V)), where α(V) is the inverse Ackermann function.
What is the naive time complexity of Kruskal’s Algorithm?
O(EV + E log E), due to inefficient union-find operations.
What is α(V) in the context of Kruskal’s Algorithm?
The inverse Ackermann function, a very slowly growing function.
When does Kruskal’s Algorithm stop?
When the MST has n - 1 edges, where n is the number of vertices.
What is the purpose of the Union-Find data structure?
To efficiently track and merge disjoint sets (trees) in the forest.
What operations does Union-Find support?
FIND (find the root of a set) and UNION (merge two sets).
Why is Kruskal’s Algorithm considered greedy?
Because it always chooses the smallest edge that doesn’t form a cycle.
