Le plus long chemin dans un arbre non dirigé avec un seul parcours

44

Il existe cet algorithme standard pour rechercher le plus long chemin dans les arbres non dirigés à l'aide de deux recherches en profondeur:

  • Démarrez DFS à partir d'un sommet aléatoire et recherchez le sommet le plus éloigné. disons qu'il est .v vv
  • Maintenant, démarrez un DFS à partir de pour trouver le sommet le plus éloigné. Ce chemin est le plus long chemin du graphique.v

La question est de savoir si cela peut être fait plus efficacement. Peut-on le faire avec un seul DFS ou BFS?

(Cela peut être décrit de manière équivalente comme le problème du calcul du diamètre d'un arbre non dirigé.)

emmy
la source
2
Ce que vous cherchez est aussi appelé le diamètre de l’arbre. (Sur les arbres, "le plus long chemin" et "le plus long" sont la même chose car il n'y a qu'un seul chemin reliant deux nœuds.)
Raphael

Réponses:

22

Nous effectuons une recherche en profondeur d'abord en ordre postérieur et nous agrégons les résultats en route, c'est-à-dire que nous résolvons le problème de manière récursive.

Pour chaque nœud avec les enfants (dans l’arborescence de recherche), il existe deux cas:u 1 , , u kvu1,,uk

  • Le plus long chemin de se trouve dans l’un des sous-arbres .T u 1 , , T u kTvTu1,,Tuk
  • Le plus long chemin dans contient . vTvv

Dans le second cas, nous devons combiner le ou les plus longs chemins de dans l'un des sous-arbres; ce sont certainement ceux qui ont les feuilles les plus profondes. La longueur du chemin est alors si , ou si , avec le jeu multiple de hauteurs de sous-arbres¹.H ( k ) + H ( k - 1 ) + 2 k > 1 H ( k ) + 1 k = 1 H = { h ( T u i ) | i = 1 , ... , k }vH(k)+H(k1)+2k>1H(k)+1k=1H={h(Tui)i=1,,k}

En pseudo-code, l'algorithme ressemble à ceci:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)        
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

  1. k AA(k) est la petite valeur de (statistique d'ordre).kA
Raphaël
la source
@JeffE Concernant le deuxième commentaire: En effet, et ceci est pris en charge dans la dernière ligne: height1 + height2est la longueur de ce chemin. S'il s'agit bien du plus long chemin, il est choisi par max. C'est aussi expliqué dans le texte ci-dessus, donc je ne vois pas trop votre problème? Vous devez sûrement récidiver afin de déterminer s’il s’agit bien du chemin le plus long, et même si ce n’est pas le cas, cela ne fait pas mal (à juste titre) de récidiver.
Raphaël
@JeffE En ce qui concerne le premier commentaire, le calcul de pour exclut height2explicitement toute height1considération, comment peut-il choisir le même enfant deux fois? Cela a également été expliqué dans le texte d'introduction.
Raphaël
1
Apparemment, nous parlons différents dialectes pseudocodes, car j'ai du mal à comprendre le vôtre. Il serait utile d’ajouter une déclaration explicite en anglais qui longestPathHeight(T)renvoie une paire (h,d), où hest la hauteur Tet dle diamètre de T. (Droite?)
JeffE
@JeffE Right; Je pensais que cela était clair d'après le code, compte tenu de l'explication, mais apparemment, mon extrapolation de "clair" pour d'autres pseudocodes-paradigmes était insuffisante (le mien est Scalaesque, je suppose). Désolé pour la confusion, je clarifie le code (j'espère).
Raphaël
8

Cela peut être résolu d'une meilleure façon. De plus, nous pouvons réduire la complexité temporelle à O (n) en modifiant légèrement la structure des données et en utilisant une approche itérative. Pour une analyse détaillée et de multiples façons de résoudre ce problème avec diverses structures de données.

Voici un résumé de ce que je veux expliquer dans un de mes articles de blog :

Approche récursive - Diamètre de l'arbre Une autre façon d'aborder ce problème est la suivante. Comme nous l'avons mentionné ci-dessus, le diamètre peut

  1. complètement mentir dans le sous-arbre gauche ou
  2. complètement mentir dans le sous-arbre droit ou
  3. peut s'étendre sur la racine

Ce qui signifie que le diamètre peut être dérivé idéalement de

  1. le diamètre de l'arbre gauche ou
  2. le diamètre de l'arbre droit ou
  3. la hauteur du sous-arbre gauche + la hauteur du sous-arbre droit + 1 (1 pour ajouter le nœud racine lorsque le diamètre s'étend sur le nœud racine)

Et nous savons que le diamètre est le chemin le plus long, nous prenons donc le maximum de 1 et 2 au cas où il se trouverait dans le côté ou bien 3 si il couvre la racine.

Approche itérative - Diamètre de l'arbre

Nous avons un arbre, nous avons besoin d'une méta-information avec chacun des nœuds pour que chaque nœud sache ce qui suit:

  1. La hauteur de son enfant gauche,
  2. La hauteur de son enfant juste et
  3. La distance la plus éloignée entre ses nœuds feuilles.

Une fois que chaque nœud a cette information, nous avons besoin d’une variable temporaire pour suivre le chemin maximum. Au moment où l'algorithme se termine, nous avons la valeur de diamètre dans la variable temp.

Maintenant, nous devons résoudre ce problème dans une approche ascendante, car nous n'avons aucune idée des trois valeurs de la racine. Mais nous connaissons ces valeurs pour les feuilles.

Étapes à résoudre

  1. Initialisez toutes les feuilles avec leftHeight et rightHeight à 1.
  2. Initialise toutes les feuilles avec maxDistance à 0, nous faisons en sorte que si l'un des éléments leftHeight ou rightHeight vaut 1, la maxDistance = 0
  3. Montez un par un et calculez les valeurs du parent immédiat. Ce serait facile parce que maintenant nous connaissons ces valeurs pour les enfants.
  4. À un noeud donné,

    • assigne leftHeight au maximum de (leftHeight ou rightHeight de son enfant de gauche).
    • assigne le rightHeight au maximum de (leftHeight ou rightHeight de son enfant droit).
    • Si l'une de ces valeurs (leftHeight ou rightHeight) est égale à 1, la maxDistance est égale à zéro.
    • si les deux valeurs sont supérieures à zéro, maxDistance est défini à leftHeight + rightHeight - 1
  5. Conservez la maxDistance dans une variable temp et si, à l'étape 4, la maxDistance est supérieure à la valeur actuelle de la variable, remplacez-la par la nouvelle valeur maxDistance.
  6. À la fin de l'algorithme, la valeur de maxDistance est le diamètre.
Dharam
la source
1
Qu'est-ce que cela ajoute à ma réponse précédente, en plus d'être moins général (vous ne traitez que des arbres binaires)?
Raphaël
9
Cette réponse est plus lisible et plus facile à comprendre à mon avis (votre pseudocode est très déroutant).
Reggaeguitar
-3

Le code ci-dessous renvoie un chemin de diamètre utilisant un seul parcours DFS. Cela nécessite un espace supplémentaire pour garder trace du meilleur diamètre vu jusqu'à présent, ainsi que du chemin le plus long commençant à un nœud particulier de l'arbre. Il s'agit d'une approche de programmation dynamique basée sur le fait qu'un chemin de plus grand diamètre n'inclut pas la racine, ou est une combinaison des deux plus longs chemins des voisins de la racine. Nous avons donc besoin de deux vecteurs pour garder une trace de cette information.

 int getDiam(int root, vector<vector<int>>& adj_list, int& height, vector<int>& path, vector<int>& diam) {
    visited[root] = true;
    int m1 = -1;
    int m2 = -1;
    int max_diam = -1;
    vector<int> best1 = vector<int>();
    vector<int> best2 = vector<int>();
    vector<int> diam_path = vector<int>();
    for(auto n : adj_list[root]) {
        if(!visited[n]) {
            visited[n] = true;
            int _height = 0;
            vector<int> path1;
            vector<int> path2;
            int _diam = getDiam(n, adj_list, _height, path1, path2);
            if(_diam > max_diam) {
                max_diam = _diam;
                diam_path = path2;
            }
            if(_height > m1) {
                m2 = m1;
                m1 = _height;
                best2 = best1;
                best1 = path1;
            }
            else if(_height > m2) {
                m2 = _height;
                best2 = path1;
            }
        }
    }

    height = m1 + 1;

    path.insert( path.end(), best1.begin(), best1.end() );
    path.push_back(root);

    if(m1 + m2 + 2 > max_diam) {
        diam = path;
        std::reverse(best2.begin(), best2.end());
        diam.insert( diam.end(), best2.begin(), best2.end() );
    }
    else{
        diam = diam_path;
    }


    return max(m1 + m2 + 2, max_diam);
}
Trevor Van Loon
la source
2
Ce n'est pas un site de codage. Nous déconseillons les réponses constituées principalement d’un bloc de code. Au lieu de cela, nous voulons des réponses qui expliquent les idées à la base de l’algorithme et donnent un pseudocode concis (qui ne nécessite aucune connaissance d’un langage de programmation particulier pour être compris). Comment calculez-vous le plus long chemin commençant à un nœud particulier de l'arborescence? (surtout que le plus long chemin peut commencer par aller "en haut" de l'arborescence DFS, c'est-à-dire vers la racine)
DW