Edge sort — Kruskal

Kruskal மரப் பிணைப்பில் (MST) விளிம்புகளை எடை குறைவு முதல் செயலாக்குகிறோம். அதற்கு முன் விளிம்புகளை எடையின்படி வரிசைப்படுத்த வேண்டும்; சில சமயங்களில் முனைப் புள்ளிகள் tie-break.

உண்மை உலகில் இது ஏன் முக்கியம்?

நெடுவழி இணைப்பு திட்டமிடல்யில் ஒவ்வொரு கேபிள் துண்டத்திற்கும் செலவு; மலிவானவற்றை முதலில் முயற்சித்து MST போன்ற கட்டமைப்பை உருவாக்கலாம். போக்குவரத்து எரிபொருள் மதிப்பீட்டின்படி வழிகளை வரிசைப்படுத்தி பின் greedy பொருத்தம். விளையாட்டு AI நகர்வுகளை மதிப்பெண்ணால் வரிசைப்படுத்தி ஆராய்வு. வரிசைப்படுத்தல் — முன்நிபந்தனை.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

விளிம்புகளை (weight, u, v) tuple ஆக சேகரித்து ஏறுவரிசையில் வரிசைப்படுத்தவும். நிலைத்த தீர்மானம்க்கு (u,v) tie-break. பின் union–find சுழற்சி. வரிசைப்படுத்தல் பெரும்பாலும் O(E log E); union–find O(E α(V)).

Pythonில் முயற்சி செய்வோம்

edges = [(4, 0, 1), (2, 1, 2), (2, 0, 2), (7, 2, 3)]
edges.sort()  # weight, then u, then v by Python tuple order
print(edges)

அடிக்கடி நேரும் தவறுகள்

• எடை மட்டும் வரிசை; இணையான விளிம்புகளை மறத்தல்.
• எடை கூட்டலில் முழு எண் வெடிப்பு — Python int பாதுகாப்பு.
• எடை சமம், முனை வேறுபாடு — tie-break வெளிப்படையாக.

முக்கியச் சுருக்கக் குறிப்புகள்

• MST / matroid greedy இல் விளிம்பு வரிசை முதல் படி.
• Tie-break தெளிவாக — சோதனை எளிது.
• Kruskal க்கு disjoint set தேவை; வரிசை மட்டும் போதாது.