Greedy algoritmi

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.

Minimum spanning tree

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.