Prim's Algorithm Minimum Spanning Tree Graph Algorithm

/ tusharroy25
github.com/mis...
github.com/mis...
github.com/mis...

[@pranavganorkar2379]

for those who came for details for min binaryheap from tushar's dijkstra algorithm video, watch from 1:15 to 5:55. cheers !

[@NohandleReqd]

Now this is some helping out!!!

[@PROcrastiDRIVESVofficial]

You can really teach. Thank you for all your hard work. You're the exact opposite of all those professors clogging up the halls and offices at uni, because you can actually make this stuff easy to understand for human beings.

[@JAlternative106]

Your explanations of these graphing algorithms by far the the most thorough and clear. thank you so much for doing these.

[@HemantKumar-cb2uz]

the ease and confidence in the voice adds clarity to the solution, i like it

[@ameyapatil1139]

You are the boss ! I simply love your tutes !

[@nicholaslarovere6037]

Very well done - I appreciate your pacing throughout the lesson. You start the video building the foundation we need to then understand later parts of the lesson - that is key!

[@akashnayak3752]

from the last 7 days was stuck with a particular doubt. Was losing my mind over it! 7 mins into the video and my doubt is cleared. Thank you so much. May the Gods bless you.

[@ManojSingh-eu1js]

Sir, You are an excellent teacher and a wonderful person to help a lot of needy ones like me here. Thank u so much. Please keep up the good work!

[@karansaxena4422]

Hi Tushar, hats off to you for investing so much of your time in this channel! This helps a lot of people!

[@shaunakchadha4961]

You are one of the best Data Structure teachers............Far better than the ones in our college

[@gauravsrivastava9428]

Thanks for the great explanation. One point which is not mentioned in the video is that this is eager implementation of Prim's algorithm. There exists a lazy implementation of prim's algorithm with a different implementation. However, the basic idea remains the same.

[@mirahmed5023]

Neat, clear and thorough presentation. I am certain that you are helping a good chunk of students who do not get enough from their professors' lectures. Thank you and keep up the good work (y).

[@mirahmed5023]

+Tushar Roy btw Tushar, it would be very helpful if you could do tutorials on sorting algorithms, especially the advanced ones such as quicksort, mergesort, shellsort.

[@amirthakatesh6360]

Thanks a ton!! All your videos are extremely helpful ,especially before exams! Upload more videos as much as possible, you make things look so simple and easy.

[@FarhanMohammedKN]

Thanks for the video, Awesome explanation

[@tommyw5332]

I may be mistaken, but I think the operation while he's visiting C and replaces the AB edge of cost 3 with the BC edge of cost 1 is incorrect. Again, I may be mistaken here, but I was under the impression you have to compare the cost of the edge (BC: 1) with the total cost to get to the edge from A (AD: 1 + CD: 1 = 2), or 2+1 = 3, and since 3 is not less than the current value stored, B's path to edge (AB: 3) is not overwritten. I think what was done here in this specific case (just the CB edge, not the rest), was similar to how edges are selected for Kruscal's algorithm. BC is still a valid edge of one of the MSTs of this particular graph, but what I'm saying is the reasoning of WHY the decision to replace AB with BC was incorrect under Prim's algorithm. In other words, with his reasoning, if the edge BC was weighted 2, he would have still selected BC as the new edge to get to B from A, which would have resulted in a non-minimum spanning tree (ADCB: 1+1+2 = 4 vs AB: 3).

[@NohandleReqd]

Hey man. Yours are some of the best and simplest videos for these weirdly complex data structures. Keep up the good work. Also, as you are handling complex stuff, could you start making videos for different complex Dynamic Problem? It will be a great help.

[@TheAmonkeys]

Your tutorials and explanations are awesome, keep it up!

[@dance2die]

Thank you, Tushar. The explanation was nice and clear.

[@AakankshaDevgan]

You teach unbelievably well! Perfect!

[@saitaro]

Your videos are really helpful. You got talent for this stuff.

[@KirubaEbenezer]

Saving me in exam time... For placement preps it is very useful... do more videos as much you can... lol

[@nancyhada4480]

You are really an amazing teacher.

[@pradyumna27]

Appreciate your efforts. Thank you for the video. It helped allot.

[@Dule43]

Than you vary much for this video. You helped me a lot to understand this algorithm!

[@vigneshwarp3462]

Nice explanation Tushar.. Thank you very much.

[@zishunokia6233]

Fantastic Explanation! Best i have seen on youtube... Keep it up... Waiting for more uploads.. Thanks

[@amith89rm]

Hi Tushar, Thanks so much for your videos. Keep these videos coming. It helped in understanding algorithms so well. I used to spent lot of time to understand algorithms but your videos helped me in understanding in less than 20 mins. Thanks so much for the videos. I did feel you are talking a little faster but i changed the video playback speed :) Cheers!!!!

[@ningwang8077]

Very very clear, Oh you do a great job!

[@sahildhawan22]

I now type algo name Tushar Roy in KZbin search bar for my exams! :) But plz see my doubts in your DP videos.

[@hemanshu0503]

@Tushar It looks like the space complexity should be O(V) as we're only going to store a single edge per vertex, did I miss anything?

[@user-jo2eu3wu1g]

Really great explanations. Thanks!

[@bogdanboariu9107]

Great videos ! Thanks for the explanations !

[@diogodias2634]

mate because of you i could do one problem at university, thank you and good luck :-* (sorry for the bad english, not my native language)

[@ganapatibiswas5858]

Great lesson

[@shreyassingh6203]

Hey Tushar, At any points we are only storing V vertices and V edges. So space complexity is O(V) not O(E+V). Think and you will realise. Ps- We are always storing V edges and never storing E edges. |E| can be O(V) in special cases but still space complexity remains O(V+E) = O(V). For |E| of order O(V^2) we are only storing V edges, so space complexity remains to be O(V). Give it a thought, and you will get it. Map of result has V keys, Heap + Map will have at most V nodes, and result list will have V-1 edges. Its all V edges + V vertices.

[@yifeigong135]

Thank you so much Tushar!

[@yashkant559]

Appreciate your efforts!....great one.... :)

[@saikirankolusu6165]

Thank u sir for all u'r videos we are getting so much of knowledge about the subject.i want skip list information, program.

[@vikramadityakukreja4795]

As someone who doesn't use c++ for competitive, Tushar's java code is extremely useful :P

[@WorldOfPersianDoc]

thanks a lot for your good explanation.

[@madhukiranattivilli2321]

Should use D-ary heap instead of Binary heap w/ Prim's MST algo. D is tree order (i.e. max # of children of any node). D=log2(V) (D=E/V is another way, but log2(V) gives better performance). removemin and decrease are the 2 prominent OPs among which decrease is more frequent (O(E), removemin at O(V)). decrease causes swim whereas removemin causes sink. swim causes comparison b/w a node with it's parent, all the way till the root if required, whereas sink causes getting the smallest among all children and comparing that with the node, all the way till final level if required. So swim performs better with D-ary heap whereas sink performs better with binary heap. But since swims are more frequent than sinks, D-ary heap has to be used with D=log2(V) to strike a balance in the performance of sinks and swims. sink and swim run in O(log2(V)) time with binary heap. With D-ary heap they run in O(log(V)) time =~ O(log(V)) time

[@aviralruhela5389]

THANK YOU !!!!!!! Got it all in first time!

[@mrinalmandal914]

bro u are just awesome, keep it up , plz upload more videos

[@aayushtakkar7871]

Thanks .. best lecture representation..!

[@ianpinero9773]

Thank you so much Tushar :)

[@warAlgorithmm]

perfectly explained!!..thank you

[@mukundsridhar4250]

Brilliant as usual.

[@aadil4236]

Nice explenation. I think kruskal algorithem for MST is way simpler.

[@muhammadatharkhan8695]

Amazing explanation ! :)

[@anandzutshi357]

Hi! Really enjoyed your tutorial. Would be great if you could upload videos on graph colouring problems.

[@saadnnoor]

your tutorials are pretty good :) please upload your tutorials on Number theory :)

[@nithyasundar84]

Tushar.. Do we really need resultList as the vertexToEdge map itself holds all the edges required for the result? Can the vertexToEdge map acts as the result set?

[@varun5413]

nice explanation

[@kumarsahastranshu6647]

very nice....!!

[@nishpatwa007]

Hi, I have one question Instead of storing the edges in the result set can't we just print the values of hashmap at the end to print the result ,since the values will be overridden whenever there is an update of weight?

[@lokeshaggarwal5129]

bhai aap great ho!!!!

[@troysincomb]

It's faster to just trace the smallest immediate edge for a test. This is just what the algorithm has to do.

[@timetraveller3647]

no

[@vaibhavkumar903]

Shouldn't the order be ['AD', 'DC', 'CB', 'CF', 'FE'] where CD->DC ,BC->CB, EF->FE. he started with ( smallest element in dictioary+visited vertices) but later he changed the order. Correct me if i'm missing anything here

[@ayushmalpani8865]

Thankyou for the video!! Can you please upload the link of how to construct heap + map datastructure in c++ . I am not able to find it.

[@weiak11]

This one is great

[@ankitdulani]

what would be the cost of traversal for 9 or 10 as once a person has reached B node it need to return to C so that it could traverse further

[@ankitnegi5820]

mast..

[@karthiksar1]

Hi Tushar,Really loved the way you explained!!!In binary heap of ur code,i have a doubt,wen you update NodePosition map,y dont u update allNodes position.Because in few areas of your code you take node depending on postion from map.

[@MrRys]

shouldn't the decrease function work so that decrease(f,2) would subtract 2 from (f,7) and reposition it's location in the tree? so instead of repositioning (f,-2) as is in the video, it should reposition (f,5)?

[@dipal042]

Excellent explanation! Keep it up. If 2 edges are found with same weight , which edge should I choose? After Step1, Can I choose edge BD instead of edge AB?

[@priyaranjansingh6814]

A graph can have more than one minimum spanning tree. So, while traversing in the graph if you will find two edges of same weight then you can choose either first one or second one. Output will result in two different minimum spanning tree.

[@divyanshupreti3434]

Awesome!

[@Austin-hm6qq]

Thanks man!!

[@marcusaureliusfanboy]

At 2:07,I see why contains() is O(1). But why is findMin() O(logN).Shouldnt it be O(1) since you can directly access the heap root in O(1). Correct me if I am wrong.

[@marcusaureliusfanboy]

I see where I went wrong. For anyone having the same doubt,peeking the min value i.e just reading the min value takes O(1). But in extractMin(),the min element is not only read but also removed from the heap,so readjusting the links in heap takes O(logN).

[@aishwarysingh6277]

while calculating the cost of the path you are ignoring the weight of the node

[@MessiLionel123]

the complexity of heap contains is O(n) as it needs to search all elements.

[@chuxv]

+Lionel Messi a MAP is used to speed up that operation at the cost of space. MAP stores key => position , HEAP is implemented using an ARRAY, meaning, it takes almost O(1) (depending on the quality of your HASH FUNCTION) to find an element (and thus the position in the ARRAY), from there is O(1) to get the element from the HEAP since you already now its position. This implementation achieves good speed at the cost of waisting a los of space: Graph (adjacency list): O(V+E) Heap (array) = O(V) + Map (HashTable) = O(V) MST List of Edges = ~O(V) MST Map = ~O(V) As you can see, for a 40MB graph we are looking at a very expensive implementation in terms of memory allocation. Time also gets a huge hit on performance. Think of it this way: it is not the same looking for a shoe in a house than looking for it in a Football stadium. Now, since he is using java, think of the garbage collections (which are blocking calls). If you use a lot of space it will be reclaimed sooner or later (most likely sooner). All in all, time complexity is very relative when you do not understand the big picture.

[@MessiLionel123]

+Chucho Valladares Excellent thanks for the clarification :)

[@MessiLionel123]

+Tushar Roy Keep up the good work bro.

[@sakinafatima]

thankuuuuuuuu

[@akashkalia6623]

How the vertices and edges of graph is used to construct Minimum Heap ?

[@leozilla]

you where talking a little faster than in your other videos, for me it was a little too fast, pls slow it down a bit next time

[@jawwadismail9419]

Y don't u use playback speed option 😀

[@harshitagarwal5188]

if we are implementing this in c++ then i think it would be better to use STL set instead of STL priority queue since when we gonna be updating the edge in the priority queue first we need to erase it and then insert it again and since priority queue doesn't have erase method but set has , it would be better to use set. i am a novice, please correct me if i am wrong.

[@chanlongtieu5297]

Why do you extract F after B is all checked?

[@BrewingHappinessrocks]

oky thank you and if we are simply given a que to solve a spanning tree which is directed ..so which method to use ?

[@ritesh4165]

Sir how can we impliment decrease key operation in priority queues in java .......as heaps can also be created using priorityqueue in java

[@adityabharadwaj2049]

I love you bro.

[@paolocarroll2915]

what happens when u try to extract min and there are two with the same value

[@suhasnayak4704]

In Binary Heap implementation, for node class he has used weight. Can anyone tell me what is the purpose of using weight attribute for node class ?

[@roxtriv]

Why would it use O(V + E) auxiliary space? Heap would have maximum V vertices and map would store only 1 edge per vertex(the edge with minimum path to that vertex).

[@just_browsin]

somebody please explain this. I was thinking the same thing Heap has at most V space , map would be same thing. In the arraylist where you store the minimum edge that contributes the vertex that is V space as well and the answer array is at most V space as well right? because it's a minimum spanning tree so you're only going to have the number of edges needed to connect all the vertices which can't be more than the number of vertices so V again...so 4V in total so O(V) space seems correct. Somebody tell me why I'm wrong

[@elllot_]

It's because you have to store the weights some how and the only way to do so efficiently is to generate a hashmap of each weight. Also you would need to keep track of the connectivity (adjacency) list of each node so doing which basically outlines all edges.

[@gauravseta]

where is binary heap video on your channel? I dont find it anywhere in any of playlists .

[@szabyka16]

Ty :D

[@RahulRajav]

Thank you very much sir for your tutorials,the way you explain is really nice but i request you to suggest me source from where i should study java so that i can be able to implement these graphs logic using predefined function P.S-I know collection framework,but not method such as getAllVertexForEdge()

[@RahulRajav]

I thought those are predefined method and i don't know.well,thank you very much sir

[@AP-eh6gr]

+Rahul Raja use JgraphT library

[@AhmadAwais]

Can you check if the formulae you had for children and parents were right? Coz. in Binay Heap this is how I implement it. - Left child: 2 * i - Right child: 2 * i + 1 - Parent: i / 2

[@adityamittal4357]

His formulae are right. So are yours. It's because he started the index of root node at 0 and you started it at 1. The formulae depend on how you index.

[@puchob2]

excellent explanation, too bad that priority queues does not exist in C#

[@infotechagentdotcom3070]

Thank you boss! You are good. what if i want an interface to display the graph, as input and the output will also be displayed in form of graph (to solve general problems) with each of the iterations (with table displayed). How can this be implemented using java. Thank you

[@cch8155]

Tushar Roy your video is great! i learned a lot! but i have a question. why is the time complexity for the heap 'contains' operation O(1)? i guess we need to loop through all the map and check if 'B' contain in the map... is not that O(n)? thanks

[@cch8155]

thanks~

[@cch8155]

btw do you know how to solve traveling sales men with branch and bound? thanks i know how to solve it by dp but it take too many space if i have 25 cities . thanks a lot!

[@sakshamagarwal8244]

Why is the complexity not VlogV?

[@shivamkanodia384]

can you please write complete implementation of priority queue with decrease key operation?

[@jacksonarnold96]

when do you insert things into the binary heap

[@gursharan749]

how edges are stored in graph?

[@susanladart4607]

Your implementation does not give a MST for the following example. Every time you add a vertex (using min heap), your algorithm does a BFS only on one vertex. But instead, you should do a BFS on all the vertices of the intermediate MST. For e.g. if AB = 2 (instead of 3), BD = 4 (instead of 3) and DC = 3 (instead of 1), your implementation would still give the same result which is AD, CD, BC, CF, FE (length = 11). However, the correct solution is AD, AB, BC, CF, FE (length = 10) which is the MST.

[@ChandraShekhar-by3cd]

Sir Where can I find the Code for Prims Algorithm using C++ STL?

[@anubhavanubhav7651]

great exPL!

[@BrewingHappinessrocks]

is the process same for directed graphs?

[@conradosanchez7332]

The source code on GitHub called primMST is missing a couple of class source code files such as Edge, Graph, and Vertex. Where are they?

[@tushar.bansal_]

here it is- github.com/mission-peace/interview/blob/master/src/com/interview/graph/Graph.java

[@yashmittal6353]

how does this algorithm avoid cycle?

[@sonudoo]

Is there any way to implement maps in C?

[@marriagedance8657]

Why does extract min takes O(logn) time ? We only need the first element of the heap, so shouldn't it be O(1) ?

[@MrRounaksoni]

After extracting minimum element, it disturbs the property of minimum heap. So we have to call heapify function which takes O(logn) time to convert it into minimum heap.

[@marriagedance8657]

@@MrRounaksoni yup, got it. Thanx bro :)