Dasturchi, frilanser, gik va introvert
Maximum flow'ni topiş jarayonida, ba'zida yeçimga erişiş uçun allaqaçon berilgan flow'ni kamaytiriş hisobiga boşqa (parallel) edge'da flow'ni oşiriladi. Inson közi bilan körib, qaysi flow'ni kamaytiriş, qaysi flow'ni oşirişni özi aniqlab olişi mumkin, lekin kodda nima qilişni qanday ifodalaymiz?
Avvalgi maqolada maximum flow allaqaçon topilgan graph'ni körib ötdik. Endi flow'ni qanday hisoblaş haqida söz yuritamiz.
Graph processing masalalarini örganişni davom ettiramiz. Minimum cut - graph'ni ikkiga şunday böliş kerakki, uning böliniş edge'lari bir-biriga eng kam (kuçsiz) boğlangan joyi bölsin. Oddiyroq aytganda, graph'ni ikkiga böliş uçun eng kam harajat / kuç talab etilsin.
Uşbu maqolada biz negativ (manfiy) weight'larning graph'da shortest path'ni topişdagi ta'sirini körib çiqamiz. Avvaldan aytib ötiş kerakki, negativ weight'lari bor graph'lar uçun bir körib ötgan Dijkstra algoritmi işlamaydi.
Graph'dagi minimum spanning tree'ni topişning klassik algoritmlaridan biri - Kruskal algoritmi ğoyasi tuşunişga oson. Uning işlaş tartibi...
Minimum spanning tree (MST) - undirected graph'dagi barça özaro boğlangan vertex'larni öz içiga olgan (spanning) va aylana bölmagan (acyclic) sub-graph'lar içidan minimum weight'li sub-graph.
Biz çiziqli bölmagan ma’lumotlar tuzilmasini örganişni boşlaganimizda, ularning bazaviy xarakteristikasini körib çiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (heç bölmaganda sanoq tartibiga ega emas).