Discuter:Algorithmes de connexité basés sur des pointeurs

Un article de Wikipédia, l'encyclopédie libre.

"Ainsi, la recherche d'une solution de complexité linéaire est toujours d'actualité.

" J'ai comme un doute, là : on n'a pas de preuve théorique que, justement, ce n'est tout simplement pas possible de faire mieux que nlog(n) ? gem 6 avr 2005 à 21:05 (CEST) j'ai vérifié t'as raison Franckyboy 6 avr 2005 à 21:17 (CEST)

[modifier] Algorithme statique ou évolutif ?

Je ne suis pas sûr de bien comprendre le problème présenté dans cet article. Le texte semble présenter des « méthodes évolutives » (algorithmes en ligne/on-line algorithms) basées sur des structures de gestion d'ensembles disjoints (union-find). Si tel est le cas, il faudrait, je pense, commencer par dire que dans le cas statique un parcours (en profondeur ou en largeur) permet de déterminer toutes les composantes connexes d'un graphe en temps linéaire.

Concernant les algorithmes présentés, il manque le pseudo-code principal. Les différentes procédures union et la fonction racine ne sont jamais appelées depuis une procédure globale.

Pour le résultat théorique de Tarjan, quelqu'un a-t-il une référence ? La complexité minimale est-elle Ω(nlog(n)), Ω(plog(n) ou Ω(p + nlog(n) ?

Jfheche 22 jun 2005 à 21:34 (CEST)

[modifier] quoi ?

Cet article est très mauvais car il peut laisser penser que l'on ne connaitra jamais d'algorithme linéaire déterminant si un graphe est ou non connexe.

Or déterminer la connexité d'un graphe est un problème élémentaire, qu'un parcours en largeur ou en profondeur résout avec une délicieuse simplicité et une complexité linéaire.

Si ces algorithmes sont jugés trop peu intéressant par l'auteur, les algorithmes linéaires (comme celui de Tarjan, justement) servant à déterminer si un graphe orienté est ou non fortement connexe lui auraient permis de satisfaire son goût de la difficulté, tout en approfondissant le sujet.

Plegrand 29 juillet 2005 à 22:09 (CEST)

Le probleme se resout en temps lineaire d'apres moi egalement. Il serait important de preciser qu'avec une bonne implementation : Un parcours en profondeur remplissant un tableau de marque puis 1 test marque[sommet1]=marque[sommet2](temps constant) suffit pour obtenir le resultat souhaité. sauf erreur de ma part (ce qui est possible car je ne comprend pas l'interet de l'article) Log0 23 mai 2006 à 00:52 (CEST)