Bonjour à tous !
Actuellement, je tente de récupérer sous la forme d'une liste (en utilisant std::list), tous les sommets constituant un cycle dans un graphe orienté.
J'ai donc tout d'abord détecté si le graphe comportait un cycle et il y'en a bien un.
Pour faire cette détection, j'ai dans la classe ci-dessous, la méthode "dfs" :
Et j'ai essayé d'intégrer directement le push_back de la liste dans ma fonction de détection (afin de ne pas reparcourir le graphe pour afficher les sommets qui sont dans le cycle), mais en vain.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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 template<typename GraphType>class DirectedCycle { typedef GraphType Graph; private: const Graph& g; std::vector<bool> onStack, marked; bool hasCycle; std::list<int> cycle; void dfs(int v){ onStack.resize(g.V()); marked.resize(g.V()); onStack[v] = true; marked[v] = true; for(int w : g.adjacent(v)) { if (hasCycle) return; if(!marked[w]) { // cycle.push_back(w); dfs(w); } else if (onStack[w]) { hasCycle = true; } } onStack[v] = false; }
Comment faire pour récupérer ses sommets ? Suis-je obligé de reparcourir le grahe dans une autre méthode ?
Je ne comprends pas pourquoi cela ne marche pas... Quelqu'un saurait l'expliquer ?
je suis sur netbeans IDE 8.0.1
Merci de vos réponse
Partager