Se connecter / S'enregistrer
Votre question

Traduction en C d'un petit algorithme

Tags :
  • Mémoires
  • Programmation
Dernière réponse : dans Programmation
2 Mars 2006 15:33:41

Bonjour à tous.

Voici un petit algorithme qui permet de déterminer si un graphe possède ou non un cycle.
Cet algorithme dit simplement que tant qu'il existe un sommet v (de l'ensemble des sommets) tel qu'il n'y a pas d'arcs sortants de ce sommet, on remplace G (le graphe) par le graphe moins ce sommet.
Si a la fin le graphe est vide, le graphe n'a pas de cycle.
Sinon il en a un.

Mon problème est de savoir quels sont les moyens pour programmer cet algorithme en C ??
Comment puis-je faire G:=G-v (ma question principale) car ce serait un genre de variable ensembliste ?!

Merci !!

Donnée : G=(V,E) est un graphe simple orienté.

Algorithme :

Tant qu'il existe v € V tel que le d^-(v)=0,
G:=G-v
Si G=vide
alors sortie :"oui, G sans cycle"
sinon sortie :"non, G possède un cycle"

Autres pages sur : traduction petit algorithme

2 Mars 2006 17:04:25

tout dépend de la façon dont vous représentez la notion de graphe en C.

La plus simple est d'utiliser un tableau Arc de dimension 2 sur les sommets S1, S2, S3, ... Sn.

Arc[i,j] contient vrai (ou le poids) si il existe un arc allant de Si à Sj.

"Si" n'a pas d'arc sortant si pour tout j, arc[i,j]=faux (ou 0).

Enlevez Si du tableau arc, revient à mettre faux ou 0 dans toutes les cases arc[j,i].

C'est très rapide à programmer mais cela consomme beaucoup de mémoire (n²).

Sinon il est possible d'utiliser des listes chainées.

Une liste principale "sommet" liste les divers sommets et de chaque sommet on fait partir la liste "arc" des sommets auxquels il est relié.
2 Mars 2006 18:04:59

Merci !

Je suis obligé d'utiliser les listes chaînées...

Je vais donc essayer de lister les champs de destination d'un sommet à l'autre, de les compter et de les stocker dans un tableau.

Ca cofirme mon idée encore merci !
a b L Programmation
2 Mars 2006 21:24:00

Oui pour les graphes ce sont des listes chainées qu'il faut utiliser, c'est le plus pratique pour faire des parcours après ;-)
Tom's guide dans le monde
  • Allemagne
  • Italie
  • Irlande
  • Royaume Uni
  • Etats Unis
Suivre Tom's Guide
Inscrivez-vous à la Newsletter
  • ajouter à twitter
  • ajouter à facebook
  • ajouter un flux RSS