Jump to content

Théorie des graphes


Recommended Posts

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.

Link to comment
Share on other 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...

Link to comment
Share on other 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

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.

×
×
  • Create New...