medium
2 min read
Kruskal MST
Kruskal Minimum Spanning Tree (MST) A Kruskal Minimum Spanning Tree (MST) is a subgraph of a graph that connects all the vertices without any cycles. The MS...
Quick Actions
Insights
Difficultymedium
Reading Time2 min
Kruskal Minimum Spanning Tree (MST) A Kruskal Minimum Spanning Tree (MST) is a subgraph of a graph that connects all the vertices without any cycles. The MS...
Kruskal Minimum Spanning Tree (MST)
A Kruskal Minimum Spanning Tree (MST) is a subgraph of a graph that connects all the vertices without any cycles. The MST is constructed by iteratively adding edges to the graph, starting with the edges that create the minimum spanning tree.
Construction:
Start with an empty spanning tree.
Choose the edge with the minimum weight among all edges not yet added to the spanning tree.
If the edge connects a new vertex to an existing vertex, add the edge to the spanning tree and continue the iteration.
Repeat this process until all edges have been added to the spanning tree.
Properties:
The MST is a subgraph of the original graph.
The MST has the minimum total edge weight of all possible MSTs for the original graph.
The MST is a forest, meaning it is a disjoint set of vertices.
Example:
Consider the following graph:
A --- B
| |
C --- D
The minimum spanning tree for this graph would be:
A --- B
\ /
C --- D
Applications:
MSTs have many applications in computer science, including:
Graph drawing
Network routing
Image processing
Scheduling
Resource allocation
Time Complexity:
The time complexity of Kruskal's algorithm is O(E log V), where E is the number of edges and V is the number of vertices in the graph. This is because the algorithm iterates over all possible edges in the graph and adds them to the spanning tree in order of their weight