Kruskal algorithm implementation

Рет қаралды 79,184

3 жыл бұрын

This video covers the implementation of Kruskals algorithm by using an example dry run of the code and finally the code explanation.This video is an extension to my previous video on kruskal algorithm where i had explained the algorithm using example.In this video, i have shown implementation of kruskal algo using disjoint set union by rank and path compression algorithm.In the dry run, i have not explained path compression find algorithm to reduce complexity of understanding.All the related USEFUL video links are present below.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:-
Spanning Tree (MST): • Spanning Tree | MST | ...
Kruskal's algorithm: • Kruskals algorithm | C...
Disjoint Set (UNION/FIND): • Disjoint Set | UNION a...
Disjoint set UNION by RANK and Path Compression: • Disjoint set UNION by ...

Пікірлер: 85

@yashnistane6728 3 жыл бұрын

Most underrated channel! Loved the way you teach!!!

@ashutoshkumar4267 3 жыл бұрын

Thank you for this graph series, its really helpful. waiting for next topics !!!

@techdose4u 3 жыл бұрын

Sure

@eduarddez4416 3 жыл бұрын

Thank you very much , I searched for multiple explanations / code implementations but this was the clearest one. Good job

@techdose4u 3 жыл бұрын

Thanks :)

@shoumeshrawat1362 3 жыл бұрын

Thank you for all your hard work in making these videos

@rajkumarmahajan2527 3 жыл бұрын

great session, flawless communication, easy to understand. Thanks

@techdose4u 3 жыл бұрын

Welcome :)

@HimanshuuSaini 2 жыл бұрын

Awesome Content. Thank You So much.

@abhishekkumarsah1917 3 жыл бұрын

In your github code, in kruskals function you have not updated j pointer(j++) in while loop when the edge doesn't form a cycle. If my right, do correct it in code or if my wrong, please do inform me the reason :)

@VarunKaushal-zx9zq Жыл бұрын

Amazing Session, great job sir!

@ytg6663 2 жыл бұрын

Your straight speech kills me

@techdose4u 2 жыл бұрын

😅

@mdmahedi9414 3 жыл бұрын

This is awesome. Clearly understood the concept and code also. 🧡🧡🧡

@techdose4u 3 жыл бұрын

Nice :)

@ibrohimahmadjonov6859 Жыл бұрын

Good lesson for Kruskal algorithm. Thanks

@omarelnaggar9940 Жыл бұрын

amazing explanation , thx alot

@noobninja4882 3 жыл бұрын

thanks a lot , please continue this graph series

@techdose4u 3 жыл бұрын

Sure :)

@agileprogramming7463 3 жыл бұрын

Wow!! This is awesome!!

@techdose4u 3 жыл бұрын

Thanks agile :)

@yihongliu3850 3 жыл бұрын

thank you! nice as usual

@techdose4u 3 жыл бұрын

Welcome :)

@rajkumarvb2602 3 жыл бұрын

Great sir. It helped me a lot to understand graph algorithms. Thanks for your time and effort sir!!

@techdose4u 3 жыл бұрын

Welcome

@aniketmasram6500 3 жыл бұрын

You explanation is amazing 🔥🎊

@VeraVeraniego 3 жыл бұрын

delightful explanation

@techdose4u 3 жыл бұрын

Thanks :)

@Cloud-577 2 жыл бұрын

thank you soo much!!

@guillem99 2 жыл бұрын

Why don't you increase j on every iteration of the while loop? I'm confused.

@ankitshaw5375 3 жыл бұрын

SIr what if we are not able to push (v-1) no of nodes and we have processed all the nodes in the adj_List??Then it wont be an MST??

@rohitmishra8076 3 жыл бұрын

Thank you so much sir. 🙏🙏

@techdose4u 3 жыл бұрын

Welcome

@AltafHussain-on2oe 3 жыл бұрын

Thank you very much sir.

@techdose4u 3 жыл бұрын

Welcome :)

@GATEPlaylist 2 жыл бұрын

Thanks

@techdose4u 2 жыл бұрын

Welcome 😊

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

Concise presentation!!!

@techdose4u Жыл бұрын

Thanks :)

@ananysharma9290 3 жыл бұрын

First bhai , Love you Bro , Big Fan

@techdose4u 3 жыл бұрын

Thanks

@kunalsoni7681 3 жыл бұрын

Sir really very interesting session 😊 I understand full implementation.. Thank you so much for making videos ❤️😇

@techdose4u 3 жыл бұрын

Welcome

@Johnnysins385 2 жыл бұрын

Thanks sir keep making video and help us

@techdose4u 2 жыл бұрын

Sure :)

@jjbrotherscreation3267 3 жыл бұрын

Good explanation

@techdose4u 3 жыл бұрын

Thanks

@CanalRD Жыл бұрын

I dont get why you point 0 to 1 and 3 to 1 and says that '1' is parent for both 0 and 3. Because 3 is poiting to 1, it means that 3 comes first, so '1' should have 3 as a parent

@shushantgaur9420 3 жыл бұрын

Line 74, along with i++ shouldn't there be j++ as well. Otherewise same values will be pushed back in the vector in the starting.

@siddhantsrivastava7426 2 жыл бұрын

Very nice video ! some good explanation! But just one suggestion you should show the whole code in this video only ...because one may have learnt sets and other concepts from somewhere else! and it is also difficult to merge functions showed in different videos

@prasad.patil12 3 жыл бұрын

This graph series is very helpful could you make one video on resume preparation and personal projects ideas in order to get interview call from companies?

@techdose4u 3 жыл бұрын

Yea sure

@ARSAGAMING69 Ай бұрын

8:25 (1,4,3) 1 having parent 4 4 having parent -1 Then why we haven't consider that edge between 1 and 4 with weight 3 ???

@secretsexp9931 26 күн бұрын

Which mic are u using?

@animeshsahu6267 3 жыл бұрын

@12:20 why are you not doing j++ along with i++ ?

@shushantgaur9420 3 жыл бұрын

I have the same doubt. Along with i++ there should be j++ as well at line 74

@MegaSethi 3 жыл бұрын

there has to be j++

@anudeepreddy6171 Жыл бұрын

there should be ++j;

@Ali-mc4le 3 жыл бұрын

Hi Sir, what tool are you using to draw and write your solutions?

@techdose4u 3 жыл бұрын

Tablet Wacom pro

@Ali-mc4le 3 жыл бұрын

@@techdose4u thank you!!

@mohdkamran530 2 жыл бұрын

@TechDose, My implementation doesn't takes edge(0 to 2), instead takes (2 to 3) and still gives 8 as the minimum cost. I think it depends on the order of edges sorted, both have cost 2. So the edge (2,3) comes before edge(0,2) and gets selected. Is it right? Also, I am using parent array only to check if there is a cycle and working fine. I think using rank will only optimise the solution, right?

@yashikagarg4044 3 жыл бұрын

Which one is better kruskal or prim...please give their comparison

@techdose4u 3 жыл бұрын

I follow kruskal because it's easier to remember 😂

@vasiprashanti Жыл бұрын

Sessions are great! Can I get the code for Kruskal in Java language?

@dysonfilmstw4764 3 жыл бұрын

Can someone share python code for krushkal algorithm using heap?

@ananysharma9290 3 жыл бұрын

Articulation Points dal do Sir

@techdose4u 3 жыл бұрын

I am covering topics step by step. That will be covered after shortest path algos.

@ananysharma9290 3 жыл бұрын

@@techdose4u okay Sir Thanks

@yahyafati 2 жыл бұрын

what is the use of rank here?

@techdose4u 2 жыл бұрын

Union

@vaibhavjain4710 2 жыл бұрын

I think , j++ should be at line number 67 instead of line number 69

@23_vaishnavikarpe55 2 жыл бұрын

When i paste the code it doesn't give output

@farhanbajwa4954 5 ай бұрын

there is a mistake in a code you are increasing j vaiable only inside condition which form infinite loop

@AmarKumar-vo2bv 3 жыл бұрын

Please show Path compression technique

@techdose4u 3 жыл бұрын

Follow disjoint set video union by rank and path Compression. You will get it.

@ravikumarkamble6403 3 жыл бұрын

if we doensnt use rank then?

@ravikumarkamble6403 3 жыл бұрын

? Anyone answer

@Nothing-sj6vb 3 жыл бұрын

if we don't use rank, then it is hard to find the correct parent for a vertex.

@MayankKumar-nn6us 3 жыл бұрын

sir plz provide the answer in python

@techdose4u 3 жыл бұрын

😅 I will try

@chiragtejwani1803 3 жыл бұрын

Please reduce the number of ads they are really disturbing otherwise good video

@raviashwin1157 3 жыл бұрын

Thanks

@techdose4u 3 жыл бұрын

Welcome