Forums Rue-Montgallet.com
Rue-Montgallet.comRue-Hardware.comRue-Occasion.comRue-DVD.comRue-Jeuxvideo.comRue-AudioVideo.comRue-Telephone.comForums
S'inscrire | S'identifier |
| Recherche avancée | Aide
 

  FORUM


  Programmation


  Autre


  Algo de Warshall-Floyd et Kruskal

 
 

1 utilisateur anonyme et 11 utilisateurs inconnus

 Mot :   Pseudo :  
 
Bas de page
Auteur
 Sujet :

Algo de Warshall-Floyd et Kruskal

 
n°15408
Profil sup​primé
Posté le 09-12-2005 à 17:04:41  answer
 

Bonjour,  
 
j'aurais besoin d'aide car je dois coder en C,ces 2 algorithmes(avec une matrice et avec une liste d'adjacence pour chacun des algos).  
 
 
Merci d'avance à ceux qui m'aideront


Message édité par Profil supprimé le 12-12-2005 à 12:30:22
n°15409
P-Y
Profil : Vieux de la vieille
Posté le 09-12-2005 à 17:22:58  profilanswer
 

tu as deja code quelquechose? les structures de donnees (matrice et liste) sont imposees ou c'est a vous de les coder?

n°15415
lbasic
Profil : Jeune recrue
Posté le 10-12-2005 à 01:53:48  profilanswer
 

j'ai ça dans le fond d'un tirroir.
c'est en Liberty BASIC. (donc facile à lire).
 

Code :
  1. 'saisie des arbres
  2. input "combien y a t'il d' arbres ?";nbarbre
  3. dim arbre$(nbarbre,2)
  4. for i=1 to nbarbre
  5.     print "entrez le nom de l' arbre N° ";i
  6.     input nom$
  7.     arbre$(i,1)=nom$
  8. next i
  10. 'saisie des arêtes
  11. input "combien y a t'il d'arêtes ?";nbarete
  12. dim segment$(nbarete,4)
  13. for i= 1 to nbarete
  14.     print "segment N° ";i
  15.     input "arbre de debut ";ad$
  16.     input "arbre de fin   ";af$
  17.     input "poids          ";poid$
  18.     print
  19.     poid$=right$("0000000000"+trim$(poid$),10)
  20.     segment$(i,1)=ad$
  21.     segment$(i,2)=af$
  22.     segment$(i,3)=poid$
  23. next i
  25. 'tri des segments par ordre croissant de poid
  26. sort segment$(, 1, nbarete, 3
  27. for u=1 to nbarete
  28.     print segment$(u,1);"-";segment$(u,2);"   ";segment$(u,3)
  29. next u
  31. segment$(1,4)="x" 'indique que le premier segment est retenu
  32. foret=2
  33. nbgr=1
  35. ad$=segment$(1,1)
  36. af$=segment$(1,2)
  37. poidS=val(segment$(1,3))
  38. 'ajout des arbres du segment au groupe numero 1
  39. s=0
  40. for i=1 to nbarbre
  41.     if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2)="1"
  42.     if s=2 then exit for
  43. next i
  45. 'analyse des segments
  46. for u=2 to nbarete
  47.     ad$=segment$(u,1)
  48.     af$=segment$(u,2)
  49.     poids=val(segment$(u,3))
  50.     print "Je selectionne le segment ";ad$;"-";af$;" qui a un poid de ";poids
  51.     s=0
  52.     'recherche des groupes de chaque arbre du segment
  53.     for i=1 to nbarbre
  54.         if ad$=arbre$(i,1) then s=s+1:grad=val(arbre$(i,2))
  55.         if af$=arbre$(i,1) then s=s+1:graf=val(arbre$(i,2))
  56.         if s=2 then exit for
  57.     next i
  58.    
  59.     'si les arbres ne sont dans aucun groupe on en cree un nouveau
  60.     if grad+graf=0 then
  61.         nbgr=nbgr+1
  62.         s=0
  63.         for i=1 to nbarbre
  64.             if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2))=str$(nbgr)
  65.             if s=2 then exit for
  66.         next i
  67.         segment$(u,4)="x"
  68.         print "creation du groupe d'arbre numero ";nbgr
  69.         print "le segment est retenus."
  70.         goto [suite]
  71.     end if
  72.    
  73.     '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
  74.     if grad*graf=0 then
  75.         if grad then
  76.             bgr=grad
  77.             print "L'arbre ";af$;" à été ajouté au groupe ";bgr
  78.         else
  79.             bgr=graf
  80.             print "L'arbre ";ad$;" à été ajouté au groupe ";bgr
  81.         end if
  82.         s=0
  83.         for i=1 to nbarbre
  84.             if ad$=arbre$(i,1) or af$=arbre$(i,1) then s=s+1:arbre$(i,2))=str$(bgr)
  85.             if s=2 then exit for
  86.         next i
  87.         segment$(u,4)="x"
  88.         print "le segment est retenus."
  89.         goto [suite]
  90.     end if
  91.    
  92.     'si les arbres sont dans le même groupe on ne retient pas le segment
  93.     if grad=graf then
  94.         print "ces arbres sont dans le groupes numero ";grad
  95.         print "le segment ne sera pas retenus."
  96.         goto [suite]
  97.     end if
  98.    
  99.     'si les deux arbres appartiennent à des groupes differents on regroupe les arbres des deux groupes.
  100.     grm=min(grad, graf)
  101.     grx=grad+graf-grm
  102.     for i=1 to nbarbre
  103.         if ad$=arbre$(i,1) or af$=arbre$(i,1) then
  104.             arbre$(i,2))=str$(grm)
  105.         else
  106.             grr=val(arbre$(i,2))
  107.             if grr=grx then arbre$(i,2))=str$(grm)
  108.         end if
  109.     next i
  110.     segment$(u,4)="x"
  111.     print "regroupement des arbres des groupes numero ";grm;" et "; grx
  112.     print "le segment est retenus."
  113. [suite]
  114. next u
  115. print
  116. print "Liste des segments retenus:"
  117. for u=1 to nbarete
  118.     if segment$(u,4)="x" then print segment$(u,1);"-";segment$(u,2);"   ";segment$(u,3)
  119. next u
  120. input "appuyez sur une touche pour quitter";r$
  121. end


 
j'espere avoir pu t'aider.
 
source du message : ( http://lbasic.atomysk.com/forum/vi [...] =6329#6329 )
 
@++


Message édité par lbasic le 10-12-2005 à 01:58:00
n°15416
Profil sup​primé
Posté le 10-12-2005 à 11:10:58  answer
 

P-Y a écrit :

tu as deja code quelquechose? les structures de donnees (matrice et liste) sont imposees ou c'est a vous de les coder?


Les structures de données c'est à nous de les coder.
Sinon,j'ai codé les structures matrice et liste de cette manière:

Code :
  1. typedef struct
  2. {
  3.   int nb_sommets;/* valeur indiquant le nb de sommets de la matrice */
  4.   int **matrice;/* matrice */
  5. }Graphe_Matrice;
  7. typedef struct cellule
  8. {
  9.   int valeur;
  10.   struct cellule *suivant;
  11. }Cellule;
  13. typedef Cellule *Liste;
  15. typedef struct
  16. {
  17.   int nb_sommets;
  18.   Liste*adjacence;
  19. }Graphe_Liste;


 
Si tu peux m'aider ce serait sympa.


Aller à :
Ajouter une réponse

  FORUM


  Programmation


  Autre


  Algo de Warshall-Floyd et Kruskal

 

Forum MesDiscussions.Net, Version 2007.2
(c) 2000-2007 No1Dev
Page générée en 0.239 secondes