Prims algorithm | MST | Code implementation

Рет қаралды 137,938

4 жыл бұрын

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/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL VIDEOS:-
Disjoint Set (Simple): • Disjoint Set | UNION a...
Disjoint set UNION by RANK and Path Compression: • Disjoint set UNION by ...

Пікірлер: 174

@kashishjain3179 2 жыл бұрын

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 2 жыл бұрын

Welcome 😊

@mahadevsai3748 3 жыл бұрын

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 3 жыл бұрын

❤️

@user-nm4vn9tq5o 2 жыл бұрын

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 😂

@rupaksarkar4600 Жыл бұрын

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

@techdose4u Жыл бұрын

Welcome :)

@lingyunsu5207 2 жыл бұрын

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

@avidlearner7393 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

Welcome 🤗

@suvamgupta2914 3 жыл бұрын

💯 true

@mainakmondal5228 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

Welcome :)

@nishidwivedi1308 8 ай бұрын

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

@vasudevrao1434 3 жыл бұрын

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

@mdrafiqulislam8233 2 жыл бұрын

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

@assemmedo8 9 ай бұрын

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

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

@DarkUnknown7 3 жыл бұрын

You helped a lot ! Appreciated !

@techdose4u 3 жыл бұрын

Thanks :)

@dhanashreegodase4445 2 жыл бұрын

Thanks for such a great explanation. never stop making videos

@heidarsafari4753 8 ай бұрын

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.

@shalinikumari5532 3 жыл бұрын

Great explanation ,amazing process.Very much helpful

@techdose4u 3 жыл бұрын

Thanks

@moeen007 2 жыл бұрын

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

@techdose4u 2 жыл бұрын

Thanks ❤️

@user-pg8wq2pw1f Жыл бұрын

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

@jaskiranmalhotra989 3 жыл бұрын

Best Explaination so far :)

@puneethj9920 3 жыл бұрын

Awesome! Great Explanation👏

@mahipalsingh-yo4jt 3 жыл бұрын

successfully implemented by watching your video. Thanks sir.

@techdose4u 3 жыл бұрын

Welcome :)

@smartwork7098 14 күн бұрын

Beautiful explanation!

@suvamgupta2914 3 жыл бұрын

Thanks for making these videos ❤️

@sejalrai30 Жыл бұрын

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

@ABHISHEKKUMAR-wc9ke 2 жыл бұрын

best explaination on youtube

@techdose4u 2 жыл бұрын

😊

@sujoyseal195 3 жыл бұрын

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

@ranjanreddy623 Жыл бұрын

This explanation deserves more views😍😍

@prateeksinghal630 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

Thanks :)

@prateekjain7623 3 жыл бұрын

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

@amanbhandari349 3 жыл бұрын

Best channel ever seen for ds algo . ❤❤❤

@techdose4u 3 жыл бұрын

❤️

@asifiqbalsekh 2 жыл бұрын

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 :)

@impatientgaming9868 6 ай бұрын

Good explanation!!!

@Thoughs_05 3 жыл бұрын

Great I understood everything thanks bro

@techdose4u 3 жыл бұрын

Welcome :)

@nonpreservative8354 3 жыл бұрын

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

@surajmaity6194 Жыл бұрын

THANK YOU SO MUCH

@nishithramanuj509 2 жыл бұрын

Superb explanation sir

@kunalsoni7681 4 жыл бұрын

Nice explanation 😊 thanks for to making graph series

@techdose4u 4 жыл бұрын

Welcome

@surajtopal9940 3 жыл бұрын

thank you so much sir :)

@techdose4u 3 жыл бұрын

Welcome

@user-sz2sl6lo2m 2 жыл бұрын

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

@kongzilla2897 3 жыл бұрын

Thank you so much :)

@techdose4u 3 жыл бұрын

Welcome :)

@tsupreetsingh 3 жыл бұрын

very clear and concise !

@techdose4u 3 жыл бұрын

Thanks :)

@varnittyagi2693 3 жыл бұрын

Great Explanation

@techdose4u 3 жыл бұрын

Thanks

@067_prahladmondal7 2 жыл бұрын

great explaination vaiya!

@liquidred257 3 жыл бұрын

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 2 жыл бұрын

Yes , right

@siddharthpunmiya2744 3 жыл бұрын

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

@satishshingade8514 3 жыл бұрын

you are amazing !!!

@techdose4u 3 жыл бұрын

Thanks :)

@RahulGupta-xg6vs 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

Nice :)

@impatientgaming9868 6 ай бұрын

Good one

@mohitkamal4864 4 жыл бұрын

Excellent one🤩🤩

@techdose4u 4 жыл бұрын

Thanks :)

@manikantabandla3923 3 жыл бұрын

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 3 жыл бұрын

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

@ayyappareddy4461 3 жыл бұрын

Thank you very much sirrrrrrrrrrr

@techdose4u 3 жыл бұрын

Welcome bro :)

@divanshmahajan1769 4 жыл бұрын

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

@theprofessor1663 3 ай бұрын

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

@venuvenu2719 4 жыл бұрын

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

@ujeshnada7281 3 жыл бұрын

Best video of MST....

@techdose4u 3 жыл бұрын

Thanks

@relaxthegamer Жыл бұрын

Love u bro

@bunnyrabits 4 жыл бұрын

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 7 ай бұрын

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?

@kunalpatidar2849 3 жыл бұрын

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)

@arpanbanejee5143 2 жыл бұрын

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 2 жыл бұрын

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

@yihongliu7326 2 жыл бұрын

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

@souviknandi9298 3 жыл бұрын

nicely explained

@techdose4u 3 жыл бұрын

Thanks

@mdizrail792 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

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

@hemanthch8155 3 жыл бұрын

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

@Mauglus 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

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

@bunnyrabits 4 жыл бұрын

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

@rakeshsinha9541 4 жыл бұрын

Thanks

@techdose4u 4 жыл бұрын

Welcome

@motivation_hubPJ 3 жыл бұрын

can we use priority queue to get next min node ?

@techdose4u 3 жыл бұрын

Yes

@MAHMOODAHMAD-nr4wo 3 жыл бұрын

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 3 жыл бұрын

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 3 жыл бұрын

@@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 3 жыл бұрын

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

@software3089 Жыл бұрын

Can someone provide the same code of adjacency list?

@saranyas7629 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

I am making a come back in August challenge :)

@saranyas7629 4 жыл бұрын

This is great news

@techdose4u 4 жыл бұрын

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

@sainikhil956 3 жыл бұрын

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?

@vamsia5543 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

Yea. It will soon come.

@AbhishekRaj174 2 жыл бұрын

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

@ayushgarg5929 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

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

@ayushgarg5929 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

You mean for disconnected graph?

@ayushgarg5929 4 жыл бұрын

@@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 4 жыл бұрын

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.

@VivekJaviya 4 жыл бұрын

which software you use??

@techdose4u 4 жыл бұрын

Wacom pro inkspace sketch.io

@supernova7870 4 жыл бұрын

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

@techdose4u 4 жыл бұрын

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 4 жыл бұрын

@@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 4 жыл бұрын

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

@supernova7870 4 жыл бұрын

@@techdose4u okk sir.

@shaswatdas6553 3 жыл бұрын

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

@aryanraju2544 3 жыл бұрын

exactly i am confused as well

@shyamsingharoy4853 Жыл бұрын

How to find cost bro

@mddilshadalam8561 3 жыл бұрын

in which software do you write like this ?

@mddilshadalam8561 3 жыл бұрын

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

@psgoat1111 3 жыл бұрын

Sublime text it is..

@mddilshadalam8561 3 жыл бұрын

@@psgoat1111 not about editor ( code writing stuff)

@AyushGupta-kb9iv 4 жыл бұрын

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

@antimony0004 3 жыл бұрын

share adjacency list code also

@kunalsoni7681 4 жыл бұрын

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 4 жыл бұрын

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 4 жыл бұрын

@@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 4 жыл бұрын

@@Amit_Kumar_1999 thanks for sharing your suggestions 😇

@techdose4u 4 жыл бұрын

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

@kunalsoni7681 4 жыл бұрын

@@techdose4u okay sir 😊 thanking you

@abhishekdasgupta1679 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

Please explain your doubt

@abhishekdasgupta1679 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

@@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 3 жыл бұрын

@@techdose4u finally understood, thanks bro

@techdose4u 3 жыл бұрын

Welcome :)

@tatu_indranil 2 жыл бұрын

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++ 😅😅

@avinaba_mazumdar 3 жыл бұрын

Wait you from Durgapur?

@techdose4u 3 жыл бұрын

Yes right :)

@avinaba_mazumdar 3 жыл бұрын

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

@nikhilbalwani5556 3 жыл бұрын

are you from NIT durgapur?

@techdose4u 3 жыл бұрын

Yep

@nikhilbalwani5556 3 жыл бұрын

@@techdose4u placed?

@techdose4u 3 жыл бұрын

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

@nikhilbalwani5556 3 жыл бұрын

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

@techdose4u 3 жыл бұрын

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

@b.sainathreddy4567 3 жыл бұрын

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

@shaswatdas6553 3 жыл бұрын

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)

@farhanbajwa4954 6 ай бұрын

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.

@dashrathyadav1476 4 жыл бұрын

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 4 жыл бұрын

True.

@willturner3440 3 жыл бұрын

Any body here for cc long 😂

@shubhampatil2777 2 жыл бұрын

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