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

ap3 Messages postés 215 Date d'inscription   Statut Membre Dernière intervention   -  
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   -
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. 


//lon
public static List<Parcours> combinaisonBT(List<Noeud> noeuds, int longueur) {
        Noeud racine;
        List<Parcours> cheminCourant= new ArrayList<>();
        List <Noeud> voisins= new ArrayList <Noeud>();
        List <Parcours> result= new ArrayList <Parcours>();
        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<cheminCourant.size(); j++){
                    result.add(cheminCourant.get(j));
                }

                for (int j = a; j < result.size(); j++) {
                    result.get(j).add(racine);
                }



            }
            return result;
        }
    }
A voir également:

5 réponses

Réponse 1 / 5
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
les résultats sont-ils trop nombreux, trop peu nombreux, pas corrects, ?
 
0
Réponse 2 / 5
ap3 Messages postés 215 Date d'inscription   Statut Membre Dernière intervention   10
 
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.
0
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   1 584
 
je pense que l'algorithme est fondamentalement incorrect. je suggère de décrire l'algorithme et de le programmer ensuite.
0
Réponse 3 / 5
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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 ?
0
Réponse 4 / 5
yg_be Messages postés 23541 Date d'inscription   Statut Contributeur Dernière intervention   Ambassadeur 1 584
 
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.
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 5
KX Messages postés 16761 Date d'inscription   Statut Modérateur Dernière intervention   3 020
 
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<Noeud> {

    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<Parcours> listeCycles(List<Noeud> noeuds) {
        List<Parcours> parcours = new ArrayList<Parcours>();
        for (Noeud noeud : noeuds) {
            Parcours debutParcours = new Parcours();
            debutParcours.add(noeud);
            trouverCycle(parcours, debutParcours, noeud, noeud);
        }
        return parcours;
    }

    private static void trouverCycle(List<Parcours> 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
0

Discussions similaires

Table des matières dont les titres n'apparaissent pas..
Synua -
ggg -

10 réponses