NTA-NET (UGC-NET) Computer Science & Applications (87) Data and File Structures-Trees & Graphs and Their Algorithms Study Material (Page 14 of 16)
Choose Programs:
⏳ 🎯 Online Tests (4 Tests [100 questions each]): NTA Pattern, Analytics & Explanations
Rs. 800.00 -OR-
3 Year Validity (Multiple Devices)
Sample TestsDetailsSee Demo
🎓 Study Material (2083 Notes): 2024-2025 Syllabus
Rs. 1250.00 -OR-
3 Year Validity (Multiple Devices)
Topic-wise Notes & SampleDetails
🎯 2699 MCQs (& PYQs) with Full Explanations (2024-2025 Exam)
Rs. 600.00 -OR-
3 Year Validity (Multiple Devices)
CoverageDetailsSample Explanation
Help me Choose & Register (Watch Video) Already Subscribed?
Minimum Spanning Trees- Kruskal: Algorithm, Concept of Kruskal՚s Algorithm, Walk through
Algorithm
Concept of Kruskal՚s Algorithm
Kruskal՚s algorithm to find the minimum cost-spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree. A tree connects to another only and only if, it has the least cost among all available options and does not violate MST properties.
Kruskal՚s Algorithm
MST_KRUSKAL (G, w)
1 A:={}
2 for each vertex v in V[G]
3 do MAKE_SET(v)
4 sort the edges of E by nondecreasing weight w
5 for each edge (u, v) in E, in order by nondecreasing weight
6 do if FIND_SET(u)!=FIND_SET(v)
7 then A:=A∪{(u,v)}
8 UNION(u,v)
9 return A
Basics of Kruskal՚s Algorithm
Sort the edges E in an non-decreasing order (please note two edges can have…
… (561 more words, 697 figures) …
Subscribe (by clicking here) to view full notes and track progress.
Minimum Spanning Trees – Prim՚s Algorithm: Prim՚s Algorithm Analysis of the Prim՚s Algorithm
Minimum Spanning Trees
- Prim՚s algorithm to find minimum cost spanning tree (as Kruskal՚s algorithm) uses the greedy approach. Prim՚s algorithm shares a similarity with the shortest path first algorithms.
- Prim՚s algorithm, in contrast with Kru…
… (335 more words, 60 figures) …
Subscribe (by clicking here) to view full notes and track progress.