Aller au contenu

Théorie des graphes


Messages recommandés

Je voulais savoir comme il y a des spécialistes du Java, comment vous me conseilleriez d'implenter les graphes ?

Personnellement j'ai fait comme ca :

public class Node {
private int id;
private String nom;
private ArrayList fils = new ArrayList();

public Node(int id, String nom, ArrayList fils){
	this.id = id;
	this.nom = nom;
	this.fils = fils;
}

public class Graphe{
private ArrayList g = new ArrayList();

public void addNode(Node n){
	g.add(n);
}

Il me faudrait un moyen efficace pour répondre à ces questions :

1. Programmer une méthode capable de donner le nombre minimum de noeuds qu'il est necessaire de parcourir pour atteindre un puit partant d'une source.

2. Programmer une méthode capable de donner le nombre maximum de noeuds qu'il est necessaire de parcourir pour atteindre un puit partant d'une source.

3. Concevez un premier itérateur à l'aide d'une classe emboitée permettant de parcourir chaque noeud en profondeur d'abord.

4. Puis un autre type d'itérateur capable de parcourir chaque noeud en largeur d'abord.

Merci d'avance.

Lien vers le commentaire
Partager sur d’autres sites

1. Programmer une méthode capable de donner le nombre minimum de noeuds qu'il est necessaire de parcourir pour atteindre un puit partant d'une source.

Si j'ai bien compris, c'est trouver le plus court chemin, et pour ça il y a de nombreux algorithmes, par exemple Dijkstra, A* (A-star), Ford-Bellman si les arcs peuvent être négatifs...

Lien vers le commentaire
Partager sur d’autres sites

A* pas vraiment, ou alors avec une heuristique vraiment bizarroïde (et en plus tu n'es pas sûr de la convergence). Le top, ça reste Dijkstra, et Dijkstra rajoute une notion de poids à chaque sommet (comme étant le min l'intégrale du parcours depuis la source) ainsi que le prédécésseur.

Mais à mon avis ça marche bien en raisonant pas sommet, et pas par arêtes comme dans d'autres algo :D

Lien vers le commentaire
Partager sur d’autres sites

Archivé

Ce sujet est désormais archivé et ne peut plus recevoir de nouvelles réponses.

×
×
  • Créer...