Bonjour,
On m'a conseillé ce forum, je viens donc faire appel à votre aide pour un problème sur un algorithme Tarjan de détection de composantes fortement connexes dans un graphe orienté.
Pour les curieux qui éventuellement ne connaitraient pas, voici le wiki très bien expliqué des composantes fortement connexes :
http://fr.wikipedia.org/wiki/Composa...tement_connexe
Donc voilà, un algorithme existe pour repérer ses composantes : L'algorithme de Tarjan. J'ai essayé de le coder moi-même, mais il semblerait que j'aie quelques soucis :
Voici donc mon algorithme commenté. J'espère que quelqu'un sera en mesure de m'aider.
J'ai laissé les lignes de debug, elles pourront peut-être vous être utiles...
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
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 // Applies Tarjan Algorithm on Graph : this. public void TarjanAlgorithm() { this.index = 0; stack.clear(); if (this != null) { if(this.SetOfVertices != null) { for(Vertex V : SetOfVertices) { tarjan(V); } } } } // Tarjan Function public void tarjan(Vertex v) { v.setIndex(index); // System.out.println("index de "+v.getNumber()+" : "+v.getIndex()); v.setLowLink(index); // System.out.println("lowlink de "+v.getNumber()+" : "+v.getLowLink()); // add to the stack stack.add(v); // if(stack.contains(v)) System.out.println(v.getNumber()+" a bien été empilé"); index++; // for each w of Adjacent Vertex of v for(Vertex w : v.getAdjacentVertices()) { // System.out.println("passage dans les points adjacents au point "+v.getNumber()+" : "+w.getNumber()); // if w.index is undefined if(w.getIndex() == -1) { tarjan(w); v.setLowLink(Math.min(v.getLowLink(), w.getLowLink())); } else { // System.out.println("index de "+w.getNumber()+" : non nul"); if(stack.contains(w)) { v.setLowLink(Math.min(v.getLowLink(), w.getIndex())); // System.out.println("La pile contient "+w.getNumber()); } } } // SCC found if(v.getIndex() == v.getLowLink()) { ArrayList<Vertex> new_scc = new ArrayList<Vertex>(); // pop the stack Vertex w = new Vertex() ; // Pop stack and push scc while( (w.getNumber() != v.getNumber()) && stack.size() != 0) { int x = stack.size() -1; w = stack.remove(x); new_scc.add(w); } SCC scc = new SCC(new_scc); Sccs.add(scc); stack.clear(); } }
Quelques informations utiles :
- Cet algorithme est une méthode de la classe Graphe
- Ils existent des classes Vertex, Edge, et SCC (Strongly Connected Component ou Composante Fortement Connexe)
Partager