Algo de Prim et Kruskal

'saisie des arbres
input "combien y a t'il d' arbres ?";nbarbre
dim arbre$(nbarbre,2)
for i=1 to nbarbre
    print "entrez le nom de l' arbre N° ";i
    input nom$
    arbre$(i,1)=nom$
next i

'saisie des arêtes
input "combien y a t'il d'arêtes ?";nbarete
dim segment$(nbarete,4)
for i= 1 to nbarete
    print "segment N° ";i
    input "arbre de debut ";ad$
    input "arbre de fin   ";af$
    input "poids          ";poid$
    print
    poid$=right$("0000000000"+trim$(poid$),10)
    segment$(i,1)=ad$
    segment$(i,2)=af$
    segment$(i,3)=poid$
next i

'tri des segments par ordre croissant de poid
sort segment$(, 1, nbarete, 3
for u=1 to nbarete
    print segment$(u,1);"-";segment$(u,2);"   ";segment$(u,3)
next u

segment$(1,4)="x" 'indique que le premier segment est retenu
foret=2
nbgr=1

ad$=segment$(1,1)
af$=segment$(1,2)
poidS=val(segment$(1,3))
'ajout des arbres du segment au groupe numero 1
s=0
for i=1 to nbarbre
    if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2)="1"
    if s=2 then exit for
next i

'analyse des segments
for u=2 to nbarete
    ad$=segment$(u,1)
    af$=segment$(u,2)
    poids=val(segment$(u,3))
    print "Je selectionne le segment ";ad$;"-";af$;" qui a un poid de ";poids
    s=0
    'recherche des groupes de chaque arbre du segment
    for i=1 to nbarbre
        if ad$=arbre$(i,1) then s=s+1:grad=val(arbre$(i,2))
        if af$=arbre$(i,1) then s=s+1:graf=val(arbre$(i,2))
        if s=2 then exit for
    next i
    
    'si les arbres ne sont dans aucun groupe on en cree un nouveau
    if grad+graf=0 then
        nbgr=nbgr+1
        s=0
        for i=1 to nbarbre
            if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2))=str$(nbgr)
            if s=2 then exit for
        next i
        segment$(u,4)="x"
        print "creation du groupe d'arbre numero ";nbgr
        print "le segment est retenus."
        goto [suite]
    end if
    
    'si un des deux arbres n'est pas dans un groupe on le met dans le même groupe que l'autre arbre du segment
    if grad*graf=0 then
        if grad then
            bgr=grad
            print "L'arbre ";af$;" à été ajouté au groupe ";bgr
        else
            bgr=graf
            print "L'arbre ";ad$;" à été ajouté au groupe ";bgr
        end if
        s=0
        for i=1 to nbarbre
            if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2))=str$(bgr)
            if s=2 then exit for
        next i
        segment$(u,4)="x"
        print "le segment est retenus."
        goto [suite]
    end if
    
    'si les arbres sont dans le même groupe on ne retient pas le segment
    if grad=graf then
        print "ces arbres sont dans le groupes numero ";grad
        print "le segment ne sera pas retenus."
        goto [suite]
    end if
    
    'si les deux arbres appartiennent à des groupes differents on regroupe les arbres des deux groupes.
    grm=min(grad, graf)
    grx=grad+graf-grm
    for i=1 to nbarbre
        if ad$=arbre$(i,1) or af$=arbre$(i,1) then
            arbre$(i,2))=str$(grm)
        else
            grr=val(arbre$(i,2))
            if grr=grx then arbre$(i,2))=str$(grm)
        end if
    next i
    segment$(u,4)="x"
    print "regroupement des arbres des groupes numero ";grm;" et "; grx
    print "le segment est retenus."
[suite]
next u
print
print "Liste des segments retenus:"
for u=1 to nbarete
    if segment$(u,4)="x" then print segment$(u,1);"-";segment$(u,2);"   ";segment$(u,3)
next u
input "appuyez sur une touche pour quitter";r$
end