colorier en deux couleur un graph avec DFS

Le problème exposé dans ce sujet a été résolu.

Salut à tous,
depuis quelques jours, je m'intéresse à la théorie des graphs,
Je me suis donc décidé à coder une exercice simple pour commencer, à savoir: peut-on colorier un graph avec deux couleurs sans que deux noeuds côte à côte aillent la même couleur.

J'ai tenté d'implementer l'algorithme DFS et je suis arrivé à ce qui suit, mais il ne fonctionne pas très bien (ca serait trop beau sinon) L'entrée à la forme:

nombreDeNoeuds nombreD'arret
noeudx voisin
noeudx voisin
noeudx voisin
…

pour la sortie, la fonction dfs renvoie un boolean.

exemples justes:

Pour l'entrée (une ligne)
3 2 //3 noeuds (0,1,2), 2 arrets
0 1
1 2
je reçois:
0{1, }
1{0, 2, }
2{1, }
YES

pour: (un triangle)
3 3
0 1
1 2
2 0
0{1, 2, }
1{0, 2, }
2{1, 0, }
NO
juste aussi

Le problème vient avec cet input:
6 5
0 2
1 2
1 3
2 3
4 5

La fonction dfs devrait me retourner false, mais elle me renvoie true. Les voisins, sont correctement formés, mais elle ne me donne pas le bon résultat. Comment je dois procéder pour arriver à trouver d'où vient le problème ?

Je ne sais pas trop quoi afficher comme message qui pourrait m'aider, si elle me donnait faux à la place de vrai, j'aurais afficher parent et child pour trouver l'emplacement qui pose problème, mais là je suis à cour d'idées (et de motive) :lol: .
le code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//
//  main.cpp
//

#include <iostream>
#include <vector>

std::vector<std::vector<int>> graph;
std::vector<int> color;


bool dfs(int parent) {
  
  for(int child = 0; child < graph.at(parent).size()/*number of child 'parent' has*/; ++child) {
      
      int node = graph.at(parent).at(child);
      
      if(color.at(node)==0) {

          color.at(node) = 3-color.at(parent); //set value 2 then 1 then 2 then 1 ... each dive ( each generation has the floor has the same color )
          
          
          dfs(node); //go and see neigbour to node
          
      } else {
      
          if(color.at(parent) == color.at(node)) {    //node's color == parents color => impossible to colorize with 2 color
              
              return false;
          }
      }
  }
  return true;    //everything is visited and 'if' not triggered so it can be made of 2 color
  
}


int main(int argc, const char * argv[]) {
  
  
  int n, m;                                     //n = node and m = arret
  std::cin >> n >> m;
  
  graph = std::vector<std::vector<int>>(n);
  color = std::vector<int>(n, 0);                //nothing visited yet

  

  for(int i = 0; i < m; i++) {
      int a, b;
      std::cin >> a >> b;                     
      graph.at(a).push_back(b);       //add child b to node a
      graph.at(b).push_back(a);       //add child a to node b
  }
  
  for(int x=0; x<graph.size(); ++x){
      std::cout << x<<"{";
      for(const auto& y: graph.at(x)){
          std::cout<<y<<", ";
      }
      std::cout<<"}\n";
      
  }
  int parentNum = 0;
  color.at(parentNum) = 1;            //starting point
  
  
  dfs(parentNum);
  
  if(dfs(parentNum)){
      std::cout <<"YES";
  }
  else
      std::cout <<"NO";
  
  return 0;
}

Merci de m'avoir accordé un instant ;-)

+0 -0

Salut,

Ligne 23, il faut prendre en compte la valeur de retour de ton fils. Si par exemple ton fils se rend compte qu'il y a un bug dans la coloration que tu es en train de construire (en renvoyant faux), il faut aussi que le pere renvoie faux.

Sinon, dans ton exemple, ton graphe a deux composantes connexes, alors que tu n'en traites qu'une (celle de 0). Il faudrait rajouter une boucle dans ton main. ;)

EDIT : Egalement, ligne 68 tu appelles dfs sans recuperer la valeur qu'elle retourne (et tu fais un deuxieme appel ligne 70, que cette fois tu utilises).

+0 -0

Merci beaucoup,

Ta réponse m'a mener à une autre question: comment différencier les différentes composantes du graph afin de toutes les traités, Je pourrais lancer dfs sur tout les noeuds, le pire cas (en complexité algorithmique) serait lorsque le graph peut être colorier, mais je suppose qu'il y a une méthode plus fine non ?

+0 -0

Je pourrais lancer dfs sur tout les noeuds, le pire cas (en complexité algorithmique) serait lorsque le graph peut être colorier, mais je suppose qu'il y a une méthode plus fine non ?

d3m0t3p

Par exemple, tu peux n'appeler dfs que sur les noeuds qui ne sont pas deja colories. De cette maniere, sur la totalite des appels a dfs, tu ne parcouriras qu'au plus une fois chaque noeud (et chaque nouvel appel dans main correspondra a une nouvelle composante connexe).

+0 -0

si ça intéresse quelqun, voici le code après avoir effectué les modifications proposées par @Lucas-84

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
//
//  main.cpp
//
//  Created by d3m0t3p on 06.12.16.
//

#include <iostream>
#include <vector>

std::vector<std::vector<unsigned long int>> graph;
std::vector<unsigned long int> color;


bool dfs(unsigned long int parent) {

    for(unsigned long int child = 0; child < graph.at(parent).size()/*number of child 'parent' has*/; ++child) {

        unsigned long int node = graph.at(parent).at(child);

        if(color.at(node)==0) {

            color.at(node) = 3-color.at(parent); //set value 2 then 1 then 2 then 1 ... each dive ( each generation at the same floor has the same color )


            return dfs(node);

        } else {

            if(color.at(parent) == color.at(node)) {    //node's color == parent's color => impossible to colorize with 2 color

                return false;
            }
        }
    }
    return true;    //everything is visited and 'if' not triggered so it can be made of 2 color

}


int main(int argc, const char * argv[]) {



    unsigned long  int n, m;
    std::cin >> n >> m;

    graph = std::vector<std::vector<unsigned long int>>(n);
    color = std::vector<unsigned long int>(n, 0);   //nothing visited



    for(size_t i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        graph.at(a).push_back(b);       //add child b to node a
        graph.at(b).push_back(a);       //add child a to node b
    }
    /*
    for(int x=0; x<graph.size(); ++x){          //show node x and his neighbour
        std::cout << x<<"{";
        for(const auto& y: graph.at(x)){
            std::cout<<y<<", ";
        }
        std::cout<<"}\n";

    }*/

    int parentNum = 0;
    color.at(parentNum) = 1;            //starting point


    for(size_t v = 0; v < graph.size(); ++v ){

        if(v == 0){
            if( !dfs(parentNum) ){
                std::cout <<"NO\n";
                return 0;
            }
        }

        if(!color.at(v) ){

            if( !dfs(parentNum) ){
                std::cout <<"NO\n";
                return 0;
            }


        } //we could fusion the two condition, but it's more clear that way
    }
    std::cout <<"YES\n";

    return 0;
}

Si vous avez des remarques, je suis ouvert à toutes propositions

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte