Algorithme de Prim en Python

Version imprimable

Bonjour à tous,

J'ai un projet églament c'est de coder l'algo de Prim en Python : je n'ai fait que 6 mois de python au paravant, excusez mon niveau !

J'ai généré un petit code mais il me renvoit un arbre vide... Je ne vois pas où est l'erreur...
Merci pour votre aide !

Bien cordialement,

Nora

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# -*-coding: utf-8 -*-
 
def ASortantes(G,Y): #aretes sortantes
 
    if x in Y or y in Y:
        AS={(v,x,y) for (v,x,y) in G}
    return(AS)
 
 
def Prim(G):
    Tree=[]
    X=set()
    n=len(X)
    Y={0}
    a=0
    while a<n-1:
            AS=ASortantes(G,Y)
            AS.sort()
            (v,x,y)=AS[0]
            Y=Y.union([x,y])
            Tree.append((v,x,y))
            a=a+1
    return Tree
 
 
G = [(7,0,1),(7,0,2),(3,0,3),(6,0,8),(8,1,7),(3,1,4),(1,2,4),(9,3,5),(1,4,7),(4,4,6),(3,4,5),(2,5,6),(2,5,8),(2,6,8),(5,7,8)]
print (Prim(G))

07/02/2017, 13h42
aepli

Bonjour,

Pourrais-tu utilisé la balise "code" pour ton script, il sera plus lisible, merci.
Dans l'éditeur la balise "code" peut être insérée en cliquant sur le bouton "#".

Salutations.
07/02/2017, 18h27
wiztricks

Citation:

Envoyé par Noranour

J'ai généré un petit code mais il me renvoit un arbre vide... Je ne vois pas où est l'erreur...

Pour comprendre l'erreur, il faut réfléchir à ce que votre code devrait faire et comprendre pourquoi il ne le fait pas. Pour çà, vous avez l'instruction "print" et vous posez des questions comme:
"Est ce que je passe bien dans le while?"
Pour y répondre, vous ajoutez de print ('a=', a) juste après while a<n-1:.
Si rien ne s'affiche, c'est que la condition n'est jamais vraie.
Ce qui explique pourquoi la liste reste vide mais pose une autre question "pourquoi cette condition n'est jamais vraie?".
Pour y répondre, lecture du code, un peu de logique, print,...

- W
08/02/2017, 14h27
aepli

Bonjour,

Merci pour la balise "code", il y a du mieux. :)

Essayez aussi de nommer vos variables avec des noms intelligibles expliquant implicitement leur contenu, si pour vous votre algorithme est évident, pour les personnes qui vous relisent, ce n'est pas toujours le cas.

Et évidemment quelques commentaires pour expliquer ce qui doit être réalisé par les instructions suivantes, n'est pas superflu.

Dans votre cas et comme le précise wiztricks, il serait peut être intéressant de vous poser des questions sur les valeurs qui sont prisent par les variables a et n dans votre boucle.

Essayé de faire un tableau pour chaque itération, comme par exemple:

a n n-1

0 len(X) = ? ?

1 ? ?

etc. ... ...

Salutations.
PS: Petite astuce, pensez-vous qu'en l'état votre boucle arrive a incrémenté la variable a de 1 ?

a	n	n-1
0	len(X) = ?	?
1	?	?
etc.	...	...