YouTube Instagram TikTok How it works FAQ

The fastest way to turn talking videos into clean, searchable text. Free, private and no account required.

About

Built by Rishav Raj with one goal: free transcripts for everyone.

rishav@yttotranscript.com

Transcribe

YouTube to text
YouTube with timestamps
Instagram Reels
TikTok videos

Learn

How it works
FAQ
YouTube transcripts guide

More

Chrome extension
Contact
Privacy policy
Terms of service

© 2026 YTtoTranscript. Made for creators & researchers.

Not affiliated with YouTube, Instagram or TikTok. Respect creators’ copyright.

Lec 23 Prims Algorithm — Transcript · YTtoTranscript

Home/Transcripts/YouTube

YouTube Transcript

Lec 23 Prims Algorithm

NPTEL - Indian Institute of Science, Bengaluru · 2,701 words · 14 min read · EN

Watch on YouTube

Share X LinkedIn WhatsApp

Below is the complete, readable transcript of Lec 23 Prims Algorithm by NPTEL - Indian Institute of Science, Bengaluru on YouTube. Read the full text, copy any part you need, or generate a transcript for any video with our free tool.

namaskara in this session We Begin our discussions on algorithms for finding minimum spanning trees in the past sessions we have seen the algorithms for single Source shortest path problem and all pair shortest path problem they were all working on directed graphs all our minimum spanning tree algorithms are going to work on undirected

unconnected graphs so let GB a connected undirected graph this is Edge weighted each Edge has got a weight and weight of an edge is denoted by W of e as usual W of e could be arbitrary it could be positive negative zero any value we put no restriction on uh the weight and the weights are

arbitrary real numbers for all practical purposes we can take them to be arbitary integers your tree is a connected acyclic graph the basic definition of a tree a tree is said to be a spanning tree for a graph if vertex sets are identical you can see that V and V Dash the vertex set is same

the Ed set is a subset of e vertex set is same so you are given a G let us say A B C D E F let's say this is the graph G with the same set I'm going to use a subset of edges to build the tree okay so for example at a I can

connect with b b with c b with e b with d e with f these edges this is a subset of edges therefore this is a spanning tree you can see that edges of te are edges of G so it is a spanning tree now weight of a spanning tree how do we Define a weight or what is known

as the cost of a spanning tree is some of the weights of the edges found in that uh tree add all the edge weights you to get the cost of the spanning tree minimum cost spanning tree usual definition there may be several spanning trees we are interested in that spanning tree which has got a minimum cost so

Transcribe another video

Paste any YouTube, Instagram or TikTok link to get a free transcript.

Free · No sign-up · Unlimited

Add to Chrome — transcribe in one click

weight of T is less than or equal to weight of T Das for any spanning tree T Dash okay you take any spanning tree its cost will be equal or more that means the tree that we have is minimum cost spanning tree or minimum spanning tree minimum spanning some books will use minimum cost spanning tree most

books use minimum spanning tree we follow the terminology of minimum spanning tree so we have to find an algorithm efficient algorithms for finding the minimum cost of spanning tree there's one interesting property uh of the MST if all Edge weights are distinct there will be only one minimum cost to spanning tree otherwise there can be

several minimum cost spanning trees if the edge rates are distinct there'll be only one minimum spanning tree which is yeah only one minimum cost of spanning tree so we assume without any loss of generality that all the edge weights are distinct now we will see certain properties of uh spanning trees in general a

tree is a connected a cyclic ground that means it is minimally connected you remove any Edge the tree breaks into pieces it becomes disconnected and there are no Cycles because there are no Cycles you take any two vertices in a tree it is connected therefore there is a path and there's only one path if you have multiple paths

they may enclose a cycle therefore between every pair of vertic is there exist only one path in t there exists a path and that will be the only one path okay you cannot have two different paths if they have that will enclose a cycle which is contradiction to a cyclic property that is the reason why it is

minimally connected every tree has got n minus one edges where n is the number of vertices a tree with n vertices there are several configurations of the tree but all the trees will have exactly nus1 edges if we have a tree and suppose we add a non- tree Edge so here is a

picture the tree need not be

binary suppose I add a non- tree Edge this is U this is V let us say between u and v there is a unique path that path plus this Edge is going to form a cycle in general if there is a path and if you add an edge it forms a cycle right so here is a

cycle this is the cycle that is uh formed so I can give a label and uh remove

this for example if this vertices are called A B C D E F G H I J K L something like that so U to B to a to c to e to G to V to U this is a cycle the tree has a path and you have added an edge the path and an edge will

form a cycle unique cycle there will be only one cycle that is created now in this cycle if you remove any Edge again another spanning tree gets created because the cycle is broken for example if you remove the edge C okay let me see whether I could do that ah if I remove the edge

C UV is included UV is added this another spanning tree why this is a tree now you see there is no disconnection it is a cyclic there was a cycle and an edge in that cycle is removed because an edge in the cycle is removed it doesn't get disconnected and the graph again becomes a cyclic so this

is a cyclic connected off therefore this is a tree this is a spanning tree because it has got all the vertices so you can take a spanning tree T add an edge e remove an edge e Dash you call that as T Dash what is that edge e Dash e Dash is not any any

Edge e Dash is an edge in the cycle created by adding e to T when you add e to t a cycle is created e Dash must be one of the edges of that cycle if you remove any other Edge the cycle still will remain that's not the idea so we need to

remove an edge of the cycle any Edge in that cycle can be removed the cycle is broken the connectivity is there so you get T Dash T Dash is also a spanning tree if T is a spanning tree the T Dash con instructed in this way is also a spanning tree now how are

the weights related it's very simple weight of T Das equal to weight of T minus weight of e plus uh sorry plus weight of e minus weight of e Dash you have removed an edge you have added an edge so this weight is added and this weight is removed this is how the weights are

related so from One spanning Tree you can obtain another spanning Tree in this process at an edge and remove an edge in the cycle that is formed you have another spanning tree the cost of the new spanning tree and the old spanning tree is related in this way okay these preliminaries are good enough

for us to begin our discussions on minimum spanning tree algorithm the first algorithm that we are going to look at is designed by Prim so we will take a closer look at prim's algorithm the design of the prims algorithm is is motivated or inspired by certain interesting properties of the edges of minimum cost spanning

tree okay so we'll take a look at the properties and then we go to the design and development of uh prim's algorithm so here is a general property and this property allows us to build the minimum spanning tree uh in variety of ways okay therefore this a crucial and important property and by the

way we are since the vertex set is same as the vertex set of the input graph all we have to do is that build the edge set for the spanning tree okay therefore we will focus on the Ed set of the spanning tree how do I build that edge set there are n minus

one edges that we have to pick how do we pick those n minus one edges that ex it being same all right so here is an interesting uh property we Define a cut as a split of the graph a cut is a partition of the vertex set into two parts a set s and its

complement V minus s when you split the vertex set and if you redraw the graph putting s in one side and V minus s in another side okay this is the original graph let us take again the same graph let's say A B C D E F let us Put A and E in one

side other vertices this is s what is V minus s b uh c d f this is V minus f let us draw the graph now A to B there is an edge a to c there is an edge and B to C there is an edge okay B to e there is an

edge B to D there is an H and D to f there is an h d to e there is an H C to e there is an ed so in this way we are going to redraw the graph putting s vertices in one side V minus s vertices in another side when we do like this

we get what is known as Crossing edges and internal edges BC is an internal Edge b d is an internal Edge a c is a Crossing Edge why it is a Crossing Edge it goes from s to V minus s it's undirected graph you can say that it is going from V minus s to S we will

generally say that it is between s and V minus s all right Crossing Edge means it will have one end vertex in s another end vertx in v minus s other vertices are all internal vertices so let a be a set of edges let a be a set of edges we say a cut respects

a if no edge of a is a Crossing edge of the cut okay a cut respects a if no edge of a is a Crossing Edge in other words edges of a are all distributed as internal edges either it will be internal to s or it may be internal to V minus s but edges of a are distributed

as internal edges no Crossing Edge is in a right such a cut is called respecting cut there can be several respecting cuts for a given a and there are cuts which may not respect a all right so these are all basic definitions and these definitions and structural properties are useful let a be a set of edges of some minimum

spanning tree okay let us assume that we have built the minimum spanning Tree by identifying some of the edges so a is the current set of edges in my hand so a is a set of edges of some minimum spanning tree assume that s v minus s is a cut respecting a and let e be a crossing edge with

minimum weight okay so I have a set of edges a I have a partition S V minus s edges of a are all internal to S and V minus s it's a respecting cut no Crossing edges in a such a cut of course this will have several Crossing edges let e be a crossing edge with

minimum weight each Crossing Edge has got a weight choose e to be that edge with the minimum weight that is called the minimum weight Crossing Edge then a union e is a subset of edge of some minimum spanning Tree in other words I can extend a by including e in fact e is called safe Edge e is

called safe Edge to add to a it is safe to add you still have the property that a union e is a subset of some minimum spanning tree right therefore here is a concrete way to extend a one concrete way is find a minimum Crossing Edge minimum weight Crossing Edge for a cut that is

respecting a then add that edge to a you have a subset of minimum spanning three edges okay A Moment's reflection will tell you that if I could do that n minus one times and keep on adding initially let me have a equal to Mt keep adding edges I'm not mindlessly adding edges I'm adding edges but still I have a set

of edges which are a part of some minimum spanning tree if I could do that n minus one times cardinality of a will be n minus1 and this will be a minimum spanning tree that's it an algorithm is now possible therefore this mathematical property is very important so based on this mathematical property here is the template a model

for all algorithms for minimum spanning tree we will apply this template for Prim algorithm initially a is empty n minus one times I'm going to add edges to a what kind of edge I add safe edges why it is safe a will still be a subset of a minimum spanning tree a will keep

growing but still it will be a part of some minimum when a becomes n minus one it completes a minimum spanning tree because a minimum spanning tree can have only n minus one edges here is a set of n minus one edges which are a part of a minimum spanning tree that means they

Define minimum spanning tree that's it therefore the algorithm is find a cut respecting a find a minimum weight Crossing Edge E A is a union e go back now a is updated for the updated a find a cut respecting a in the new cut find the minimum weight Crossing Edge add that to a now a will

have two edges again go back for the two Edge a find a respecting cut and so on do this n minus one times you have the edge set of a minimum spanning tree okay what is the vertex set it is the vertex set of the graph that we don't have to worry about it that is the

reason why minimum spanning tree algorithms will focus on building the minimum spanning tree Edge by Edge vertex it is fixed okay so initially G equal to v e t equal V A A is empty set then a gets one Edge after another in N minus one iteration finally cardinality of a will be n minus1 at that point T = to VA

will be a minimum spanning tree that is all our plan we will see how this can be implemented okay there are choices so we have to make clever choices all right any cut respecting a we can choose therefore we have to choose the cut in a clever way that construction of the cut

finding the minimum weight Crossing Edge they all can be done efficiently if you work with a complicated cut searching in that working with that could become very inefficient therefore our Focus will be on how are we going to get a respecting cut and once we have a resp cut for a and after adding an edge to a how are we

going to find a new respecting cut for the new a thinking along these lines we are going to build an algorithm and finally those kind of analysis and discussions will lead to the description of prim's algorithm we will see the details in our next session thank you