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
Vous devez vous connecter pour publier un commentaire.
Kruskals algorithme veut ajouter un certain avantage
(a, b)
. Toutefois, avant de le faire, il doit vérifier sia
etb
sont déjà connectés (s'ils le sont, il ne sera pas ajouter le bord).Votre quatre lignes à faire que de vérifier si
a
etb
sont déjà connectés.Pour comprendre cela, vous devez connaître les éléments suivants: d'Abord
u
etv
sont mis àa
etb
, respectivement. Le tableaup
stocke les composants connectés. C'estp[x] = y
signifie:x
se trouve dans la composante connexe dey
. Notez qu'au départ, chaque sommet représente sa propre composante connexe, indiqué parp[n1] = 0, p[n2] = 0, ...
(c'est à dire le composant est mis à 0).En outre, notez que chaque composante connexe est représentée par un sommet.
Donc, ici nous allons:
while(p[u])
vérifie siu
est représentant d'un composant (u
est un représentant iffp[u] == 0
, ce qui provoque la boucle while à l'arrêt). Donc, siu
est le représentant d'un composant, il s'arrête.La partie la plus intéressante est la suivante: Si
u
n'est pas un représentant, l'algorithme de recherchep[u]
, c'est à dire qu'il recherche le nœud qui est le représentant de la composante deu
. Puis il met à jouru
en conséquence (u=p[u]
).Vous pouvez envisager de tout ce jeu sous forme de graphique. Considérons le tableau suivant représente les composants connectés:
Cela signifie, que nœud
1
appartient à la composante représentée par2
.4
appartient à la composante représentée par3
, qui appartient lui-même à la composante représentée par2
. Notez que2
est un représentant, car elle a l'entrée0
.Vous pouvez visualiser ce qu'un graphe:
Vous voyez, nous avons actuellement 3 composants représentés par 2, 7 et 9, respectivement.
Si nous voulons maintenant ajouter un nouveau bord de
(6,7)
, nous avons à "monter les arbres" jusqu'à ce que nous trouvons les auxiliaires 2 et 7, respectivement. Comme nous le voyons, les auxiliaires ne sont pas les mêmes, nous ajoutons le bord.Maintenant un autre exemple: Nous voulons ajouter bord
(6, 5)
, nous avons donc "aller en haut de l'arbre" et de trouver des représentant2
dans les deux cas. Ainsi, nous n'avons pas d'ajouter le bord."Monter dans les arbres" est fait par les lignes qui ont été explicitement indiqué par vous.
Kruskal a des étapes intermédiaires, où les deux composantes connexes sont fusionnés. Si vous ajoutez un nouveau bord, il doit passer entre les deux composantes connexes. Ces composants sont stockés dans
p
.Cet exemple m'a beaucoup aidé! 🙂
ainsi, le
if(u!=v)
instruction vérifie si les représentants ne sont pas les mêmes pour s'assurer qu'il n'y a pas de cycles. Suis-je le droit?Pas sûr, mais autant que je me souvienne, il fonctionne sur pure graphiques. (Peut-être cette helpts: stackoverflow.com/questions/22649416/...)
OriginalL'auteur phimuemue