Scribd
Upload
4 views1 page

Kruskal's Algorithm for Minimum Spanning Tree

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph by sorting edges and adding the smallest edge that does not form a cycle. The algorithm involves steps such as sorting edges, checking for cycles using a Disjoint Set data structure, and continues until the MST contains (V - 1) edges. Its time complexity is O(E log E) and it is applicable in areas like network design and road construction.

Uploaded by

hdawar353
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

Kruskal's Algorithm for Minimum Spanning Tree

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph by sorting edges and adding the smallest edge that does not form a cycle. The algorithm involves steps such as sorting edges, checking for cycles using a Disjoint Set data structure, and continues until the MST contains (V - 1) edges. Its time complexity is O(E log E) and it is applicable in areas like network design and road construction.

Uploaded by

hdawar353
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Kruskal’s Algorithm – Easy DSA Notes

1. What is Kruskal’s Algorithm?


Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, weighted, undirected graph.

2. Minimum Spanning Tree (MST)


A spanning tree that connects all vertices with the minimum possible total edge weight and contains
no cycles.

3. Key Idea (Very Easy)


Sort all edges by increasing weight and keep adding the smallest edge that does not form a cycle.

4. Steps of Kruskal’s Algorithm


Step 1: Sort all edges in increasing order of weight.
Step 2: Pick the smallest edge and check if it forms a cycle.
Step 3: If no cycle is formed, include the edge in MST.
Step 4: Repeat until MST contains (V - 1) edges.

5. Cycle Detection
Cycle detection is done using Disjoint Set (Union-Find) data structure.

6. Data Structures Used


- Edge list
- Disjoint Set (Union-Find)

7. Time Complexity
Sorting edges: O(E log E)
Overall complexity: O(E log E)

8. Important Points
- Works on connected, undirected, weighted graphs
- Greedy algorithm
- MST contains exactly (V - 1) edges

9. Applications
- Network design (cables, pipelines)
- Road construction
- Minimum cost connections

You might also like