Dasturchi, frilanser, gik va introvert
Maximum flow’ni topish jarayonida, ba’zida yechimga erishish uchun allaqachon berilgan flow’ni kamaytirish hisobiga boshqa (parallel) edge’da flow’ni oshiriladi. Inson ko’zi bilan ko’rib, qaysi flow’ni kamaytirish, qaysi flow’ni oshirishni o’zi aniqlab olishi mumkin, lekin kodda nima qilishni qanday ifodalaymiz?
Avvalgi maqolada maximum flow allaqachon topilgan graph’ni ko’rib o’tdik. Endi flow’ni qanday hisoblash haqida so’z yuritamiz.
Graph processing masalalarini o’rganishni davom ettiramiz. Minimum cut – graph’ni ikkiga shunday bo’lish kerakki, uning bo’linish edge’lari bir-biriga eng kam (kuchsiz) bog’langan joyi bo’lsin. Oddiyroq aytganda, graph’ni ikkiga bo’lish uchun eng kam harajat / kuch talab etilsin.
Ushbu maqolada biz negativ (manfiy) weight’larning graph’da shortest path’ni topishdagi ta’sirini ko’rib chiqamiz. Avvaldan aytib o’tish kerakki, negativ weight’lari bor graph’lar uchun bir ko’rib o’tgan Dijkstra algoritmi ishlamaydi.
Graph’dagi minimum spanning tree’ni topishning klassik algoritmlaridan biri – Kruskal algoritmi g’oyasi tushunishga oson. Uning ishlash tartibi…
Minimum spanning tree (MST) – undirected graph’dagi barcha o’zaro bog’langan vertex’larni o’z ichiga olgan (spanning) va aylana bo’lmagan (acyclic) sub-graph’lar ichidan minimum weight’li sub-graph.
Biz chiziqli bo’lmagan ma’lumotlar tuzilmasini o’rganishni boshlaganimizda, ularning bazaviy xarakteristikasini ko’rib chiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (hech bo’lmaganda sanoq tartibiga ega emas).