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) .
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