Algo qui retourne tous les cycles d'un graphe non orienté Fermé

Question

Bonjour, j'ai conçu un algo qui retourne tous les cycles d'un graphe. L'implémentation est en JAVA. J'ai une classe Graphe qui a une liste de sommets (noeuds). Un noeud a une liste de voisins(qui sont aussi des noeuds). Un noeud a un attribut booléen estMarque qui permet de savoir si on est déjà passé sur le noeud lors d'un parcours). Le problème c'est que ma fonction ne retourne pas les bons résultats. Quel est le problème ? Merci d'avance. //lonpublic static List combinaisonBT(List noeuds, int longueur) { Noeud racine; List cheminCourant= new ArrayList<>(); List voisins= new ArrayList (); List result= new ArrayList (); int i, a; //Si la liste a qu'un seul élément if (noeuds.size() == 1) { Parcours p = new Parcours(); p.add(noeuds.get(0)); result.add(p); return result; } else { //Pour chaque noeud for (i = 0; i < noeuds.size(); i++) { //La racine change racine = noeuds.get(i); racine.marquer(); voisins.clear() ; //Vérification des voisins for(Noeud v : racine.getVoisins()) { if(!v.estMarque()){ voisins.add(v); } } //noeudsSansRacine.addAll( racine.getVoisins()); //try{noeudsSansRacine.remove(i);}catch (Exception e){} a = result.size(); //Appel récursif cheminCourant = combinaisonBT(voisins, longueur); racine.nonMarquer(); for(int j= 0;j

yg_be · Answer

les résultats sont-ils trop nombreux, trop peu nombreux, pas corrects, ?

ap3 · Answer

Ils sont pas corrects. Au niveau du nombre je pense qu'il n'y en pas assez.

Les résultats ne sont pas tous de la bonne taille.

KX · Answer

Bonjour,

Si on reprends juste la première condition :

if (noeuds.size() == 1)
{
    Parcours p = new Parcours();
    p.add(noeuds.get(0));
    result.add(p);
    return result;
}
Cela signifie qu'un graphe avec un seul nœud possède un cycle composé de ce seul nœud... Déjà ça c'est faux. Pour avoir un cycle il faudrait au moins 3 nœuds et 3 arcs : A-B, B-C, C-A. D'ailleurs dans cette configuration est-ce que tu considères que A-B-C est le même cycle que B-C-A et C-A-B ou tu les comptes 3 fois ? Peut-être même 6 fois avec C-B-A, B-A-C et A-C-B ?

yg_be · Answer

cela me semble une très bonne idée de le faire par récursivité.
cependant, je ne pense pas que tu puisses utiliser la fonction principale comme fonction récursive.  tu dois plutôt définir une autre fonction qui, elle, sera récursive.
l'idée de marquer les nœuds parcourus peut fonctionner, mais n'est pas très élégante.
je pense qu'il est indispensable de passer à la fonction récursive le noeud de départ et le noeud d'arrivée.

KX · Answer

Voici une manière de faire. PS. Comme je ne sais pas ce que contiennent exactement les classes Parcours et Noeud j'ai fait les miennes en partant des méthodes que tu utilisais déjà (même si ça me chagrine que ce soit les noeuds qui portent leurs propres voisins et qu'il n'y ait aucune notion de graphe là dedans). import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Parcours extends ArrayList { public Parcours(Parcours parcours) { super(parcours); } public Parcours() { super(); } } class Noeud { String id; Noeud[] voisins; public Noeud(String id) { this.id = id; } public Noeud[] getVoisins() { return voisins; } public void setVoisins(Noeud... voisins) { this.voisins = voisins; } @Override public boolean equals(Object obj) { return id.equals(((Noeud) obj).id); } @Override public String toString() { return id; } } public class Cycles { public static List listeCycles(List noeuds) { List parcours = new ArrayList(); for (Noeud noeud : noeuds) { Parcours debutParcours = new Parcours(); debutParcours.add(noeud); trouverCycle(parcours, debutParcours, noeud, noeud); } return parcours; } private static void trouverCycle(List parcoursNoeud, Parcours debutParcours, Noeud racine, Noeud courant) { for (Noeud voisin : courant.getVoisins()) { if (voisin.equals(racine)) { // on revient au départ if (debutParcours.size() > 2) { // on a un cycle Parcours parcours = new Parcours(debutParcours); parcours.add(voisin); parcoursNoeud.add(parcours); } continue; } if (debutParcours.contains(voisin)) {// déjà fait continue; } Parcours suiteParcours = new Parcours(debutParcours); suiteParcours.add(voisin); trouverCycle(parcoursNoeud, suiteParcours, racine, voisin); } } public static void main(String[] args) { Noeud a = new Noeud("A"); Noeud b = new Noeud("B"); Noeud c = new Noeud("C"); Noeud d = new Noeud("D"); Noeud e = new Noeud("E"); Noeud f = new Noeud("F"); a.setVoisins(b, d); b.setVoisins(a, c, d); c.setVoisins(b, e, f); d.setVoisins(a, b, e); e.setVoisins(c, d); f.setVoisins(c); System.out.println(listeCycles(Arrays.asList(a, b, c, d, e, f))); } }La confiance n'exclut pas le contrôle

Algo qui retourne tous les cycles d'un graphe non orienté

5 réponses

Discussions similaires