Discussion :

[proc02]

Salut à tous,

J'ai un graphe orienté et je souhaite parcourir les arcs [chaque arc visité une seule fois] de ce graphe mais je suis un peu bloqué je présente l'algorithme que j'essaie d'appliquer et aussi mon début de code.
Algorithme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 procedure DFS(G, v):
     label v as explored
     for all edges e in G.incidentEdges(v) do
       if edge e is unexplored then
             w = G.adjacentVertex(v, e)
             if vertex w is unexplored then
                 label e as a discovered edge
              recursively call DFS(G, w)
             else
               label e as a back edge

Bout de code:

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
 
public ArrayList<Noeud> oneTour(Noeud <T> s,ArrayList<Noeud> ch){
		ArrayList<Arc<T>> chemin=new ArrayList<>();
		ch=new ArrayList<>();
		ch.add(s);
		s.setMarque(true);
		List<Arc<T>> out=s.getOutArcList();
		for(Arc<T>e :out){
			Noeud<T> w= e.getTo();
			if((e.mark==false)){
				chemin.add(e);
				ch.add(w);
			}
			oneTour(w,ch);
 
		}

Ce code ne fonctionne pas car m'affiche comme erreur StackOverflowError
J'ai besoin de vos aides [conseil, correction ...].
Merci à vous.

[joel.drigo]

Salut,

L'erreur StackOverflowError signifie que tu as un appel récursif illimité : comme la pile, elle, est limitée, tu obtiens une erreur lors du dépassement de cette limite.

Tu obtiens cette erreur parce que la méthode oneTour s'appelle récursivement sans autre condition que celle qu'il existe un arc partant du nœud visité, ce qui est toujours le cas, sauf si tu pars d'un nœud isolé dès le début.

Comme, justement, tu dois visiter chaque arc un seule fois, il te faut marquer les nœuds et/ou arcs comme visités au fur et à mesure du parcourt, et tester cet état pour éviter de visiter à nouveau.

On voit que ton code ne respecte pas directement ton algorithme : il y a 2 if dans l'algo et un seul dans le code, et il y a un else dans l'algo qui n'est pas dans le code...

[proc02]

Merci pour votre réponse cela m'a inspiré énormément. Par contre je me suis orienté vers d'autre types d'algorithmes plus spécialisés tels que l'algorithme de Fleury et ça donne un quelque chose qui me donne satisfaction.

Merci!!!