Théorie des graphes

[Soulfly_tribe90]

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.

[tuXXX]

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

[Soulfly_tribe90]

Ouai les algos je les connais parce que je les ai fait en C mais surtout sur l'implementation des graphes : est ce que c'est une bonne méthode comme je le fais ??

[lorinc]

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