The Eduladder is a community of students, teachers, and programmers just interested to make you pass any exams. So we help you to solve your academic and programming questions fast.
In eduladder you can Ask,Answer,Listen,Earn and Download Questions and Question papers.
Watch related videos of your favorite subject.
Connect with students from different parts of the world.
Apply or Post Jobs, Courses ,Internships and Volunteering opportunity. For FREE
See Our team
Wondering how we keep quality?
Got unsolved questions? Ask Questions

Design-and-Analysis-of-Algorithms-Subject-Code--10CSL47-Lab-Manual-PROGRAM-6-->View question

What is the minimum spanning tree?

what is the minimum spanning tree? Explain it in detail


Asked On2019-08-11 14:26:26 by:imakki

Taged users:
satyashiromani

Likes:
imakki

Dislikes:
Be first to dislike this question
Talk about this  Like  Dislike
View all qusetions
Answers

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.

Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are:

  1. Cluster Analysis
  2. Handwriting recognition
  3. Image segmentation


Famous algorithms for finding the Minimum Spanning Tree:

Kruskal’s Algorithm

Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal's algorithm follows greedy approach as in each iteration it finds an edge which has least weight and add it to the growing spanning tree.

Algorithm Steps:

  • Sort the graph edges with respect to their weights.
  • Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
  • Only add edges which doesn't form a cycle , edges which connect only disconnected components.

Answerd on:2019-09-03 Answerd By:Ananth

Likes:
|Ananth

Dislikes:
Be first to dislike this answer
Talk about this  Like  Dislike

You might like this video:Watch more here

Watch more videos from this user Here

Learn how to upload a video and start earning here



Lets together make the web is a better place

We made eduladder by keeping the ideology of building a supermarket of all the educational material available under one roof. We are doing it with the help of individual contributors like you, interns and employees. So the resources you are looking for can be easily available and accessible also with the freedom of remix reuse and reshare our content under the terms of creative commons license with attribution required close.

You can also contribute to our vision of "Helping student to pass any exams" with these.
Answer a question: You can answer the questions not yet answered in eduladder.How to answer a question
Career: Work or do your internship with us.Work with us
Create a video: You can teach anything and everything each video should be less than five minutes should cover the idea less than five min.How to upload a video on eduladder