Discussion :

[Premium]

Bonjour,

j'aurais besoin d'aide pour ceci.
Supposons que j'ai l'arbre suivant :

Code :

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

1
2
3
4
5
6
7
8
 
                                           A
                                         /   \
                                        B     D
                                      /  |    |
                                    C   E     E
                                    |    |    |
                                    D   F     G

Je voudrais savoir comment faire pour avoir les distances minimales depuis un sommet.

Par exemple, si on souhaite les distances minimales depuis le sommet A, on aurait :
B,1 D,1 C,2 E,2 E,2 D,3 F,3 G,3
lorsqu'un sommet apparait plusieurs fois, il faut garder le plus petit .
Dans l'exemple, entre D,1 et D,3 on garderait D,1 et entre E,2 et E,2 on garderait E,2

Merci d'avance

[mat.M]

Basiquement il faut faire parcourir récursivement l'arbre , déterminer le nombre de noeuds parcourus pour chaque branche , mémoriser chaque parcours dans une pile et trier cette pile.
Le parcours le plus petit est le bon

Jette un coup d'oeil sur l'algo de Djikstra

[Premium]

Basiquement il faut faire parcourir récursivement l'arbre , déterminer le nombre de noeuds parcourus pour chaque branche , mémoriser chaque parcours dans une pile et trier cette pile.
Le parcours le plus petit est le bon

Jette un coup d'oeil sur l'algo de Djikstra

L'algo de Djikstra marche sur des arbres ?

[FrancisSourd]

Fusionne les sommets identiques. Tu obtiens un graphe:

Code :

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

1
2
3
4
5
6
7
 
 
a----b----e-----g
|    |    |
|    c    |
|    |    |
-----d-----

Calcule les plus courts chemins à partir de a.
Comme tu as besoin des plus courts chemins en nombre d'arêtes, un parcours en largeur suffit et cela se fait en O(m) où m est le nombre d'arêtes.

[FrancisSourd]

L'algo de Djikstra marche sur des arbres ?

Bien sûr car un arbre est un graphe... mais c'est enfoncer un clou avec un marteau-pilon car il n'y a qu'un seul chemin entre deux sommets d'un arbre.

[Premium]

Fusionne les sommets identiques. Tu obtiens un graphe:

Code :

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

1
2
3
4
5
6
7
 
 
a----b----e-----g
|    |    |
|    c    |
|    |    |
-----d-----

Calcule les plus courts chemins à partir de a.
Comme tu as besoin des plus courts chemins en nombre d'arêtes, un parcours en largeur suffit et cela se fait en O(m) où m est le nombre d'arêtes.

Salut,
tu l'obtiens comment la fusion ?
Le problème, est que j'ai écrit les fonctions de gestion de l'arbre ... je ne peux pas tout changer pour utiliser un graphe.

[Jean-Marc.Bourguet]

Fusionne les sommets identiques. Tu obtiens un graphe:

Code :

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

1
2
3
4
5
6
7
 
 
a----b----e-----g
|    |    |
|    c    |
|    |    |
-----d-----

Calcule les plus courts chemins à partir de a.
Comme tu as besoin des plus courts chemins en nombre d'arêtes, un parcours en largeur suffit et cela se fait en O(m) où m est le nombre d'arêtes.

Comment tu fais pour fusionner. Si j'ai

Code :

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

1
2
3
a--b--c--d
|
+--c

Je vois mal comment faire une fusion en un graphe qui me trouve a--c comme chemin mais pas a--c--d.

Une solution est de faire un parcours en largeur sur l'arbre -- autrement Dijsktra sur l'arbre avec un test sur le label plutot que sur le noeud.

[FrancisSourd]

Comment tu fais pour fusionner. Si j'ai

Code :

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

1
2
3
a--b--c--d
|
+--c

Je vois mal comment faire une fusion en un graphe qui me trouve a--c comme chemin mais pas a--c--d.

Dans ma compréhension du problème, je pensais effectivement donner la valeur 2 au noeud d (de l'exemple ci-dessus). Mais à la relecture du problème, c'est sans doute plutôt 3 quand je relis le problème. Premium, confirmes-tu?

Si d doit prendre la valeur 3, il suffit de calculer la profondeur de chaque noeud par un parcours quelconque (largeur, profondeur ou autre...) puis, pour chaque label a,b,c... regarder sa hauteur minimale. Cela se fait en O(n) (n est le nombre de noeuds dans l'arbre).