3.5 Prims and Kruskals Algorithms - Greedy Method
Summary
TLDRThis script explains the concept of a minimum cost spanning tree (MCST) in graph theory. It defines a spanning tree and illustrates how to calculate the number of possible spanning trees in a graph. The focus then shifts to finding the MCST using greedy algorithms like Prim's and Kruskal's, which efficiently select edges to minimize the total cost without forming cycles. The script also addresses scenarios with missing edge weights and non-connected graphs, emphasizing the importance of connected components in spanning tree formation.
Takeaways
- 🌳 A spanning tree is a subgraph of a connected graph that includes all the vertices and exactly (n-1) edges where n is the number of vertices.
- 🔄 The number of different spanning trees possible for a graph can be calculated using combinations, specifically 'n choose (n-1)' where n is the number of edges.
- 🔢 The formula to calculate the number of different spanning trees is (number of edges) choose (number of vertices - 1) minus the number of cycles.
- 🏗️ Prim's algorithm is a greedy method to find the minimum cost spanning tree by initially selecting the smallest edge and then always choosing the smallest edge connected to the already selected vertices.
- 🛠️ Kruskal's algorithm is another greedy method that selects the smallest edge and continues to do so without forming cycles until (n-1) edges are chosen.
- ⏱️ Kruskal's algorithm has a time complexity of O(n^2), but this can be improved to O(n log n) using a min-heap data structure.
- 🔄 Both Prim's and Kruskal's algorithms can be applied to non-connected graphs, but they will only find spanning trees for the individual connected components.
- 💡 The minimum cost of a missing edge in a graph can be deduced by understanding the cycle it would form if included in a spanning tree.
- 📉 In a weighted graph, different spanning trees can have varying costs, and the goal is to find the one with the minimum cost.
- 🚫 A graph must be connected to have a spanning tree; disconnected graphs do not support the concept of a single spanning tree.
Q & A
What is a spanning tree?
-A spanning tree is a subgraph of a graph that includes all the vertices of the graph but only a subset of the edges, specifically the number of edges is equal to the number of vertices minus one, and it contains no cycles.
How many different spanning trees can be formed from a graph with six vertices and six edges?
-The number of different spanning trees that can be formed is given by the combination formula \( \binom{6}{5} \), which equals 6.
What is the formula to calculate the number of different spanning trees possible from a given graph?
-The formula to calculate the number of different spanning trees is to take the number of edges available, subtract the number of cycles formed by those edges, and then subtract one to account for the number of vertices.
How does the cost of a spanning tree in a weighted graph differ from one spanning tree to another?
-The cost of a spanning tree in a weighted graph can vary because different sets of edges can be chosen to form the tree, each with a different total weight.
What is the minimum cost spanning tree?
-The minimum cost spanning tree is the spanning tree that has the lowest possible total edge weight among all possible spanning trees for a given weighted graph.
What are the two greedy algorithms for finding the minimum cost spanning tree?
-The two greedy algorithms for finding the minimum cost spanning tree are Prim's algorithm and Kruskal's algorithm.
How does Prim's algorithm work to find the minimum cost spanning tree?
-Prim's algorithm starts with an arbitrary vertex and grows the minimum cost spanning tree by always adding the smallest edge that connects a new vertex to the tree.
How does Kruskal's algorithm work to find the minimum cost spanning tree?
-Kruskal's algorithm sorts all the edges in the graph by weight and adds them to the minimum cost spanning tree in ascending order, ensuring no cycles are formed.
What is the time complexity of Kruskal's algorithm without using a data structure like a min-heap?
-The time complexity of Kruskal's algorithm without using a min-heap is \( \Theta(n^2) \), where n is the number of vertices.
How can Kruskal's algorithm be optimized using a min-heap?
-Using a min-heap, Kruskal's algorithm can achieve a time complexity of \( \Theta(n \log n) \) by efficiently finding the next minimum edge to add to the tree.
Can Prim's or Kruskal's algorithm find a minimum cost spanning tree for a non-connected graph?
-No, Prim's or Kruskal's algorithm cannot find a minimum cost spanning tree for a non-connected graph because a spanning tree requires all vertices to be connected.
What is the minimum possible weight for an edge that is not included in the minimum cost spanning tree?
-The minimum possible weight for an edge not included in the minimum cost spanning tree is the weight that would have been chosen if it were available before the edge that actually formed a cycle.
Outlines
🌳 Understanding Spanning Trees
The paragraph introduces the concept of a minimum cost spanning tree (MCST) and explains what a spanning tree is. A spanning tree is a subgraph of a larger graph that includes all the vertices but only a subset of the edges, specifically 'n-1' edges where 'n' is the number of vertices. The paragraph uses an example graph to illustrate this, showing how to select edges to form a spanning tree without creating any cycles. It also discusses the number of possible spanning trees that can be formed from a given graph, which is calculated by choosing 'n-1' edges from the total number of edges available.
🔍 Prim's Algorithm for Minimum Cost Spanning Trees
This section delves into Prim's algorithm, a greedy method for finding the minimum cost spanning tree of a connected, weighted graph. The algorithm starts with an arbitrary vertex and iteratively adds the cheapest edge that connects a non-selected vertex to the growing tree. The paragraph explains the step-by-step process of Prim's algorithm using an example graph, highlighting how to avoid cycles while selecting edges. It concludes with a discussion of the algorithm's time complexity and how it cannot be applied to non-connected graphs.
🌐 Kruskal's Algorithm for Finding Minimum Cost Spanning Trees
The paragraph describes Kruskal's algorithm, another greedy method for finding the minimum cost spanning tree. Unlike Prim's algorithm, which starts from a vertex and grows the tree, Kruskal's algorithm begins with the edges, sorting them by weight and adding them to the tree as long as they do not form a cycle. The paragraph explains how Kruskal's algorithm can be optimized using a min-heap data structure to improve its efficiency. It also addresses how Kruskal's algorithm can be applied to non-connected graphs to find spanning trees for each component.
🔄 Handling Edges with Missing Weights in Spanning Trees
This section discusses a scenario where a graph has edges with missing weights and how to determine the minimum possible values for these edges to form a valid spanning tree. The paragraph explains that if certain edges are not included in the spanning tree because they form cycles, their weights must be greater than the smallest available edge that could be included. It uses an example to illustrate how to find the minimum cost spanning tree even with missing edge weights and emphasizes that there can only be one optimal solution for the minimum cost, despite the possible variation in the set of input edges.
Mindmap
Keywords
💡Spanning Tree
💡Graph
💡Vertices
💡Edges
💡Cycle
💡Weighted Graph
💡Minimum Cost Spanning Tree
💡Prim's Algorithm
💡Kruskal's Algorithm
💡Greedy Method
💡Min Heap
Highlights
Definition of a spanning tree in a graph
Explanation of how to select edges for a spanning tree
The importance of avoiding cycles in a spanning tree
The formula for calculating the number of possible spanning trees
The concept of a weighted graph and its impact on spanning trees
The cost of a spanning tree and how it is calculated
Introduction to Prim's algorithm for finding the minimum cost spanning tree
Step-by-step explanation of Prim's algorithm
The limitation of Prim's algorithm for non-connected graphs
Introduction to Kruskal's algorithm as an alternative method
The greedy approach of Kruskal's algorithm in selecting edges
The impact of using a Min Heap to improve Kruskal's algorithm
The time complexity analysis of Kruskal's algorithm
The application of Kruskal's algorithm on non-connected graphs
How to determine the minimum possible value of missing edges in a graph
The uniqueness of the minimum cost in spanning tree problems
The possibility of multiple spanning trees with the same minimum cost
Transcripts
the topic is minimum cause spanning tree
so for that first of all we'll
understand what does it mean by a
spanning
tree here I have an example
graph graph is represented as G and v e
v is the set of
vertices 1 2 3 4 5 6 and E is the set of
edges the set of edges are from 1 to
2 and 2 to
3 3 to 4 and so
on graphs are represented as set of
vertices and edges now what is this
spanning tree spanning tree is a
subgraph of a graph me I should take the
subset of this so subset of what what is
this and it just both subset or only one
subset so I should take the subset of
edges vertices must be as it is so I
should take all vertices
six spanning Tre means I should take all
vertices then how many edges how many
vertices I have number of vertices are n
that is six so I should take number of
vertices minus one that is only five
edges SP Tre is a subgraph of a graph
having all vertices but only nus one
edges so out of these edges I should
take only five so 1 2 3 4
5 I did not take this one so this is
spinning
tree see a tree will not have a cycle so
there is no cycle here yes there's no
cycle here if I this you can say it's a
cycle if you start from one vertex you
can again reach back to that vertex but
here
there is no
cycle is it possible that I will take
this one but I will not take this yes
there's also an spanning
tree I will take this but I will not
take this yes this is also an spanning
tree so which Edge to select that is a
choice that is a choice for a spanning
tree so I can say that s is a subgraph
of a graph where s is defined as set of
of vertices and set of edges where set
of vertices are same as the vertices of
a
graph and edges are number of vertices
minus one so the number of edges are
number of vertices minus one this is how
formally we can divide in mathematics we
can Define like this now next thing for
a given graph how many different
spanning trees can be generated I want
to know that how many different spanning
trees are possible so see number of
edges are how many six 1 2 3 4 5 6 I
have and a spanning tree I should take
only
five I should take only five so 6
C5 out of six edges out of six edges I
have to select five how many ways I can
do that so 65 C ways so F 65 C is how
much six only so I can have six
different spanning trees just now you
can see it's a simple one that I have
skip this Edge like this I can leave one
one Edge right and I can form a spanning
tree right I can take all except this
take all except this take all except
this six are possible suppose if I have
one more Edge now now I have seven edges
and I want to select five now how many
spaning trees are possible see I can
have this spanning tree
also or I can have this spanning tree
also no possibilities are more now this
is 7
C5 7 C5 but this Edge will form cycle so
how many cycles it is forming this is
one cycle and this is another cycle so
this Edge is forming two cycles of
number of vertices less than six so if
it is forming number of vertices less
than 6 then you will
be 7 C5 -
2 so that's it so what's the formula to
know how many different spanning trees
are possible from a given graph so
whatever the number of edges you have
you should take all those and see of how
many edges you need you need five so
five is what number of vertices minus
one so this is number of vertices minus
1 and minus number of
Cycles you have to subtract number of
Cycles I have a graph where the edges
are having weights so this is a weighted
graph this a weighted
graph I want to know what are the
possible spanning trees possible so I'll
draw a few spanning trees let us draw
one spanning tree this is vertex 1 and 2
and 3 and four so four vertices are
there then how many edges I should take
4 - 1 only three so I'll select this one
1 2 3 so what is the weight of this one
5 3 and six so what is the cost of this
spanning tree cost of this spanning tree
is
14 I'll take one more spanning tree 1 2
3 4 and I'll take these edges let us see
what is the cost of this 4 63 then what
is the cost of this one
13 I'll take one more spanning Tre 1 2 3
4 and I'll take these edges this one and
this one and this one 4 2 and 3 so this
is cost is how much
9 now from this example some observation
we can understand something if you have
a weighted graph and you get different
spanning trees the cost of the spanning
trees may be varying you can get a
different cost of spanning
trees now the problem is can I find out
the minimum cost of spanning tree can I
find out the minimum one which gives me
minimum yes you can find out how you can
try all possible spanning trees
and then from that you can check
whichever is minimum you can pick up
that answer this is one
method trying all possible spanning
trees will be too lengthy is there any
greedy
method yes the greedy methods are
available for finding the minimum cause
spanning tree if a weighted graph is
given you can find out the minimum cause
spanning Tree by following the method
without finding out all possible span
entries so what are those those methods
one method
is prims algorithm and the second method
is cuscal
algorithm there are two algorithms for
finding minimum costes pan inry I have a
weighted graph here and I have to find a
minimum cost of spanning tree by
following prim's algorithm let's see how
Prim algorithm Works through an example
now as per prims algorithm he says that
from a graph first of all you select a
minimum cause Edge so the smallest Edge
in the entire graph is this
one
then this is the initial one now for the
rest of the procedure always select a
minimum cost Edge from the graph but
make sure that it should be connected to
already selected
vertices now the next minimum is which
one 3 to 4
don't take that it will not be connected
to one or six so take only those which
are connected to one or six means what
he is trying to do is always maintain a
tree primce thinks that if some farther
away Edge is selected then it may not be
forming a tree
finally so that is the reason he
suggested that always select a minimum
Edge which should be connected so let us
see what's the next one so for this
connected one are this one and this one
so out of this 25 and 28 25 is minimum
so select this
25 then this 28 and five connected to
five are 22 and 24 so out of this 28 24
and 22 so from 1 and 6 and 5 I'm
checking so already six is over so 1 and
five so out of those this is smallest
one so four is selected now from 1 six
and 5 4 who is smallest the connected
one so this is 24 and 18 and 12 so 12 is
a smaller so we will take
12 then out of all these which connected
is the smallest so here I have 24 18 and
16 so 16 is a smaller so take that
16 then out of all these who is next
connected so from 2 to 7 there is an
edge which is connected so this is
7 that's
it there are seven vertices so 1 2 3 4 5
6 six edges are selected and this how we
got a minimum C cost spanning tree and
and this is how we got a minimum cost
spanning tree what is the cost of a tree
the cost of a tree is if I add all
these if I add all these it is 99
so the approach of prims is initially
select the smallest one then always
select the connected smallest
one all right so this is the method of
Prim
algorithm next if I have a graph 1
2
3
4 5 6
7 if I have a graph like this which is
not connected there are total seven
vertices but there are two pieces in a
graph can Prim find out the minimum cost
spanning tree for this one no no
algorithm can find out because we cannot
find a tree for this one spanning tree
for this one in a spanning tree it must
be connected so for non-connected graph
we cannot find spanning trees at all but
if I start prims on this one starting
from vertex one if it is starting then
it may find the spanning tree for only
one component not the other component
next method for finding minimum cost of
spanning tree is Cru sculls method this
also follows a greedy approach instead
of trying out all possible spanning
trees it shows a procedure by following
which we can get a minimum cost of
spanning tree it says that always select
a minimum cost Edge always select a
minimum cost Edge let us follow this one
select smallest
Edge 1 2 6 that is 10 this one is
smallest and the next smallest test is 3
to 4 so the second Edge I'm selecting is
3 to 4 and it's cost is 12 next minimum
is 2 to 7 select 2 to 7 and this is 14
and the next minimum is 2 to 3 that is
16 and after this
the next minimum Ed is 7 to 4 but that
is 18 if I select that it will form a
cycle yes cral method says that always
select a minimum cost Edge but if it is
forming a cycle don't con include it in
the solution discard that edge don't
include an edge so it means always
select such that it is not forming a
cycle so if I include 4 to 7 it will
form a cycle so next one you check so
the next one is 22 so this is from 5 to
4 or 4 to 5 so this is 22 next minimum
is 24 so that is 7 and 5 if I include
this also it will form a cycle don't
include that one then the next minimum
one is 25 that is from 5 to 6 so this is
25 and the cost of this one is if you
add all these weights it's
99 so here also I got the same result
just how I got in prim's algorithm so
the so the prim algorithm and cral
algorithm has given the same result on
this particular graph now time taken by
Cal's algorithm how much time it takes
see it has to always select a minimum
cost Edge from the set of edges so let
us say there are e number of edges so
out of these edges it will find out the
minimum one and how many such edges it
will be selecting it will be selecting V
minus one that is number of vertices
minus one like we know in a spanning
tree if there there are seven vertices
we need six edes for forming a spanning
tree so that's 7 - 1 so as many vertices
we have minus one number of edges we
have to select so the total time will be
Theta of V into e there e v is number of
vertices and E is number of edges so it
is n into e n is the number of vertices
and E is the number of edges which can
also be written as n square if we say
both are n then it is n squ so the time
taken by chal algorithm is
n²
but cisal algorithm can be improve when
we have to always select a minimum cost
Edge then there is one data structure
which will always give you minimum value
that is min
heap if Min Heap is used then Min Heap
will always give you a minimum value
whenever you delete a value you get a
minimum value so if all these edges are
kept in a Min he whenever you delete you
will be getting a next minimum Edge so
you don't have to search so from Min
whenever you delete the time taken is
login so how much time it will take for
finding a minimum cost Edge log n time
so how many times you have to do that
that is end time number of vertices
minus one time so n so by using Min he
the time time complexity of crysal
algorithm will be n log n so that's how
crysal algorithm can be made
faster now if there is a graph given
that is not connected graph it is having
two components four vertices on this
side five vertices on that side can we
find a spanning tree on a non-connected
graph no spanning tree is not possible
but what happens if I run a scal
algorithm so csal algorithm will try to
find out total number of edges that is 9
- 1 so it will try to select eight edges
and it will not be forming a spanning
tree for entire graph but it may be
finding the spanning tree for each
component let us say if the first
minimum the one it will select is this
one then the next minimum it is having
more than one edes let us say it selects
next minimum and the next minimum it
will select this next minimum it selects
this and this is the next minimum so in
this way it is selecting the minimum
adjust from both the components or it
will be selecting from all the
components so it may be finding spanning
trees for all the components but not for
the entire graph so cisal algor them may
work for non-connected graphs also but
it may give spanning tree for those
components let us take a problem here a
graph is given and the weights of the
edges are also given but here two edges
are not having their weights if I take
only these edges which are having a
weight they are forming a spanning tree
of a graph just hide these two edges it
becomes a spanning tree now the question
is what could be the minimum values of
these two edges what could be the
minimum possible value maximum it can be
anything but at least what could be the
value see as this is included in a
spanning tree this is included in a
spanning tree this is not included
because it is forming a cycle so it is
forming a cycle if it is included this
will form a cycle so it may be
considered after selecting these two
after selecting these two so the weight
of this could be
four right first this is selected then
this is selected then this is not
selected means definitely it is four if
it is less than four then that would
have been selected first right so it
came later so it is forming a cycle so
it is not taken then this four is taken
then this four is taken this five is
taken so then what could be the minimum
weight of this one so it is not selected
at last it is left over means minimum
weight of this one could be six so this
is four and that is
six so if any missing edges are there
you can find out these type of problems
we find in examinations so some missing
edges you can find out so if you know
spanning tree you can answer this type
of question let us take this example and
let us find out spanning tree for this
one minimum cost is spaning tree so if I
follow crysals method so first I will
select the minimum cause Edge this Edge
I have selected then the next minimum is
this three and that three so I can
select anyone so I'll select this one
first this selected next I'll select
this one so is it forming a cycle
inclusion of this one no so I'll select
that one then which are the edges four
and four these two are there so I can
select anyone so I'll select this one
whether this will form any cycle no so
total how many edges I have selected 1 2
3 4 and total how many vertices are
there five vertices are there so four
edges are selected that's how I got a
spanning tree so what is the cost of the
spanning tree 2 + 3 + 3 + 4 and this is
12 spanning tree is a minimization
result so definitely there will be only
one result so for a problem there can be
only one optimal solution so we should
have exactly one spanning tree only
there cannot be more than one spanning
tree right but in this example you can
see instead of taking this
four this Edge I can take this four
also now also it's forming a spanning
tree yes so I can select one more but
what is the cost cost is 12 so cost is
only one the optimal cost is 12 only you
will get definitely only one answer in
the minimization OR maximization problem
but for that answer the set of input may
be changed
so either you can include this four or
this four so total how many spanning
trees are trees are possible two
spanning trees are possible but what is
the minimum cost that is 12
Weitere ähnliche Videos ansehen
Prim's Algorithm - Implementation in Python
W6L1_Union Find Data Structure
Algorithm Design | Approximation Algorithm | Traveling Salesman Problem with Triangle Inequality
Introduction : Emergence of Connectedness
Spanning Tree Protocol - N10-008 CompTIA Network+ : 2.3
AQA A’Level Relationship between trees & graphs
5.0 / 5 (0 votes)