Discussion :

[Lily_]

Bonjour à tous,

Je ne trouve pas de solutions à mon problème, j'ai lu les FAQ et je ne crois pas que le sujet a déjà été traité!

J'ai un graphe orienté. Il manque certaines aretes. J'aimerai trouver un moyen de trouver tous les noeuds de mon graphe. J'ai donc pensé aux algorithmes de parcours (DFS et BFS), mais dans le cas des graphes orientés, cela ne fonctionne pas!

Petit exemple :
a -> b
b -> c
c -> rien
d -> b, c

On part de a, on récupère b, puis c. Mais on ne parvient pas à récupérer d.

J'espère avoir été assez claire :-)

Quelqu'un aurait-il une piste ? Y'a-t-il un moyen d'appliquer DFS ou BFS à un graphe orienté et de parcourir tous les sommets et pas uniquement les sommets suivant un chemin.

Merci d'avance!

Lily

[jguillot]

Il faut que tu lances la recherche sur chacun des noeuds entrant de ton graphe en les annotants (enfin moi c comme ça que je ferais)

Edit:
Celà depend aussi de ta structure de donnée peut être que tu as une liste des noeuds sources, il faut donc en ce cas l'utiliser pour lancer tes algos.

[Lily_]

Merci pour ta réponse! Mais je ne comprends pas trop ce que tu veux dire

Si je lance la recherche sur chacun des noeuds, comment est-ce que je regroupe ensuite les résultats ?

J'ai plusieurs graphes non connectés et je désire récupérés les noeuds des différents graphes pour créer des groupes. Donc en lancant sur chacun des noeuds, je me retrouve ensuite avec plusieurs groupes pour un meme groupe, non ?

Les données sont sous forme de hash : la clé correspond à un noeud et la valeur à 1 référence sur un tableau qui contient la liste des noeuds liés.

Merci!

[Nemerle]

Ce que tu veux faire, c'est identifier les composantes connexes de ton graphe orienté, soit en faisant des paquets de noeuds, c'est cela?

Dans ce cas, algorithme de Kosaraju (pour les graphes orientés):

http://www.liafa.jussieu.fr/~zielonk...bis_4pages.pdf


Ca détermine les composantes fortement connexes, mais tu peux adapter / simplifier au cas des composantes connexes