Prims algorithm | MST | Code implementation

In this video,I have explained the prim's algorithm which is used to find the minimum spanning tree.I have first explained the intuition for Prims algorithm and then i have shown a simple example.After that, I have shown a proper CODE algorithm using large example and at the end of the video,I have explained the CODE implementation of prims algorithm.I have explained this algorithm in an easy and simple way to follow.This is a greedy algorithm for finding minimum cost spanning tree.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithT...
TELEGRAM Group LINK: t.me/joinchat/...
=======================================================================
CODE LINK: gist.github.co...
USEFUL VIDEOS:-
Disjoint Set (Simple): • Disjoint Set | UNION a...
Disjoint set UNION by RANK and Path Compression: • Disjoint set UNION by ...

[@kashishjain3179]

was having difficulty in understanding prims for a very long but the way you explained cleared all my doubts. THANK YOU SO MUCH SIR

[@techdose4u]

Welcome 😊

[@rupaksarkar4600]

after watching dozens of videos finally i could understand prims .Thanks man

[@techdose4u]

Welcome :)

[@mahadevsai3748]

sir i have joined a course in coding blocks in that prim's algo is unable to understaand ,when i seen this video urs explaintation is 1000 times bettr and best than coding blocks

[@techdose4u]

❤️

[@user-nm4vn9tq5o]

How much was the price of DSA course? And was it worth taking?

[@devrajgoswami4357]

@@user-nm4vn9tq5o bro he literally said he was unable to understand and here you are asking 😂

[@avidlearner7393]

This is so far the best video for Prim's algorithm on KZbin. Thanks for such a great explanation.

[@techdose4u]

Welcome 🤗

[@suvamgupta2914]

💯 true

[@mainakmondal5228]

Concepts are getting clearer day by day from your videos...thank you.

[@techdose4u]

Welcome :)

[@mdrafiqulislam8233]

This is the simplest and easiest video in the internet. Thank you.

[@lingyunsu5207]

Thank you so much! This is the clearest and easiest video for me to understand the algorithm!

[@moeen007]

Love you 3000 brother, I have never been so comfortable learning the DSA. Lots of love ! :)

[@techdose4u]

Thanks ❤️

[@DarkUnknown7]

You helped a lot ! Appreciated !

[@techdose4u]

Thanks :)

[@ABHISHEKKUMAR-wc9ke]

best explaination on youtube

[@techdose4u]

😊

[@nishidwivedi1308]

So far the best explanation that I have come across. Amazing!

[@sejalrai30]

thank you so much you know tht where student get stuck ...its appreciable

[@smartwork7098]

Beautiful explanation!

[@amanbhandari349]

Best channel ever seen for ds algo . ❤❤❤

[@techdose4u]

❤️

[@MeenaMaladugalage]

You have explained it very well .Thank you very much.

[@asifiqbalsekh]

Ab pta nehi sukriya ada kaise kare...lekin ap ne jo effort dala hai isko samjha ne ke liye , hat's off.... Salam apke patience level ko samjhane ke time.... Dil se sukriya....

[@mdaasil2329]

Thanks bro. was struggling to find a proper cpp implementation for past 4 hours!

[@techdose4u]

Welcome :)

[@mahipalsingh-yo4jt]

successfully implemented by watching your video. Thanks sir.

[@techdose4u]

Welcome :)

[@sooraj_sp_11]

thank you so much ,, your efforts gives me lot of knowledge ,, I guaranteed that there will no any video on MST who explains it in such details ....... keep inspiring ...

[@vasudevrao1434]

One of the best resource among all the free and paid courses out there 🙏

[@ranjanreddy623]

This explanation deserves more views😍😍

[@assemmedo8]

Really great explanation, detailed and really makes you know what's happening step by step

[@nonpreservative8354]

Please make a video for Prim's algo using heap and adjacency matrix with time complexity O(ElogV)

[@dhanashreegodase4445]

Thanks for such a great explanation. never stop making videos

[@shalinikumari5532]

Great explanation ,amazing process.Very much helpful

[@techdose4u]

Thanks

[@tsupreetsingh]

very clear and concise !

[@techdose4u]

Thanks :)

[@prateeksinghal630]

Really Awesome Video !! It deserves all the likes !!

[@techdose4u]

Thanks :)

[@heidarsafari4753]

Thank you very much for sharing the code, sir. I could program Prim's algorithm in Matlab and find the MST for my own 480-vertex graph by taking advantage of your code programmed in C++ and your complete explanation in the video. I wish all the best for you.

[@Thoughs_05]

Great I understood everything thanks bro

[@techdose4u]

Welcome :)

[@nishithramanuj509]

Superb explanation sir

[@RahulGupta-xg6vs]

There is no doubts,great..,👌👌👌👌👌

[@techdose4u]

Nice :)

[@jaskiranmalhotra989]

Best Explaination so far :)

[@impatientgaming9868]

Good explanation!!!

[@liquidred257]

The fact that you included a parent array finally helped me figure this out (I think). so the weight associated with a given node is the weight from the parent to the node in question? Which is why node 3, perse, dosen't have a weight of 1?

[@user-nm4vn9tq5o]

Yes , right

[@067_prahladmondal7]

great explaination vaiya!

[@ujeshnada7281]

Best video of MST....

[@techdose4u]

Thanks

[@puneethj9920]

Awesome! Great Explanation👏

[@kunalsoni7681]

Nice explanation 😊 thanks for to making graph series

[@techdose4u]

Welcome

[@surajmaity6194]

THANK YOU SO MUCH

[@impatientgaming9868]

Good one

[@theprofessor1663]

Best 🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻

[@suvamgupta2914]

Thanks for making these videos ❤️

[@sujoyseal195]

In line 46 of your code , during step 3 I think it should be graph[u][j]

[@manikantabandla3923]

Thank you @techdose for creating a playlist of graph algorithms. I think we can implement the prim's algorithm in O(V(logV)) with the use of min-heap. I would be highly thankful to you if u can provide links of Leetcode problems related to every algorithm u are going to explain.

[@techdose4u]

I haven'r researched on leetcode problems for these topic. Once I find leetcode similar problems then I will add to the playlist at proper place.

[@ayonsinha2075]

no It can not be done i.g beacause in distance array we are storing the distance from source to dest nodes... so if herer inthis example shortest distane to reach 0 from 3 is 6 where so it causes problem..because we have to stiore the total cost to traverse the all nodes of graph...if u use djkistra it always add the cost source to destination..so currently we are standing at node it does not matter beacuse if that node could be the parent of target node where we are standing at...then in prims or according to MST we add the distance fom it's parent to the target or adjacent node but in dijsktra it will add up all upto source from parent+dest cost in the main cost...but we can prevent it in one way if we know who is the parent of that target node then we can subtract the cost of source to parent from our total cost but it will make things comlex and I am not sure whether it may work or not to get the proper res ...then we need 0(n) more space

[@surajtopal9940]

thank you so much sir :)

[@techdose4u]

Welcome

[@siddharthpunmiya2744]

Hey In prim why do you need to relax vertex it is a method to find minimum spanning tree by picking up adjacent edges only, not by weight of the vertex

[@varnittyagi2693]

Great Explanation

[@techdose4u]

Thanks

[@souviknandi9298]

nicely explained

[@techdose4u]

Thanks

[@saranyas7629]

I vote for going back to solving August daily challenges from Techdose

[@techdose4u]

I am making a come back in August challenge :)

[@saranyas7629]

This is great news

[@techdose4u]

But the videos may get uploaded the next day due to low processing power.

[@bunnyrabits]

sir can you start a Placement Series , making videos on topic wise questions that you told in the "30 days placement video" , it will be very helpful as we all can follow your videos. If you can a video on per day basis😊. Like if you all agree guys.

[@KeyAndLock77]

Is there one flaw in algorithm that the value[j] should be graph[U][j] + value [U] value[j] = graph[U][j] + value [U]; to correctly update distance from the root node?

[@prateekjain7623]

sir,can we use vetor of vector in pair ?? so that we not to use adjanency matrix to reduce time complexicity??

[@MAHMOODAHMAD-nr4wo]

I think prim's algorithm is much similar to Dijkstra's except for the part where we store processed vertices in the set. This is my opinion. Correct me if I am wrong

[@yuvrajjoshi4893]

No, in Dijkstra's algo you add the (value at the current node + edge weight of the adjacent node to be reached) and if it is smaller than its previous value (at the adjacent node to be reached) then only you update. But in Prim's you don't add the value at the current node before comparing, you simply check if the edge value to reach the adjacent node is smaller than its previous value, and then update if necessary.

[@MAHMOODAHMAD-nr4wo]

@@yuvrajjoshi4893 if we write a code for dijkstra using minHeap (set,priority queue) the code is somewhat similar except for the Operation part which differs in Dijkstra and prims.

[@yuvrajjoshi4893]

@@MAHMOODAHMAD-nr4wo yeah I know that. I was only telling the part where they differ.

[@ayyappareddy4461]

Thank you very much sirrrrrrrrrrr

[@techdose4u]

Welcome bro :)

[@kongzilla2897]

Thank you so much :)

[@techdose4u]

Welcome :)

[@mohitkamal4864]

Excellent one🤩🤩

[@techdose4u]

Thanks :)

[@relaxthegamer]

Love u bro

[@bunnyrabits]

It will be great if you can share some must do questions, topic wise(6-10 Questions) for begginers like me. And again it wiil be great if you make videos on that questions. Thank you

[@divanshmahajan1769]

Plz post solutions of graph problems of hackerrank also ...

[@sainikhil956]

Sir can you please tell what is the use of mst array? i want to know intuition behind it because sometimes we might reach a node in less distance after declaring that mst node true.. and what observations can we make from this algo?

[@শূন্যপথেরবালি]

Which software have you used ( for virtual blackbaord ), It feels so easy to use. And thank you for your nice explanation.

[@satishshingade8514]

you are amazing !!!

[@techdose4u]

Thanks :)

[@hemanthch8155]

It is better to start from Oth node...Coz,If we find Min weight node at the middle it is giving More weighted Output for some trees..

[@venuvenu2719]

Please explain the problem-find the longest path in binary tree

[@arpanbanejee5143]

Thanks for the video!!, I have one doubt here, even if we remove the MST SET from this algo, it seems to be working(in the efficient implementation using Priority Queue) because we are only pushing those vertices in the queue whose edge weight is less than the already existing edge weight at that vertex, so there is no chance we put an already visited vertex because its weight will be the same(1->0 is same as 0->1) So, why exactly do we need this visited(MST SET)? It's the same with Dijkstra, it works even without the Priority queue and visited array( but the Time complexity takes a hit for some test cases). Am I understanding it correctly? Or did I miss anything

[@arpanbanejee5143]

After going through some examples, I can conclude that we need the visited(MST SET) here, but if you ignore the TC, in Djikstra you don't need it, it will fetch u the correct results, but here in PRIMS Algo you will get wrong and. Take this example- undirected graph- 0->1 cost 12 1->2 cost 6 0->2 cost 18 take the corresponding opp edges as well since this is an undirected graph Now, if you remove the visited array, the key[] will look like this-[0, 6, 6] here node 1 is connected to 2 and vice versa, which is not correct. The correct key[] should be-[0,12,6] 0 connected to 1 and 1 connected to 2. Djikstra without Priority Queue and Visited array- Leetcode 1514 class Solution { class Node{ int v; double weight; Node(int v,double weight){ this.v=v; this.weight=weight; } } public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) { // build adjaceny list List[] adj=new ArrayList[n]; for(int i=0;i

[@Mauglus]

What's the difference to Dijkstra? Only that we continue until all nodes are explored?

[@techdose4u]

No. They both have different goals and so, the MST found by Prim's may not have the shortest path between 2 nodes. Read this: stackoverflow.com/questions/14144279/difference-between-prims-and-dijkstras-algorithms

[@rakeshsinha9541]

Thanks

[@techdose4u]

Welcome

[@vamsia5543]

I could implement it without help such a great explaination thank a ton , could u please upload bridges and articulation points

[@techdose4u]

Yea. It will soon come.

[@kunalpatidar2849]

How we know that the parent of node 4 is node 3, it might be 2 because last visited node is 2 ??. (at time 21:00 in video)

[@AyushGupta-kb9iv]

Hello Sir... Please make a video on given Problem... Count the number of subarrays having a given XOR Thank you...

[@ayushgarg5929]

What if all adjacent nodes has same cost...which one we would select ?

[@techdose4u]

Anyone will be fine. It depends on how you choose. In my case, I might choose the node with lower label.

[@ayushgarg5929]

@@techdose4u will this algo work if the graph is not completed. ??

[@techdose4u]

You mean for disconnected graph?

[@ayushgarg5929]

@@techdose4u No...i meant to say if the graph wasn't like all pair of nodes were connected to each other ....then in that case also this algo works. ???

[@techdose4u]

You mean a complete graph ryt. In that case, if you have multiple edges with same values then anyone can be picked and there will be multiple MST possible and anyone will be correct.

[@yihongliu7326]

Thank you for the amazing video! Just q quick question -- why do we repeat (V-1) times? Is it because each time we only connect 1 edge between 2 vertices, and we need (V-1) vertices in total?

[@veera9963]

Because for the last vertice we don't have to search for edge with minimum weight because if we do that then we will get a loop in the tree ... which should be avoided

[@amansahil5721]

because for the last vertices all its adjacent will already be processed

[@mdizrail792]

Sir can we use priority queue for selectioning the minimum edge ?

[@techdose4u]

No. You need to pick adjacent vertices only. In Kruskal's you can use priority queue.

[@motivation_hubPJ]

can we use priority queue to get next min node ?

[@techdose4u]

Yes

[@supernova7870]

Sir, @8:37 what is the logic of expanding adjacently and not randomly, PlZz clear my doubt sir ??

[@techdose4u]

Random expansion is Kruskal's method. Adjacent expansion is based on the idea that we have to connect all nodes to form MST. So there will be only 1 component. Therefore, even if we expand adjacently using greedy approach, it won't matter.

[@supernova7870]

@@techdose4u Sir, if i apply dijistras algorithm on the graph mentioned in the problem and find shortest path for each node from source vertex and take only the shortest path for each node , then sir don't you think it will to form a MST , Sir i was getting a feel that prims uses dijistras algorithm indirectly, that's why iam asking .

[@techdose4u]

Please watch my Dijkstra algo video. You will get this point cleared.

[@supernova7870]

@@techdose4u okk sir.

[@avinaba_mazumdar]

Wait you from Durgapur?

[@techdose4u]

Yes right :)

[@avinaba_mazumdar]

​@@techdose4u oh you studied at DAV, I'm from GTBPS, never checked out your schooling on LinkedIn my bad

[@kunalsoni7681]

Sir please can you solve my doubt 😇 Sir in Findmst() function have two loops Outer loop and inner loop takes v^2 time Sir but every run of outer loop also calling selectMinVertex () also takes linear time as V.

[@kunalsoni7681]

So I thinking that the time complexity should be v^3. but you are saying V^2 time complexity. Sir as we consider time of calling function or not 😇 in our prims algo ? I notice this when I writing code on my notebook

[@Amit_Kumar_1999]

@@kunalsoni7681 This is simple implementation not efficient one. As shown in video that you could use adjacency list for better time complexity (Though I don't think in complete graph it would matter). To optimise it further use priority_queue so that we don't have to scan the entire edge array for the minimum value vertex.

[@kunalsoni7681]

@@Amit_Kumar_1999 thanks for sharing your suggestions 😇

[@techdose4u]

You can use a heap to get O(E log V).

[@kunalsoni7681]

@@techdose4u okay sir 😊 thanking you

[@AbhishekRaj174]

what about findMin's time complexity, isnt that V too, so that would be V^3

[@shaswatdas6553]

Is it only me or it seemed like dijkstra and prims are very similar??🤔 only one line difference in if statement

[@aryanraju2544]

exactly i am confused as well

[@VivekJaviya]

which software you use??

[@techdose4u]

Wacom pro inkspace sketch.io

[@nikhilbalwani5556]

are you from NIT durgapur?

[@techdose4u]

Yep

[@nikhilbalwani5556]

@@techdose4u placed?

[@techdose4u]

Long back. I should say I was from NIT DGP 😅

[@nikhilbalwani5556]

@@techdose4u cool, can i find you on linkedin?

[@techdose4u]

@@nikhilbalwani5556 It should be in the description or else find in description of latest video.

[@software3089]

Can someone provide the same code of adjacency list?

[@b.sainathreddy4567]

selectminv also take o(v) so it should be o(v3) correct me if i am wrong

[@antimony0004]

share adjacency list code also

[@shyamsingharoy4853]

How to find cost bro

[@mddilshadalam8561]

in which software do you write like this ?

[@mddilshadalam8561]

do you write in computer like this or you use touchscreen laptop??

[@orewaluffy-56]

Sublime text it is..

[@mddilshadalam8561]

@@orewaluffy-56 not about editor ( code writing stuff)

[@abhishekdasgupta1679]

can't understand the selectminvertex method properly, someone pls help

[@techdose4u]

Please explain your doubt

[@abhishekdasgupta1679]

vertex = i; minimum = value[i]; } } return vertex; specially "return vertex" part

[@techdose4u]

@@abhishekdasgupta1679 Vertex = i; is used to find the vertex which has minimum value. Minimum is used to find the minimum distance value and store its corresponding vertex in vertex variable. Both should be updated together.

[@abhishekdasgupta1679]

@@techdose4u finally understood, thanks bro

[@techdose4u]

Welcome :)

[@tatu_indranil]

Can someone give me the C code using the same method as I need to implement this in C I understood the explanation but I don't know know much of c++ 😅😅

[@AlanSchooll]

You explained this algorithm wrong, because in prims we look for a next shortest visiting edge not just from a current vertex, but from all the vertex that have been visited so far.

[@shubhampatil2777]

Algorithm can be improved in this way by eliminating that second loop to find out parent (Naming conventions are different here: weights=value, visited=setMST) int findMinAdjacentEdge(int graph[size][size], int vertex,int *weights, bool *visited, int *parents){ int minWeight=INT_MAX, minIndex; for(int i=0;i

[@shaswatdas6553]

INF = 10**12 def pick_min(dist, mstset): min_i, val = min( enumerate(dist), key=lambda x: x[1] if mstset[x[0]] == False else INF) return min_i def prims(edge, V): dist = [INF for i in range(V)] dist[0] = 0 mstset = [False for i in range(V)] parent = [-1 for i in range(V)] for i in range(V-1): u = pick_min(dist, mstset) mstset[u] = True for v, w in edge[u]: if mstset[v] == False and w < dist[v]: dist[v] = w parent[v] = u print('parent,curr,dist: ', *zip(parent, list(range(V)), dist)) V = 6 edge = {} edge[0] = [(1, 4), (2, 6)] edge[1] = [(0, 4), (2, 6), (3, 3), (4, 4)] edge[2] = [(0, 6), (1, 6), (3, 1)] edge[3] = [(2, 1), (1, 3), (4, 2), (5, 3)] edge[4] = [(1, 4), (3, 2), (5, 7)] edge[5] = [(4, 7), (3, 3)] prims(edge, V)

[@willturner3440]

Any body here for cc long 😂

[@HIMANSHUSHARMA-zo2sg]

I think this is djakstra's...

[@dashrathyadav1476]

Bro..plz make ur vdos shorter...I have no issues..but I also want u to get good views...as ppl usually choose shorter vdos..

[@techdose4u]

True.