Minimum spanning tree'ni topiş uçun Kruskal algoritmi
Graph'dagi minimum spanning tree'ni topişning klassik algoritmlaridan biri - Kruskal algoritmi ğoyasi tuşunişga oson. Uning işlaş tartibi:
- Edge weight'larini ösiş tartibida saralab oladi.
- Kiçik edge'lardan boşlab, ularni graph'ga qöşib boradi (qoraga böyab boradi). Agar edge qöşilgaç MSTda cycle hosil bölsa, edge'ni tuşirib qoldiradi.
- Işni MSTdagi edge'lar soni V - 1 bölgunça davom ettiradi. V - graph'dagi vertex'lar soni.
**Kruskal algoritmi. Image credit: https://algs4.cs.princeton.edu/43mst/
Kodda ifodalaş
Kruskal algoritmini kodda ifodalaşdan oldin quyidagi savollarga javob topiş kerak.
Edge weighted graph'ni qanday ifodalaymiz?
Edge weighted graph'ni adjacency list'da ifodalasa böladi, faqat weight'ni ham qöşib boriş kerak. Menimça boğlanişlar uçun Map() mos keladi. Graph APIda biz Set() ni işlatgan edik, sababi adjacency list uçun boğlangan vertex'ning indeksi kifoya qilardi. Endi bizga vertex va weight ham kerak bölgani uçun, edge'ning ikki uçi bölgan vertex'larni va weight'ni Map() da saqlaymiz.
const edges = new Map() // har bir edge uçun Map yaratamiz
edges.set('v', v) // v vertex
edges.set('w', w) // w vertex
edges.set('weight', weight) // w - v vertex'ga boğlangan boşqa vertex
graph[v] = edges
Agar biz 1 vertex'ga 4 vertex'ni 10 weight'li edge qilib boğlasak, u holda adjacency list quyidagiça körinişda böladi:
graph[ null, Map { 'v': 0, 'w': 7, 'weight': 0.16 } ] // graph[0] = empty
Edge weight'larni ösiş tartibida qanday tartiblaymiz?
Javascript'da Array.sort() funksiyaning implementatsiyasida Mozilla MergeSort'ni işlatadi, Çrome V8 da esa QuickSort'ni (kiçik array'lar uçun Insertion sortni. Ikki algoritmning ham time complexity'si bir xil bölgani uçun, biz tartiblaşni optimallaştiriş haqida öylab ötirmay, Array.sort() dan foydalanamiz.
Cycle'ni qanday aniqlaymiz?
Aylanalarni topiş uçun depth first searchdan foydalansa böladi. Aslida bizga cycle'ni topiş ham şartmas, Edge'ning ikki vertexi - v dan w ga path borligini tekşiriş kifoya qiladi. Sababi agar path bölsa, yangi qöşiladigan edge cycle'ga olib keladi.
Path borligini tekşiriş uçun depth first search'dan foydalaniş mumkin.
Alternativ variant - Union-Findni işlatsa ham böladi.
Kod

Quyidagi funksiya boğlanişlarni Union-find'da tekşiradi.
Mavzu böyiça savollarni Github’dagi Webmaxor / leetcode-solutions repository’da yozişingiz yoki kodda **Reference in new issue **ni bosib, qoldirişingiz mumkin.