Discussion :

[Sve@r]

Bonjour à tous

J'ai un soucis d'algorithmique avec la théorie des graphes.

Prenons par exemple un graphe où l'ensemble des arrêtes ne peut pas reboucler, comme illustré ici


Si on part du sommet "0" et qu'on compte "1" à chaque niveau, il faudra alors 4 itérations pour atteindre l'ensemble des sommets


Si maintenant on part du sommet "2", alors il ne faudra plus que 2 itérations


Mon problème est de trouver ce sommet "2" permettant à un fluide qui s'en écoulerait d'atteindre tous les autres en un minimum d'itération. J'ai écrit un algorithme récursif qui pour un sommet donné me donne la profondeur maximale du graphe mais c'est trop long de tout tester. Même en optimisant en fournissant à mon algorithme la profondeur minimale déjà trouvée pour un sommet "X" et en le faisant s'arrêter dès qu'il descend plus bas en testant le sommet "Y" c'est encore trop long.

Donc ma question: y a-t-il un autre moyen de trouver ce "sommet 2" sans tout tester ???

Merci de votre attention

[pseudocode]

Bonjour,

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher.

Si c'est une question sérieuse, alors la réponse c'est la médiane.

la médiane est la valeur centrale qui minimise la valeur moyenne des écarts absolus => c'est celle qui est "en moyenne" la moins éloignée de toutes les autres.

A+

[picodev]

Bonjour,
Dans le cas d'un graphe non dirigé acyclique connexe, tu peux simplement retirer toutes les feuilles jusqu'à trouver le nœud ou les nœuds qui seront le ou les centres des graphes.
Dans ton exemple, on commencera par supprimer les nœuds 0,4,5 et 7 et il restera les nœuds 1,2,3 et 6. Ensuite tu supprimeras les nœuds 1,3 et 6, il ne restera que le nœud 2 → le centre de ton graphe.

Si tu avais eu un graphe :

Alors les centres auraient été les nœuds 1 et 2.

[Flodelarab]

Bonjour

Ce rappel de CodingGame m'a donné envie de faire le "puzzle de la semaine". Facile, marrant et rapide, en bash.

[Sve@r]

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher.

Merci de ton intérêt à mon souci. Effectivement c'est bien pour ce site de jeux algorithmiques. Mais on n'a pas le droit d'en parler ici car c'est aussi un site marchand et Developpez ne veut pas qu'on fasse de pubs pour des sites marchands.
Sinon effectivement c'est bien ce puzzle qui me gêne. J'ai d'ailleurs repris le même exemple (mais j'ai eu la délicatesse de refaire un dessin et non pomper le dessin d'origine). Ceci dit, je n'ai pas l'impression de tricher en venant ici car mon algorithme fonctionne et trouve le noeud central. Sauf qu'il ne le trouve pas assez rapidement et je reste bloqué à 80%...

Si c'est une question sérieuse, alors la réponse c'est la médiane.
la médiane est la valeur centrale qui minimise la valeur moyenne des écarts absolus => c'est celle qui est "en moyenne" la moins éloignée de toutes les autres.

Mouais. Je veux bien une médiane (j'avais aussi pensé au barycentre) mais une médiane de quoi ??? Du n° des noeuds ? De la distance qui sépare chaque noeud du noeud médian ? Dans le premier cas ça n'a pas de sens et dans le second il faut alors calculer chaque distance ce que je fais déjà.

Dans le cas d'un graphe non dirigé acyclique connexe, tu peux simplement retirer toutes les feuilles jusqu'à trouver le nœud ou les nœuds qui seront le ou les centres des graphes.
Dans ton exemple, on commencera par supprimer les nœuds 0,4,5 et 7 et il restera les nœuds 1,2,3 et 6. Ensuite tu supprimeras les nœuds 1,3 et 6, il ne restera que le nœud 2 → le centre de ton graphe.

Super !!!
Effectivement, c'est comme l'oeuf de Colomb.

Un grand merci pour ton aide.

[Trap D]

si c'est juste pour franchir un niveau à CodinGame, alors je te laisse chercher.

Décidément, on retrouve les exos de CG partout, plus ou moins modifiés pour ne pas apparaitre trop clairement, je suis sur qu'on en trouve aussi sur S.O. en cherchant bien.