Kruskal's Algorithm
Last updated
What is Kruskal's Algorithm?
Kruskal's algorithm is a popular procedure in computer science for finding minimum spanning trees in a graph, developed by Joseph Kruskal in 1956. The algorithm operates by sorting the edges of the graph by their weight in ascending order. Then, it loops through each, adding the edge to the spanning tree if it doesn't form a circuit with the edges already there. This process repeats until all the vertices in the graph are included in the tree. Kruskal's algorithm belongs to the group of Greedy Algorithms as it tries to find the local optimum at each stage with the hope of finding the global optimum. It has an overall time complexity of O(E log E) or O(E log V), where E is the number of edges and V is the number of vertices.
More in stage 11: Advanced Data Structures
- Advanced Data Structures
- Trie
- Segment Trees
- Fenwick Trees
- Disjoint Set (Union-Find)
- Suffix Trees and Arrays
- Binary Trees
- Tree Traversal
- Search Algorithms
- Binary Search Trees
- In-Order Traversal
- Breadth First Search
- AVL Trees
- Pre-Order Traversal
- Depth First Search
- B-Trees
- Heap
- Post-Order Traversal
- Search Algorithms
- Breadth First Search
- Depth First Search
- Shortest Path Algorithms
- Dijkstra's Algorithm
- Bellman-Ford Algoritm
- A* Algorithm
- Minimum Spanning Tree
- Prim's Algorithm
Kruskal's Algorithm: common questions
Can I learn Kruskal's Algorithm in Hindi?
This lesson is written in English. Once you sign in, open it in the interactive course and ask the AI tutor to explain Kruskal's Algorithm in Hindi or Hinglish. The tutor answers from this lesson’s own text, so it stays on the syllabus, and it runs on your own Google, OpenAI or Anthropic key.
Is this Kruskal's Algorithm tutorial for beginners?
It is lesson 79 of 107 in the free Data Structures & Algorithms roadmap, in stage 11, Advanced Data Structures. If you are new to Data Structures & Algorithms, start from stage 1 and come back here in order; if you already know the earlier stages, this lesson stands on its own.