programmer kruskal en C Fermé

Question

Bonsoir ;Pourriez-vous m'aider à programmer l'algorithme de kruskal en langage C.j'ai toujours des difficultés à commencer le programme.dans l'attente d'une réponse,je vous remercie d'avance.

pascal · Answer

Pour le fun, je me suis penché sur la question et j'ai trouvé une solution assez simple.
entre tes segments puis classe les par ordre de poids croissant.
va du premier au dernier segment.
attribue a chaque arbre un n° de groupe.
(les 2 premiers auront le 1)
a chaque fois que tu analyse un nouveau segment, si l'un des arbres est dans un groupe alors attribue ce N° de groupe aux deux arbres du segment.
si les deux arbres sont dans deux groupes distinct, alors regroupe les arbres des 2 groupes.
si les arbres sont dans aucun groupe alors cree un nouveau groupe.

dans les 3 cas ci-dessus retiens le segment autrement ignore le.

au final tu te retrouve avec un groupe contenant tous les arbres.
(la liste des segments retenus constitue l'algorythme de kruskal.

CQFD.

pascal · Answer

Voici l'adresse d'un site sur kruskal

http://www.iro.umontreal.ca/~aqelmoha/kd.htm

et voici mon programme:

'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)
    poid=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

il est ecrit en liberty basic
http://lbasic.atomysk.com

et voici le resultat:

combien y a t'il d' arbres ?9
entrez le nom de l' arbre N° 1
?A
entrez le nom de l' arbre N° 2
?B
entrez le nom de l' arbre N° 3
?C
entrez le nom de l' arbre N° 4
?D
entrez le nom de l' arbre N° 5
?E
entrez le nom de l' arbre N° 6
?F
entrez le nom de l' arbre N° 7
?G
entrez le nom de l' arbre N° 8
?H
entrez le nom de l' arbre N° 9
?I
combien y a t'il d'arêtes ?14
segment N° 1
arbre de debut A
arbre de fin   B
poids          4

segment N° 2
arbre de debut A
arbre de fin   H
poids          8

segment N° 3
arbre de debut B
arbre de fin   C
poids          8

segment N° 4
arbre de debut B
arbre de fin   H
poids          11

segment N° 5
arbre de debut C
arbre de fin   D
poids          7

segment N° 6
arbre de debut C
arbre de fin   F
poids          4

segment N° 7
arbre de debut C
arbre de fin   I
poids          2

segment N° 8
arbre de debut D
arbre de fin   E
poids          9

segment N° 9
arbre de debut D
arbre de fin   F
poids          14

segment N° 10
arbre de debut E
arbre de fin   F
poids          10

segment N° 11
arbre de debut F
arbre de fin   G
poids          2

segment N° 12
arbre de debut G
arbre de fin   H
poids          1

segment N° 13
arbre de debut G
arbre de fin   I
poids          6

segment N° 14
arbre de debut H
arbre de fin   I
poids          7

G-H   0000000001
C-I   0000000002
F-G   0000000002
A-B   0000000004
C-F   0000000004
G-I   0000000006
H-I   0000000007
C-D   0000000007
B-C   0000000008
A-H   0000000008
D-E   0000000009
E-F   0000000010
B-H   0000000011
D-F   0000000014
Je selectionne le segment C-I qui a un poid de 0
creation du groupe d'arbre numero 2
le segment est retenus.
Je selectionne le segment F-G qui a un poid de 0
L'arbre F à été ajouté au groupe 1
le segment est retenus.
Je selectionne le segment A-B qui a un poid de 0
creation du groupe d'arbre numero 3
le segment est retenus.
Je selectionne le segment C-F qui a un poid de 0
regroupement des arbres des groupes numero 1 et 2
le segment est retenus.
Je selectionne le segment G-I qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.
Je selectionne le segment H-I qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.
Je selectionne le segment C-D qui a un poid de 0
L'arbre D à été ajouté au groupe 1
le segment est retenus.
Je selectionne le segment B-C qui a un poid de 0
regroupement des arbres des groupes numero 1 et 3
le segment est retenus.
Je selectionne le segment A-H qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.
Je selectionne le segment D-E qui a un poid de 0
L'arbre E à été ajouté au groupe 1
le segment est retenus.
Je selectionne le segment E-F qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.
Je selectionne le segment B-H qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.
Je selectionne le segment D-F qui a un poid de 0
ces arbres sont dans le groupes numero 1
le segment ne sera pas retenus.

Liste des segments retenus:
G-H   0000000001
C-I   0000000002
F-G   0000000002
A-B   0000000004
C-F   0000000004
C-D   0000000007
B-C   0000000008
D-E   0000000009
appuyez sur une touche pour quitter

ça marche !!!!!

@++

Programmer kruskal en C

2 réponses

Discussions similaires