Arbre: plus long chemin

[fatal_error]

salut,

petit problème d'algorithmie:
J'ai un arbre (donc un graphe sans cycle), avec les composantes connexes.
Je voudrais déterminer pour tous les noeuds de mon arbre, la plus grande distance à root (le noeud tout en haut, qui n'a aucun prédecesseur (c'est le seul à ne pas avoir de prédécesseur)).

On peut considérer que toutes les arrêtes sont de poids 1.
Par exemple suivant ce graphe
A->B->C
A->B->D->C
d(A,C) = 3

pour ca, je peux creer une matrice d'adjacence, l'élever à la puissance n (n étant le nombre de noeuds de l'arbre) et regarder les chemins de longueur n, puis n-1, etc, ce qui me donnera la plus longue distance entre root et un noeud donné.

Mais peut-être ya-t-il plus rapide?

[Doraki]

ton arbre est fini ?

[fatal_error]

oui: il comporte au plus 70 noeuds.

[Dlzlogic]

A mon avis, ça dépend de la façon dont l'arbre est défini.
Si l'organisation est uniquement dans le sens A->B->C, alors en partant d'un noeud chaque fils aura le max entre la distance "actuelle" et celle en cours +1.

[Doraki]

il faudrait compléter la relation d'ordre Ai -> Aj en une relation totale.
Si tu mets tous tes sommets en liste
A0 A1 A2 A3.... An tel que toutes les arêtes vont de Ai vers Aj avec j>i,

tu mets d(A0) = 0 (c'est la racine de l'arbre)
puis pour i=0 à n tu fais pour toute arête Ai -> Aj, d(Aj) := max d(Aj), d(Ai)+1.
Et à la fin tu as ce que tu veux.

Réciproquement si tu as les d pour chaque Ai alors c'est super facile de compléter la relation d'ordre en une relation totale, tu les ordonnes comme tu veux selon la valeur de d. Donc ce n'est pas trop demander de linéariser l'arbre.


Je sais pas trop comment faire pour compléter la relation d'ordre efficacement.
A priori à chaque fois qu'on ajoute un couple dans l'ordre il faut vérifier qu'on introduit pas de cycle et ça peut prendre du temps.
Ou alors on y va au hasard en faisant des corrections au fur et à mesure mais il peut y avoir des corrections en cascade.

[fatal_error]

il faudrait compléter la relation d'ordre Ai -> Aj en une relation totale.
Si tu mets tous tes sommets en liste
A0 A1 A2 A3.... An tel que toutes les arêtes vont de Ai vers Aj avec j>i,

tu mets d(A0) = 0 (c'est la racine de l'arbre)
puis pour i=0 à n tu fais pour toute arête Ai -> Aj, d(Aj) := max d(Aj), d(Ai)+1.
Et à la fin tu as ce que tu veux.

capito + nice

Réciproquement si tu as les d pour chaque Ai alors c'est super facile de compléter la relation d'ordre en une relation totale, tu les ordonnes comme tu veux selon la valeur de d. Donc ce n'est pas trop demander de linéariser l'arbre.

pas capito. que représente d pour les Ai? la distance de quoi a quoi de Ai à Root? (du coup je pourrais marreter la).
j'ai cherché comment linéariser l'arbre, mais jai pas (encore) trouvé. Si tu as un lien, sinon, jvais bien arriver à trouver un truc potable

[Doraki]

j'voulais dire si tu connais les d(root,Ai) pour chaque Ai, ben en triant les sommets Ai selon cette fonction, ben quel que soit ta manière de les arranger entre eux quand t'en as plusieurs avec la même distance, ça te donne un ordre total compatible avec ->

[Dlzlogic]

Bonsoir,
Pour gérer ce type de problème, j'utilise la technique des listes chainées. Le principe est le suivant :
Un noeud est défini par
- des informations diverses
- la liste des noeuds fils sous forme d'adresse
- facultatif, l'adresse du noeud père

L'adresse du noeud père permet de remonter l'arbre à l'envers
La syntaxe de l'application de cela dépend du langage, en C c'est le mieux.

[fatal_error]

j'voulais dire si tu connais les d(root,Ai) pour chaque Ai, ben en triant les sommets Ai selon cette fonction, ben quel que soit ta manière de les arranger entre eux quand t'en as plusieurs avec la même distance, ça te donne un ordre total compatible avec ->

ouais en fait j'ai pas besoin de l'ordre total.
(L'idée derrière ce problème c'est de pouvoir regrouper les noeuds de même distance par rapport à root en "couche", fin de les mettre dans l'ensemble E_d_i(qui contient que les noeuds de distance d_i))

edt: je viens de tilter
Donc ce n'est pas trop demander de linéariser l'arbre.
c'est simplement faire
A0 A1 A2 A3.... An tel que toutes les arêtes vont de Ai vers Aj avec j>i,

c'est clair que c'est plus sexy que mes matrices en n^3 (pire des cas):ptdr: