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

Edit

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. 1 A:={}
  2. 2 for each vertex v in V[G]
  3. 3 do MAKE_SET(v)
  4. 4 sort the edges of E by nondecreasing weight w
  5. 5 for each edge (u, v) in E, in order by nondecreasing weight
  6. 6 do if FIND_SET(u)!=FIND_SET(v)
  7. 7 then A:=A∪{(u,v)}
  8. 8 UNION(u,v)
  9. 9 return A

Basics of Kruskal՚s Algorithm

  1. 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

Edit

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.