Recherche de la hauteur de tous les nœuds d'une forêt

8

J'ai une forêt, c'est-à-dire des nœuds avec des bords dirigés et aucun cycle (dirigé ou non). Je définis la hauteur d'un sommetv comme 0 s'il n'a pas d'arêtes entrantes, ou le nombre maximum d'arêtes à parcourir en sens inverse pour atteindre un sommet de hauteur 0. entrez la description de l'image ici

Je sais également que le degré moyen d'un nœud est une petite constante, disons environ 2. Pour trouver la hauteur de tous les sommets, je peux penser à deux algorithmes:

Algorithme de marche

  1. Parcourez et marquez h=0 pour les sommets sans arêtes entrantes.
  2. Pour chaque sommet avec h=0, suivez les bords sortants, en mettant à jour la hauteur de chaque sommet rencontré si sa hauteur précédente est plus petite.

Algorithme de frontière

  1. Parcourez et marquez h=0 pour les sommets sans arêtes entrantes, et marquez-les comme frontière.
  2. Pour chaque sommet de frontière, voyez si son parent a des enfants à la frontière ou en dessous. Si c'est le cas, marquez le parent comme ayant 1plus la plus grande hauteur parmi ses enfants. Marquez le parent comme étant à la frontière.
  3. Répétez 2 jusqu'à ce qu'il n'y ait rien au-delà de la frontière.

Mes questions:

  1. Y a-t-il un nom pour ce problème et une solution la plus rapide bien connue?
  2. J'ai tendance à penser simplement en remontant de toutes les h=0vertices est la solution la plus rapide. Ai-je raison?
bande passante élevée
la source

Réponses:

7

Tout d'abord, cela dépend un peu de la façon dont vous pouvez accéder à vos données pour dire quels algorithmes fonctionnent le mieux.

Quoi qu'il en soit, je suggère de déterminer les hauteurs de manière descendante plutôt que de bas en haut. Personnellement, je pense qu'une approche descendante est conceptuellement plus agréable et plus facile à analyser. Pour tout sommetv dans la forêt il est vrai que

height(v)={(maxu child of vheight(u))+1if u is not a leaf0otherwise.

Vous pouvez donc rechercher toutes les racines, puis déterminer les hauteurs en divisant une conquête. Vous toucherez chaque sommet au maximum deux fois (recherche des racines + traversée). Dans l'approche que vous avez suggérée, vous devrez peut-être toucher plusieurs fois certains sommets.

Btw, puisque vous avez une forêt, vous avez moins d'arêtes que de sommets, donc vous savez que vous avez un degré moyen inférieur à deux (et donc vous pouvez tester les racines en temps linéaire).

A.Schulz
la source
+1; les solutions récursives sont souvent plus faciles à analyser. Cela dépend également si vous avez déjà des pointeurs enfants ou non, et si vous souhaitez une solution basée sur la boucle ou la récursivité.
Joe
J'aime l'analyse! Quelqu'un peut-il aider les débutants à indiquer également comment convertir cela en forme itérative?
highBandWidth
4

Je ne sais pas si ce problème a un nom officiel ou non. Votre titre résume assez bien. Monter à partir des nœuds de hauteur 0 sera rapide, à condition de prendre soin d'éviter les travaux en double. Supposons que vous ayez un nœud avec de nombreux enfants et un long chemin au-dessus de ce nœud jusqu'à la racine. Supposons également que les hauteurs de chacun des enfants soient différentes. Chaque enfant peut mettre à jour la hauteur du nœud en question. C'est bon. Mais vous devez également éviter de mettre à jour le long chemin au-dessus de ce nœud jusqu'à ce que tous ses enfants aient signalé leurs hauteurs.

L'algorithme résultant s'exécutera en temps linéaire et le pseudo-code ressemblerait à ceci:

initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q
Joe
la source
3

Un problème si similaire qu'il pourrait être intéressant est «Préfixe parallèle sur les arbres dirigés enracinés». L'algorithme trouve le nombre d'arêtes à la racine de chaque nœud. Ainsi, les racines se retrouvent avec la valeur 0, tandis que par exemple le nœud en bas à droite se retrouverait avec une valeur de deux.

Notez que l'algorithme ci-dessous résout le problème plus général des bords pondérés, mais vous pouvez simplement initialiser le W (i) à 1 pour tout i. Et le successeur de chaque nœud i est donné par P (i) = j.

for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

L'image ci-dessous illustre la "réduction de moitié" des longueurs de trajet et rend le temps d'exécution logarithmique facile à comprendre. Il ne montre cependant pas les hauteurs de nœud calculées.

entrez la description de l'image ici

(extrait de "Introduction to Parallel Algorithms" de Joseph Jaja).

Utilisant plusieurs processeurs, il est résoluble en temps O (lg n), mais utilise des opérations O (n lg n). Il existe un hack pour le ramener au travail linéaire, mais il est légèrement impliqué.

Le chat unfun
la source
Merci! qu'est-ce que cela S(i)représente?
highBandWidth
Le nœud successeur. Donc, dans l'itération, l'un des arbres de droite, S (9) = 10, S (10) = 11, S (11) = 12, S (12) = 13 et W (9) = 1, W (10) = 1 , W (11) = 1, W (12) = 1. Dans l'itération deux, S (9) = 11, S (10) = 12, S (11) = 13, S (12) = 13 et W (9) = 2, W (10) = 2, W (11) = 2, W (12) = 1. Dans l'itération trois, S (9) = 13, S (10) = 13, S (11) = 13, S (12) = 13 et W (9) = 2 + 2, W (10) = 2 + 1, W (11) = 2, W (12) = 1.
The Unfun Cat
Vous devez imaginer que tous les S (i) et W (i) sont mis à jour en même temps lorsque vous essayez de travailler sur les détails. Cela peut être obscur, mais je voulais le poster car c'est un problème parallèle classique et très proche de ce que vous avez décrit.
The Unfun Cat