Algo prim: j un petit pbl dans la fct prim

#include<stdio.h>
#include<stdlib.h>
#define max 20
#define infini 1000001

typedef struct graphe
{
int debut;
int fin;
float poid;
}graphe;
typedef graphe tab[max];
tab tree,arcs,arcs_f;

void init();
void saisie();
void dfs(int);
int connexe();
void prim();
void remplir();
void heapSort();
void echanger(graphe *,graphe *);
void pushdown(int,int);
void construireArbre();
void AfficherArbre();
int n,nbarc,visite[max];
float m[max][max];

main()
{
int choix,test,rep;
do
{
printf("\n###################### - Menu - ######################\n");
printf("\n Introduire :\n");
printf("\n\t 1--> L'implémentation du Prim.");
printf("\n\t 2--> L'implémentation du kruskal.");
printf("\n\t 3--> Quitter.");
printf("\n\n\t\t Votre choix : ");
scanf("%d",&choix);
while(choix!=1 && choix!=2 && choix!=3 )
{
printf("\n\t Introduire 1, 2 ou 3");
printf("\n\t\t Votre choix : ");
scanf("%d",&choix);
}
if(choix==3)
exit(0);
saisie();
test=connexe();
switch(choix)
{
case 1:
ret_Prim:
if(test==1)
{
printf("\n Voici les arcs de l\'arbre par Prim:\n");
prim();
}
else
printf("\n\n Le graphe n\'est pas connexe\n");
break;
case 2:
if(test==1)
{
printf("\n Voici les arcs de l\'arbre par Kruskal :\n");
ret_kruskal:
remplir();
heapSort();
construireArbre();
AfficherArbre();
}
else
printf("\n\n Le graphe n\'est pas connexe\n");
break;
}
printf("\n Voulez vous recommencer ?");
printf("\n Introduire :");
if(choix==1)
printf("\n\t 1--> L'implémentation du kruskal.");
else
printf("\n\t 1--> L'implémentation du Prim.");
printf("\n\t 2--> Recommencer.");
printf("\n\t 3--> Quitter.");
printf("\n\t\t Votre choix : ");
scanf("%d",&rep);
while(rep!=1 && rep!=2 && rep!=3)
{
printf("\n\t Introduire 1 , 2 ou 3");
printf("\n\t\t Votre choix : ");
scanf("%d",&rep);
}
if(rep==1 && choix==1)
{
choix=2;
goto ret_kruskal;
}
else
if(rep==1 && choix==2)
{
choix=1;
goto ret_Prim;
}
}
while(rep!=3);
return 0;
}

/*------------------------------------------------- */
void init()
{
int i,j;
for(i=0;i<=n-1;i++)
visite[i]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=n-1;j++)
m[i][j]=0;
}

/*------------------------------------------------- */
void saisie()
{
int i,som1,som2;
float poids;
do
{
printf("\n Introduire le nombre de noeuds du graphe (min.2 max.%d) : ",max);
scanf("%d",&n);
}
while(n<2 || n>max);
init();
do
{
printf("\n Introduire le nombre d'arcs du graphe (min.1 max.%d) : ",n*(n-1));
scanf("%d",&nbarc);
}
while(nbarc<1 || nbarc>n*(n-1));
for(i=0;i<=nbarc-1;i++)
{
arc_incorrect:
printf("\n L\'arc n°%d :",i+1);
printf("\n Noeud de depart : ");
scanf("%d",&som1);
while(som1<0 || som1>=n)
{
printf("\n Cet arc est incorrect",som1,som2);
printf("\n Noeud de depart : ");
scanf("%d",&som1);
}
printf("\n Noeud d\'arrivé : ");
scanf("%d",&som2);
while(som2<0 || som2>=n)
{
printf("\n Cet arc est incorrect",som1,som2);
printf("\n Noeud d\'arrivé : ");
scanf("%d",&som2);
}
if(som1==som2)
goto arc_incorrect;
else
if(m[som1][som2]>0)
{
printf("\n L\'arc <%d,%d> existe deja",som1,som2);
goto arc_incorrect;
}
printf(" Introduire le poids de l\'arc <%d,%d> (min.1 max.%ld) : ",som1,som2,infini-1);
scanf("%f",&poids);
while(poids<=0 || poids >(infini-1))
{
printf(" Le poids doit être entre 0 et %ld.",infini-1);
printf("\n Introduire un autre poids : ");
scanf("%f",&poids);
}
m[som1][som2]=poids;
m[som2][som1]=poids;
} //fin for
}

/*------------------------------------------------- */
void dfs(int i)
{
int j;
visite[i]=1;
for(j=0;j<=n-1;j++)
if(m[i][j]>0 && visite[j]==0)
dfs(j);
}

/*------------------------------------------------- */
int connexe()
{
int i,val=0;
dfs(0);
for(i=1;i<=n-1;i++)
if(visite[i]==0)
{
val=1;
break;
}
if(val==1)
return 0;
else
return 1;
}

/*------------------------------------------------- */
void prim()
{
float low[max],min;
int closest[max];
int i,j,k;
for(i=1;i<=n-1;i++)
{
closest[i]=0;
low[i]=m[0][1];
}
for(i=1;i<=n-1;i++)
{
min=low[i];
k=i;
for(j=i+1;j<=n-1;j++)
if(low[j]<min)
{
min=low[j];
k=j;
}
printf("\n <%d,%d> poids %.2f",k,closest[k],low[k]);
for(j=1;j<=n-1;j++)
if((m[j][k]<low[j])&&(low[j]<infini))
{
low[k]=m[j][k];
closest[j]=k;
}
low[k]=infini;
}
}

/*------------------------------------------------- */
void remplir()
{
int i,j,y=0;
for(i=0;i<=n-1;i++)
for(j=i+1;j<=n-1;j++)
if(m[i][j]>0)
{
arcs[y].debut=i;
arcs[y].fin=j;
arcs[y].poid=m[i][j];
y++;
}
}

/*------------------------------------------------- */
void echanger(graphe *x,graphe *y)
{
graphe temp;
temp=*x;
*x=*y;
*y=temp;
}

/*------------------------------------------------- */
void heapSort()
{
int i,l=nbarc-1,j=0;
for(i=(l-1)/2;i>=0;i--)
pushdown(i,l);
for(i=l;i>=1;i--)
{
arcs_f[j++]=arcs[0];
echanger(&arcs[0],&arcs[l]);
l--;
pushdown(0,l);
}
arcs_f[j]=arcs[0];
}

/*------------------------------------------------- */
void pushdown(int first, int last)
{
int r=first;
while(r<(last+1)/2)
{
if((2*r)+1==last)
{
if(arcs[r].poid>arcs[(2*r)+1].poid)
echanger(&arcs[r],&arcs[(2*r)+1]);
r=last;
}
else
{
if((arcs[r].poid>=arcs[(2*r)+1].poid)&&(arcs[(2*r)+1].poid<=arcs[(2*r)+2].poid))
{
echanger(&arcs[r],&arcs[(2*r)+1]);
r=(2*r)+1;
}
else
if((arcs[r].poid>=arcs[(2*r)+2].poid)&&(arcs[(2*r)+2].poid<=arcs[(2*r)+1].poid))
{
echanger(&arcs[r],&arcs[(2*r)+2]);
r=(2*r)+2;
}
else
r=last;
}
}
}

/*------------------------------------------------- */
void construireArbre()
{
int NumComp[max];
int sommet,num1,num2,i=0,j;
for (sommet=0;sommet<=n-1;sommet++)
NumComp[sommet]=sommet;
for(j=0;j<=n-1;j++)
{
while((i<=nbarc-1)&&(NumComp[arcs_f[i].debut]==NumComp[arcs_f[i].fin]))
i++;
if(i==nbarc-1)
break;
tree[j]=arcs_f[i];
num1=NumComp[arcs_f[i].debut];
num2=NumComp[arcs_f[i].fin];
for(sommet=0;sommet<=n-1;sommet++)
if(NumComp[sommet]==num2)
NumComp[sommet]=num1;
}
}

/*------------------------------------------------- */
void AfficherArbre()
{
int i;
printf("\n Voici les arêtes de l'arbre couvrant de poids minimum par KRUSKAL :\n");
for (i=0;i<=n-2;i++)
printf("<%d,%d>\t", tree[i].debut,tree[i].fin);
}