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.

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();
		}
	}
J'ai laissé les lignes de debug, elles pourront peut-être vous être utiles...

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)