C++

Forum

 
Kruskal algoritm

Mercur (4)
hello friends:)i have a code for kruskal algoritm its working and i know how is the kruskal on paper.but i dont understand this codes.can anyone explain me how the codes working?:/ what is the task for sets and top arrays?




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
 
void kruskal::algorithm()
{
    // ->make a set for each node
    for(int i=1;i<=n;i++)
    {
    sets[i][1]=i;
    top[i]=1;
    }
cout<<"\nThe algorithm starts ::\n\n";
for(int i=1;i<=edge;i++)
    {
		int p1=find_node(graph_edge[i][1]);
		int p2=find_node(graph_edge[i][2]);
        if(p1!=p2)
        {
            cout<<"The edge included in the tree is ::"
				<<" < "<<graph_edge[i][1]<<" , "
				<<graf_kenar[i][2]<<" > "<<endl<<endl;
			tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
			tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
            // Mix the two sets
            for(int j=1;j<=top[p2];j++)
            {
                top[p1]++;
                sets[p1][top[p1]]=sets[p2][j];
            }
            top[p2]=0;
        }
        else
        {
            cout<<"Inclusion of the edge "
				<<" < "<<graph_edge[i][1]<<" , "
				<<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";
        }
    }
}
int kruskal::find_node(int n)
{
	for(int i=1;i<=edge;i++)
    {
        for(int j=1;j<=top[i];j++)
        {
        if(n==sets[i][j])
            return i;
        }
    }
    return -1;
}

Topic archived. No new replies allowed.