Och ko’z algoritmlar

T - olingan daraxt va S - W(T) > W(S) kerakli daraxt bo'lsin . Shubhasiz, bu sodir bo'lishi uchun biz bir vaqtning o'zida minimal vaznga ega bo'lmagan chekkani tanladik, lekin yuqoridagi algoritmga ko'ra biz doimo minimal og'irlik qirralarini tanlaymiz. Demak, Krushkal algoritmi har doim to'g'ri natija beradi. E'tibor bering, V cho'qqilarning minimal yoyiladigan daraxti kamida V-1 qirralariga ega bo'lishi va tsiklni o'z ichiga olmaydi. Shunday qilib, biz yuqoridagi bosqichda qo'shimcha chekka tanlamadik.
Ushbu maqola Vineet Joshi tomonidan taqdim etilgan . Agar sizga GeeksforGeeks yoqsa va o'z hissangizni qo'shmoqchi bo'lsangiz, hissa.geeksforgeeks.org dan foydalanib maqola yozishingiz yoki maqolangizni [e-mail] manziliga yuborishingiz mumkin. Maqolangizni GeeksforGeeks bosh sahifasida ko'ring va boshqa Geeksga yordam bering.
Agar biror narsa noto'g'ri bo'lsa yoki yuqorida muhokama qilingan mavzu haqida ko'proq ma'lumot almashishni istasangiz, sharhlaringizni yozing.
KRUSKAL ALGORITMI BO`YICHA
#include
#include
#include
using namespace std;
const int MAX = 1e6-1;
int root[MAX];
const int nodes = 9, edges = 14;
pair > p[MAX];
int parent(int a) //find the parent of the given node
{ while(root[a] != a)
{ root[a] = root[root[a]];
a = root[a]; }
return a;}
void union_find(int a, int b) //check if the given two vertices are in the same “union” or not
{ int d = parent(a);
int e = parent(b);
root[d] = root[e];
}
long long kruskal()
{
int a, b;
long long cost, minCost = 0;
for(int i = 0 ; i < edges ; ++i)
{
a = p[i].second.first;
b = p[i].second.second;
cost = p[i].first;
if(parent(a) != parent(b))
//only select edge if it does not create a cycle (ie the two nodes forming it have different root nodes)
{
minCost += cost;
union_find(a, b);
}
}
return minCost;
}
int main()
{
int x, y;
long long weight, cost, minCost;
for(int i = 0;i < MAX;++i)
//initialize the array groups
{ root[i] = i; }
p[0] = make_pair(4, make_pair(0, 1));
p[1] = make_pair(8, make_pair(1, 2));
p[2] = make_pair(7, make_pair(2, 3));
p[3] = make_pair(9, make_pair(3, 4));
p[4] = make_pair(10, make_pair(4, 5));
p[5] = make_pair(2, make_pair(5, 6));
p[6] = make_pair(1, make_pair(6, 7));
p[7] = make_pair(8, make_pair(7, 0));
p[8] = make_pair(11, make_pair(1, 7));
p[9] = make_pair(2, make_pair(2, 8));
p[10] = make_pair(4, make_pair(2, 5));
p[11] = make_pair(6, make_pair(8, 6));
p[12] = make_pair(14, make_pair(3, 5));
p[13] = make_pair(7, make_pair(7, 8));
sort(p, p + edges); //sort the array of edges
minCost = kruskal();
cout << "Minimum cost is: "<< minCost << endl;
return 0;
}