G-44. Minimum Spanning Tree - Theory

GfG-Problem Link: NA
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------

[@takeUforward]

Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79

[@KUMARBISHWAJEET-iq6ym]

Understood

[@aaaaz424]

Striver, I dont usually have the habit of commenting on videos, but when I do, it only happens when I appreciate the content a lot. Thanks for this amazing contribution to all the novice programmers for whom graph 'WAS' a tough data structure :)

[@AbhaySingh-fi7lk]

Same here ❤

[@kishanpansuriya7809]

U are more appreciating yourself rather than striver🤣

[@vaidanshkukreja8970]

**IMPORTANT** POINTS FOR MST:
1-> If each edge has a distinct weight then there will be only one & unique MST.
2-> A complete undirected graph can have n^(n-2) number of Spanning Trees. For example : Consider a triangle which have 3 vertices and 3 edges so n=3 || 3^(3-2) => 3. Hence , it would have 3 spanning trees.
3-> From a Complete graph by removing max(e-n+1) edges, we can construct a Spanning Tree.
Hope it helps!!! 😊

[@saurabhsangam2737]

This is the best and the most concise explanation of MST. Loved it ❤

[@vaishnavimore4860]

The way you teach makes me feel every topic is easier✨Thank you striver bhaiyya for making DSA easier for us!

[@debajyatibanerjee5480]

Understood! From lecture - 1 to 43 ✅

[@shivamverma3777]

Knse year m ho

[@AryanSingh-eq2jv]

you missed a bit
1) n nodes -| -| -|
2) n-1 edges | | |
3) all connected | ===> tree | ====> spanning tree | ====> minimum spanning tree
4) no cycles -| | |
| |
5) subset of a graph -| |
|
6) takes the minimum cost -|

[@stith_pragya]

Thank You So Much for this wonderful video.........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@janhvisingh-ry8wp]

Never thought i would understand a topic like graph like no other , thankyou!

[@CodeMode9313]

tumhari inglish acchi hai habibi ..and content bhi:)

[@pallavi22222]

superb explanation 🤩. You are putting in a lot of effort to provide great content.

[@cinime]

Understood! So awesome explanation as always, thank you very much!!

[@UECAshutoshKumar]

Thank you sir 😁

[@shivisingh9975]

Understood sir!

[@ajaybabupatel1665]

Understood ++ thanks Raj

[@saloniahuja482]

"Find the city with the smallest number of neighbors in a threshold distance"
Could you please cover this question as it was mentioned in your sheet,just after floydd warshall algo

[@takeUforward]

sure I will do it

[@Ekam873]

An MST does not contain any cycles. If a cycle exists, you can always remove one of its edges to reduce the weight.

[@gurmehakkaur7339]

Understood 👍🏻👍🏻

[@anmoljain1276]

Number of spanning tree in a complete graph is n^n-2 and if graph is not complete then it can be find by using krichoff law.

[@naga_prasanna_kumar]

Hi Striver, Great Work, You are putting perfectionism and great dedication in your videos,
Can you make some videos on high level SYSTEM DESIGN ? Can you make a plan of creating System Design Sheet, your DSA sheet is helpful.

[@abc-ym4zs]

Aa year bro system design amaina manchi resource o
Dorikinda

[@TechByte8]

Thanks Striver.

[@mugambo5505]

understood brother❣

[@AshutoshSingh-se8vf]

Now finally I am first Viewer 🤩

[@random_memes009]

Congratulation bro 🏅
May God help you

[@TON-108]

Thanks Bhai 🤍

[@DreamLife-05]

Understood 🙌💯

[@Learnprogramming-q7f]

Thank you bhaiya

[@paullater6230]

Understood!!! Thanks

[@dharmenderkumar2841]

UNDERSTOOD

[@yashshukla1637]

AWESOME!!

[@suryakiran2970]

Understood❤

[@gautamsaxena4647]

understood bhaiya

[@dishadugad4761]

can you please make a video on code of Total number of Spanning Trees in a Graph

[@anshugupta1365]

Understood👍👍☑️☑️

[@ajaybind6736]

understood thanks

[@muchmunchies43]

Understood!

[@p38_amankuldeep75]

understood🔥🔥

[@devmahad]

Done, Thanks :)

[@TarunKumarSaraswat]

thanks

[@TarunKumar-cn6in]

Understood ☺️

[@sanyamjain7058]

understood!

[@manasranjanmahapatra3729]

Understood.

[@amritarya5035]

The example you have given does not follow the rule of MST cuz number of edges is not equal to n-1..... Here no. of edges is n+1... Why??

[@aditijain4680]

Thankyou sir

[@udaytewary3809]

6:43 got the mst with same sum but different design Here my design is
2
/ | \
6 1 3
/ \
5 4
Understood bhaiya 🙏❤️

[@punyashloknath1990]

there is one point which is missed in defination of spanning tree, spanning tree shoud not contain any cycle .

[@Rajat_maurya]

can't we make MST of directed weighted graph?

[@takeUforward]

generally we don't. I don't see any use of it

[@a2_63_vimalmishra9]

understood

[@AshutoshSingh-se8vf]

Dekh rhe ho Binod Striver Bhaiya ki Mehnat

[@dreamyme543]

Understood:)

[@jyothiyadav2595]

Understand

[@MJ-ou9ff]

i will be starting with cp so can you tell if there's anything like making notes in this like as in things i learn for cp
Sorry,i know it's a stupid question but i will be joining clg so:p

[@sanamdeepsingh7914]

Understood

[@AmanGupta-ib5ss]

understood :)

[@akashsahu2571]

yes

[@adityaverma4902]

got it.

[@singhalgarvit]

watching at 1.5X ❌ watching at 2.5X ✅
one night before exam 🙂

[@vivekpaliwal1876]

Nice

[@srinayclg390]

GOD💙

[@durgeshjadhav01]

nice

[@meghanagsgs3575]

from node 5 to 6 , 5-1-2-6 , here the total sum is 13,why can't it be the minimum spanning tree.

[@pqr.priyanshu]

u have to visit all the nodes at least once

[@sanyamjain1053]

#understood

[@Ekam873]

there will always be no cycle in mst

[@akshaykumar192]

Aap kitne time sote ho

[@namamiNarayana]

Understood Sir! :)
Thank you! _/\_ ^^

[@saurabhtiwari9614]

✅✅✅

[@surbhigupta5777]

US

[@soubhikghosh6564]

Umderstood

[@harshdiwase1941]

undeestood

[@kushagramishra3026]

"Understood"

[@PankajSingh-pb4vs]

Op

[@prachimeshram6640]

us

[@anirbanbera5630]

Understood ☺

[@nikitakeshri9233]

Understood:)

[@KratosProton]

understood

[@suheabkhan2546]

Understood

[@komalkrishna7836]

understood

[@aritrasen3034]

Understood

[@rishabhgupta9846]

understood

[@mriduljain6809]

Understood

[@yogeshsahu6794]

Understood

[@pratikshadhole6694]

understood

[@aryankumar3018]

Understood

[@tanishkumar6682]

understood

[@debanjan10]

understood

[@rohanlambar4725]

Understood

[@1tav0]

understood

[@sayandeepdey4]

understood

[@sumitchakrabortystudy651]

understood

[@kaushalshinde8]

understood

[@dharmeshvala3657]

understood

[@adarshkumarrao3478]

understood

[@lakeshkumar1252]

understood

[@YATHARTHBHARDWAJ-y8m]

understood

[@abhinanda7049]

understood

[@HarshMohta]

understood

[@sauravfarkade1928]

understood

[@GungunRamchandani]

understood

[@22gauravkumar70]

understood

[@MJBZG]

understood

[@adi-w4j]

understood