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.
Dijkstra'ning algoritmi graph'dagi bir vertex'dan boşqa har bir vertex'ga qisqa yölni topiş uçun işlatiladi.
Biz ötgan mavzularda körib ötganimiz, minimum spanning tree - edge'lari weight'ga ega undirected graph'dagi barça vertex'larni öz içiga olgan qisqa yölni topişga bağişlangan edi. Edge-weight'li directed graph uçun esa shortest path (qisqa yöl) algoritmlari bilan tanişib çiqamiz.
Kuçli boğlangan komponentlar (strongly connected components, SCC) connected components'ning directed graph uçun möljallangan körinişi bölib, yagona farqi - strongly connected components'da vertex'lar ikki taraflama boğlangan bölişi kerak.
Biz ötgan graph masalalarida asosan undirected graph'larni körib çiqdik. Aslida undirected graph directed graph'dan kodda ifodalanganda bor yöği graph'dagi barça vertex'larning ikki tomonlama (ikki yönalişli) boğlangani bilan farq qiladi. Şuning uçun undirected graph masalalaridagi yeçimlar yoki alg
Graph ma'lumotlar tuzilmasini kodda ifodalaşning bir neça usullari bor. Amaliyotda qöyiladigan masalaga qarab usullardan biri tanlanadi.
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).