3.5 Prims and Kruskals Algorithms - Greedy Method

Summary

This 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

00:00

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

05:05

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

10:09

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

15:10

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

Keywords

💡Spanning Tree

A spanning tree is a subgraph of a connected graph that includes all the vertices of the graph and the minimum possible number of edges, specifically, one less than the number of vertices. It is a tree in the sense that it is acyclic. In the video, the concept is introduced by explaining that a spanning tree must include all vertices and edges that connect them without forming any cycles. The script uses examples to illustrate how to select edges to form a spanning tree from a given graph.

💡Graph

A graph is a mathematical structure consisting of a set of vertices (also called nodes or points) and a set of edges connecting these vertices. The script represents a graph as G(V, E), where V is the set of vertices and E is the set of edges. The graph is fundamental to the discussion of spanning trees and is used throughout the script to demonstrate various concepts.

💡Vertices

Vertices are the fundamental units of a graph, often represented by points or nodes. In the context of the video, vertices are the elements that must be included in a spanning tree. The script mentions vertices when explaining the structure of a graph and when discussing how to form a spanning tree.

💡Edges

Edges are the connections between vertices in a graph. They represent the relationships or paths between different points. The script discusses edges in the context of forming a spanning tree, emphasizing that a spanning tree must include the minimum number of edges required to connect all vertices without cycles.

💡Cycle

A cycle in graph theory is a sequence of edges and vertices that starts and ends at the same vertex, passing through other vertices along the way. The video script explains that a spanning tree cannot contain a cycle, as this would violate the definition of a tree structure.

💡Weighted Graph

A weighted graph is a graph where edges have an associated weight or cost. The script introduces the concept of weighted graphs to discuss how to find the minimum cost spanning tree, which is a spanning tree with the lowest possible total edge weight.

💡Minimum Cost Spanning Tree

The minimum cost spanning tree is a spanning tree that has the minimum possible total edge weight. The script focuses on algorithms to find this tree in a weighted graph, which is a key concept in network design and optimization.

💡Prim's Algorithm

Prim's Algorithm is a greedy algorithm used to find the minimum cost spanning tree of a connected, weighted graph. The script explains how Prim's Algorithm works by starting with an arbitrary vertex and iteratively adding the smallest edge that connects a new vertex to the existing tree.

💡Kruskal's Algorithm

Kruskal's Algorithm is another greedy algorithm for finding the minimum cost spanning tree. The script describes how Kruskal's Algorithm works by sorting all edges by weight and adding them to the tree as long as they do not form a cycle.

💡Greedy Method

A greedy method is an approach to problem-solving that makes the locally optimal choice at each step with the hope that these local choices will lead to a global optimum. The video script mentions greedy methods in the context of Prim's and Kruskal's algorithms, which are examples of greedy algorithms used to find minimum cost spanning trees.

💡Min Heap

A min heap is a binary tree-based data structure that satisfies the heap property: the key present at each node is either less than or equal to the keys of its children. The script mentions min heaps in relation to optimizing Kruskal's Algorithm, as they can efficiently retrieve the minimum edge when selecting edges for the spanning tree.

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