Récupérer les sommets constituant un cycle d'un graphe orienté
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" :
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
| 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;
} |
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.
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
