Introducing
Prezi AI.
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Loading…
Minimum Spanning Tree
3
Transcript
Minimum spanning tree
Sapargaliyeva Guldar
Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees.
The minimal spanning tree is unique, if the weights of all edges are different.
Otherwise, there can be several minimal spanning trees.
Intro
And that's what I was just talking about
Prims and Kruskal algorithms are used to find the minimal spanning trees.
How to solve this problem?
Both approaches are known as ‘greedy’ algorithms.
A greedy algorithm is a technique that performs an optimal choice at each stage in the hope of finding a global optimum.
Implementation of Kruskal's algorithm
Kruskal
1.Sort all the edges of the graph from lowest to highest weight.
2.Take the edge with the smallest weight and add it to the desired spanning tree.
3.Repeat until all vertices are covered with edges.
Prim
Implementation of Prim's algorithm:
For each adjacent vertex, if the current weight is greater than the weight of the current edge, replace it with the weight of the current edge.
2
1
Take any vertex as initial vertex and set its weight to 0.
3
Repeat these steps for all given vertices in order of increasing weight.
Using the algorithm in real life:
Usage
Thank u for ur attention
Always happy:)
Do I have 95?
Of course)
Choose a template
Presentations from around the world
Learn more about creating dynamic, engaging presentations with Prezi