Minimum Spanning Tree
মিনিমাম স্প্যানিং ট্রি
Connected weighted undirected graph-এর সব V node জুড়ে ঠিক V−1 edge-এর tree, যার total weight সবচেয়ে কম — Kruskal ও Prim greedy দিয়ে পাওয়া যায়।
also: mst, minimum spanning tree
দুটো algorithm-ই cut property-র উপর দাঁড়ানো: graph-কে দুই ভাগে কাটলে সেই cut ছোঁয়া সবচেয়ে হালকা edge-টা কোনো না কোনো MST-তে থাকবেই।
| Algorithm | ভাবনা | খরচ |
|---|---|---|
| Kruskal | edge sort করে cycle না বানালে নাও (union-find দিয়ে চেক) | O(E log E) |
| Prim | এক node থেকে tree বাড়াও, প্রতিবার cheapest crossing edge | O(E log V) |
Sparse বা sorted edge-এ Kruskal সহজ; dense graph-এ Prim। Network design, single-link clustering, approximation algorithm — MST-র practical জীবন লম্বা।