• include using namespace std; int
• # Kruskal algoritmini c++ da amalga oshirish

Bog'liq
algoritm mustaqil ish
иш хақи, Mavzu Antivirus-dasturlari, 1-SINF, V sinf texnologiya va dizayn yo‘nalishi buyicha 5-sinflar uchun , Nometal materiallar, Жуфт сузлар, дарс ишланма сон, BEKLEMISHEV KLASSIFIKATSIYASIGA KO, A new generation of realistic writers, Ochiq faoliyat ishlanma 2, Zamonaviy sun
Kruskal algoritmini c++ da amalga oshirish

Biz tegishli ma'ruzadan barcha optimallashtirishlar bilan DSU dasturidan foydalanamiz:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include using namespace std; int p[100000]; int rk[100000]; void init_dsu() { for (int i = 0; i < 100000; i++) { p[i] = i; rk[i] = 1; } } int get_root(int v) { if (p[v] == v) { return v; } else { return p[v] = get_root(p[v]); } } bool merge(int a, int b) { int ra = get_root(a), rb = get_root(b); if (ra == rb) { return false; } else { if (rk[ra] < rk[rb]) { p[ra] = rb; } else if (rk[rb] < rk[ra]) { p[rb] = ra; } else { p[ra] = rb; rk[rb]++; } return true; } } struct edge { int a, b, len; bool operator<(const edge& other) { return len < other.len; } }; int main() { vector edges; sort(edges.begin(), edges.end()); int mst_weight = 0; init_dsu(); for (edge e: edges) { if (merge(e.a, e.b)) { mst_weight += e.len; } } cout << "Minimum spanning tree weight: " << mst_weight << endl; }

1. Ish tezligidagi farqlar

Ikkala algoritm ham quyidagilar uchun ishlaydi O(M log N), ularning ishlash tezligida doimiy farqlar mavjud. Kruskal algoritmi siyrak grafikalarda (qirralarning soni taxminan tepaliklar soniga teng) tezroq ishlaydi va to'yingan grafikalarda (qirralarning soni tepaliklar sonining kvadratiga teng) - Prim algoritmi (qo'shni matritsadan foydalanganda).

a) b)

v) g)

d) e)

j) z)

Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:

edgeCount=1
while edgeCount<=Е and includedCount<=N-1 do
parent1=FindRoot(edge[edgeCount].start)
parent2=FindRoot(edge[edgeCount].end)
if parent1/parent2 then
edge[edgeCount] ni MOD ga qo’shish
includedCount= includedCount=1
Union(parent1,parent2)
Enf if
edgeCount= edgeCount+1
end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .
Shunday masalalar borki, ular tez algoritmli yechimga ega bo’lmagan masalalardir (NP-to’liq masalalar Shunday masalalar haqida va ularni yechish uchun tez algoritr mla (har doim ham o’rinli emas).) bilan tanishamiz.
NP-to’liq masalalarda bunday algoritmlar optimal yechimga yaqin bo’lgan natijani olish uchun ishlatilishi mumkin.
Biz xasislik strategiyasi ya’ni, masalalar yechishni juda oddiy strategiyasi haqida bilib olamiz.