Tom's Guide > Forum > Programmation > Traduction en C d'un petit algorithme

Traduction en C d'un petit algorithme

Forum Programmation : Traduction en C d'un petit algorithme

TomsGuide.com : 800 000 inscrits répondent à toutes vos questions high-tech et informatique. Pour obtenir de l'aide, inscrivez-vous gratuitement !
Mot :    Pseudo :           
 

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"

Liens sponsorisés
Inscrivez-vous ou connectez-vous pour masquer ceci.

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é.

Répondre à milmot

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 !

Répondre à damboy

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 ;-)

Répondre à CRicky
Tom's Guide > Forum > Programmation > Traduction en C d'un petit algorithme
Aller à :

Il y a 1921 utilisateurs connus et inconnus. Pour voir la liste des connectés connus, cliquez ici.

Attention

Vous allez répondre sur un sujet resté inactif pendant plus de 6 mois.
Assurez-vous d'apporter des éléments nouveaux à la discussion avant de poursuivre.

Répondre Annuler
Liens