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

Fermé

ap3 Messages postés 215 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 10 mars 2021 - 18 nov. 2017 à 14:01
KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 - 18 nov. 2017 à 17:21

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:

Quelles sont les 2 orientations possibles d'une page d’un document numérique ?
Supprimer une page word - Guide
Word numéro de page 1/2 - Guide
Changer l'orientation d'une page dans un document Word - Guide
Signer un document word - Guide
Traduire une page web - Guide

5 réponses

Réponse 1 / 5

yg_be Messages postés 22731 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 27 avril 2024 1 477
18 nov. 2017 à 15:02

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

Réponse 2 / 5

ap3 Messages postés 215 Date d'inscription mercredi 13 janvier 2010 Statut Membre Dernière intervention 10 mars 2021 10
18 nov. 2017 à 15:03

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.

yg_be Messages postés 22731 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 27 avril 2024 1 477
Modifié le 18 nov. 2017 à 15:58

je pense que l'algorithme est fondamentalement incorrect. je suggère de décrire l'algorithme et de le programmer ensuite.

Réponse 3 / 5

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
18 nov. 2017 à 16:35

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 ?

Réponse 4 / 5

yg_be Messages postés 22731 Date d'inscription lundi 9 juin 2008 Statut Contributeur Dernière intervention 27 avril 2024 1 477
Modifié le 18 nov. 2017 à 17:11

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.

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

Posez votre question

Réponse 5 / 5

KX Messages postés 16734 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 24 avril 2024 3 015
Modifié le 18 nov. 2017 à 17:25

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

Discussions similaires

[PIX] Commencer chaque poème sur une nouvelle page

Discussions similaires

Newsletters