Mustaqil ish fan nomi: Algoritmlash va loyihalash Mavzu

Edge weighted graph’ni qanday ifodalaymiz?
Edge weighted graph’ni adjacency list’da ifodalasa bo’ladi, faqat weight’ni ham qo’shib borish kerak. Menimcha bog’lanishlar uchun Map() mos keladi. Graph APIda biz Set() ni ishlatgan edik, sababi adjacency list uchun bog’langan vertex’ning indeksi kifoya qilardi. Endi bizga vertex va weight ham kerak bo’lgani uchun, edge’ning ikki uchi bo’lgan vertex’larni va weight’ni Map() da saqlaymiz.
const edges = new Map() // har bir edge uchun Map yaratamiz
edges.set('v', v) // v vertex
edges.set('w', w) // w vertex
edges.set('weight', weight) // w - v vertex'ga bog'langan boshqa vertex
graph[v] = edges
Agar biz 1 vertex’ga 4 vertex’ni 10 weight’li edge qilib bog’lasak, u holda adjacency list quyidagicha ko’rinishda bo’ladi:
graph[ null, Map { 'v': 0, 'w': 7, 'weight': 0.16 } ] // graph[0] = empty
Edge weight’larni o’sish tartibida qanday tartiblaymiz?
Javascript’da Array.sort() funksiyaning implementatsiyasida Mozilla MergeSort‘ni ishlatadi, Chrome V8 da esa QuickSort‘ni (kichik array’lar uchun Insertion sortni. Ikki algoritmning ham time complexity‘si bir xil bo’lgani uchun, biz tartiblashni optimallashtirish haqida o’ylab o’tirmay, Array.sort() dan foydalanamiz.