Bonjour a tous !

Voila, je cherche un algorithme qui pourrait tester si un graphe est connexe, et si non, séparer ses différentes composantes connexes en clusters.

Ma question est : avez-vous un algo qui permette de déterminer si un graphe est connexe ?

cékoi un graphe connexe

je me rappelle avoir vaguement étudié les graphes cette année, mais...

Un graphe est connexe si tu prends n'importe quel point, et tu peux joindre n'importe quel autre point en partant de lui.

Un graphe est non connexe si tu prends un point (ou un sous-graphe) qui est isolé/non-lié au reste du graphe

Parcours simple dans un graphe:
Tu prends un tableau de booléens de la taille de ton ensemble de noeuds, et pour chaque noeud, tu checkes et tu empiles.
Si tu sors du parcours avec tous les noeuds checkés, c'est un graphe connexe.
Si tu sors du parcours sans avoir tout checké, les noeuds contenus dans ta pile forment ta première composante connexe, tu vides la pile et tu recommences en partant d'un noeud non checké jusqu'a avoir parcouru tous les noeuds du graphe.

Un graphe non orienté est connexe si pour tout couple de noeuds U et V il existe un chemin entre U et V (en gros, ton graphe est en un seul bloc, y'a pas de morceaux).

On parle pas de cycles dans un graphe non orienté ? Bon je sais c'est qu'une histoire de terminologie mais quand même

Il me semble que l'algorithme A* peut correspondre à ta recherche, mais je n'en suis pas sûr. Je viens de voir vite fait à quoi il ressemble, ça me semble bon mais à confirmer.

________________________________________
Ma vidéo du moment :
http://youtube.com/watch?v=96Fm5SPsjD0 (Les Kiss Kool, à voir absolument )

"Suicide par défénestration : encore une victime de Qt "

un simple parcours de graphe suffit a reperer toute une composante connexe.
une fois que tu l'as, il suffit de chercher un noeuds qui ne soit pas dedans et de la marquer a son tour
C'est facil a ecrire ca...

"On parle pas de cycles dans un graphe non orienté ?"
Je me suis trompé, mais toi aussi. En fait c'est "une chaîne entre U et V", le chemin étant par nature orienté.
Un cycle est une chaîne dont le premier et le dernier nœuds sont le même nœud. Son pendant dans un graphe orienté est un circuit.

Et A, c'est fait pour trouver un chemin de manière heuristique (optimal pour A*). Pas vraiment le but recherché ici.

A* n'est pas un algorithme exacte, c'est juste une bonne heuristique. Si tu n'arrete pas A* des que tu as trouvé un chemin alors tu va converger vers un chemin optimal. Cependant, tu pourrais calculer un chemin optimal avec un algorithme plus efficace (Dijkstra par exemple, si tous les arcs sont de poids positif).

La question de base est beaucoup plus simple. Il suffit de faire un parcours de graphe (en fait n'importe quel parcours de graphe).

Conflit de vocabulaire je pense. Conformément à ce que j'ai appris, j'appelle A* l'algo sus-cité avec une heuristique admissible, et A les autres cas d'utilisation de cet algorithme. Avec ce nommage, A* est un algorithme admissible, il trouve un chemin optimal. (cf. Wikipedia, je n'ai pas cherché à refaire la preuve)

Merci de me corriger si je me trompe godrik.

Tu appele donc A l'algorithme qui s'arrete la premiere fois que l'on vois le noeud cible. et A* l'algorithme qui s'arrete au moment ou tu es sur que le noeud cible a bien la valeur minimal ?

Je n'avais jamais vu ces nommages la.
Une bonne partie des propriétés de l'algo dépendent de la fonction d'évaluation de distance entre 2 points que l'on utilise. Si cette fonction ne renvoie jamais une superieur a la valeur réele, elle est dites monotone (j'ai l'impression que tu l'appele admissible toi)

Avec ces appelation:
Si la fonction d'evaluation est monotone:
A trouve le plus court chemin.
A* trouve le plus court chemin en plus de temps.

Si la fonction d'evaluation est 0 (elle est donc monotone):
A et A* se comporte comme l'algorithme de Dijkstra

Si la fonction d'evaluation n'est pas monotone:
A ne trouve pas le plus court chemin.
A* trouve le plus court chemin en un temps supérieure a celui de l'algo de Dijkstra.

Encore une fois, je n'ai jamais vu la distinction entre A et A*. Avec cette appelation, je n'ai jamais vu que A (appelé A* a ces moments la).

Deplus, je pense qu'il faut faire attention a ce que raconte wikipedia sur cet algorithme, il y a des remarques qui ne m'ont pas l'air tres catholique. Comme :
"More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes." qui est suffisament imprecis pour etre faux. exponentiel peut etre, mais exponentiel en quoi ? j'imagine: en la longueur nombre de noeud du plus court chemin; mais quand on l'ecrit comme ca, on sous-entends usuellement "en la taille du graphe". Ce dernier est evidement faux si tu utilise un tas de fibonacci pour gerer la liste de noeud.

Parcours en profondeur (dfs), ou un union-find si tu dois rajouter des arcs "dynamiquement".

Ok , merci à vous, et désolé pour le retard