Discussion :

[JohnKr]

Bonjour à toutes et à tous !

Voilà, je bloque sur un exercice en JAVA mais mon problème est d'ordre algorithmique. C'est la raison pour laquelle, je poste dans cette section. Je n'ai pas trouvé de réponses sur le forum.

Mon problème se situe au niveau des graphes.


A ma disposition, j'ai 3 classes :
* Classe List (entier numéro_noeud; List suivant; entier valeur)
* Classe Graph (List tableau[])
* Classe Element (entier sommet, entier distance)

Problème 1 : Vérifier si entre deux sommets, il y a bien un arc ou pas.

La méthode se présente sous la forme : Verif_arc(sommet de départ, sommet d'arrivée)

Je pensais retourner la distance du sommet de départs (cette valeur correspond bien à la valeur de l'arc entre les 2 sommets considérés). Mon problème est que dans un graphe, un sommet peut accéder à plusieurs autres sommets.
Comment faire pour "dire" que le sommet suivant est le sommet "d'arrivée" et pas un autre ?
Je ne vois pas le lien entre les 2 sommets.

Merci d'avance pour vos réponses

[kwariz]

A ma disposition, j'ai 3 classes :
* Classe List (entier numéro_noeud; List suivant; entier valeur)
* Classe Graph (List tableau[])
* Classe Element (entier sommet, entier distance)

Problème 1 : Vérifier si entre deux sommets, il y a bien un arc ou pas.

La méthode se présente sous la forme : Verif_arc(sommet de départ, sommet d'arrivée)

Salut,
Tu me dis si je décode bien:
verif_arc sera une méthode de Graph, List est une liste d'adjacence, tableau est une matrice (creuse) d'adjacence.

La réponse est immédiate, il existe un arc entre u et v de G si v est présent dans la liste d'adjacence de u. En gros si tableau[u] contient v, dans ton cas, ou tout du moins s'il le contient et que valeur est non nulle (qu'est valeur ?), ou quelque chose dans ce genre.

C'est bien ça ta question ?

[JohnKr]

Bonjour,

Non, non c'est bien cela.
Votre réponse m'a beaucoup aidé.
Je vous remercie et bonne journée à vous.