C mise en Œuvre de Kruskal algorithme de MST

Je faisais des études de Kruskal algorithme de trouver le MST pour un graphique donné et je comprends le concept de base que vous devez tenir compte de tous les sommets comme une forêt, d'abord. Après que vous avez à trouver le minimum de bord et de rejoindre les sommets de l'arête dans un arbre. Et faire cela de façon récursive jusqu'à ce qu'un arbre contenant tous les sommets est de gauche.

Et je suis tombé sur la suite de la mise en œuvre de cet algorithme.

#include<iostream.h>
int p[10];
void kruskal(int w[10][10],int n)
{
int min,sum=0,ne=0,i,j,u,v,a,b;
for(i=1;i<=n;i++)
p[i]=0;
while(ne<n-1)
{
min=999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(w[i][j]<min)
{
min=w[i][j];
u=a=i;
v=b=j;
}
}
while(p[u])
u=p[u];
while(p[v])
v=p[v];
if(u!=v)
{
ne++;
sum+=min;
cout<<"\nedge "<<a<<"-->"<<b<<" is "<<min;
p[v]=u;
}
w[a][b]=w[b][a]=999;
}
cout<<"\nmin cost spanning tree= "<<sum;
}
void main()
{
int w[10][10],n,i,j;
clrscr();
cout<<"enter no.of vertices\n";
cin>>n;
cout<<"enter weight matrix\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>w[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(w[i][j]==0)
w[i][j]=999;
kruskal(w,n);
}

Ce que je ne comprends pas, c'est la nécessité de:

while(p[u])
u=p[u];
while(p[v])
v=p[v];

Quoi exactement ces deux boucles while?

edit: et aussi la nécessité de

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(w[i][j]==0)
w[i][j]=999; 

OriginalL'auteur Chaitanya Nettem | 2011-11-20