Dasturchi, frilanser, gik va introvert
Minimum spanning tree (MST) algoritmlarini boshlashdan avval biz ular uchun umumiy algoritm – Greedy algoritmi nazariyasini ko’rib chiqamiz. Greedy har bir qadamda optimal variantni tanlab, muammoni yechishning optimal yo’lini topishga urinadi.
Kuchli bog’langan komponentlar (strongly connected components, SCC) connected components’ning directed graph uchun mo’ljallangan ko’rinishi bo’lib, yagona farqi – strongly connected components’da vertex’lar ikki taraflama bog’langan bo’lishi kerak.
Bog’langan komponentlar (Connected components, CC) deb graphdagi bir-biriga tog’ridan to’g’ri yoki oradagi vertex’lar orqali bog’langan komponentlar to’plamiga aytiladi. Amaliyotda agar ikki vertex orasida path bo’lsa, biz ularni bog’langan deb ayta olamiz.