Moyen le plus efficace pour générer tous les descendants de tous les nœuds dans une arborescence

Je recherche l'algorithme le plus efficace pour prendre un arbre (stocké sous forme de liste d'arêtes; OU sous forme de liste de mappages du nœud parent vers une liste de nœuds enfants); et produire, pour CHAQUE nœud, une liste de tous les nœuds qui en sont issus (niveau feuille et niveau non feuille).

La mise en œuvre doit se faire via des boucles au lieu de la récusion, en raison de l'échelle; et devrait idéalement être O (N).

Cette question SO couvre une solution standard assez évidente pour trouver la réponse pour UN nœud dans une arborescence. Mais évidemment, répéter cet algorithme sur chaque nœud d'arbre est très inefficace (du haut de ma tête, O (NlogN) à O (N ^ 2)).

La racine de l'arbre est connue. L'arbre est de forme absolument arbitraire (par exemple pas N-naire, pas équilibré de quelque façon que ce soit, forme ou forme, pas de profondeur uniforme) - certains nœuds ont 1-2 enfants, certains ont 30K enfants.

Sur le plan pratique (bien que cela ne devrait pas affecter l'algorithme), l'arbre a environ 100 000 nœuds.

Si vous voulez réellement PRODUIRE chaque liste sous forme de copies différentes, vous ne pouvez pas espérer obtenir un espace supérieur à n ^ 2 dans le pire des cas. Si vous avez juste besoin d'ACCÈS à chaque liste:

Je voudrais effectuer une traversée dans l'ordre de l'arbre à partir de la racine:

http://en.wikipedia.org/wiki/Tree_traversal

Ensuite, pour chaque nœud de l'arborescence, stockez le nombre minimum dans l'ordre et le nombre maximum dans son sous-arbre (cela est facilement maintenu par récursivité - et vous pouvez simuler cela avec une pile si vous le souhaitez).

Maintenant, vous mettez tous les nœuds dans un tableau A de longueur n où le nœud avec le numéro d'ordre i est en position i. Ensuite, lorsque vous devez trouver la liste d'un nœud X, vous regardez dans A [X.min, X.max] - notez que cet intervalle comprendra le nœud X, qui peut également être facilement corrigé.

Tout cela est accompli en temps O (n) et prend de l'espace O (n).

J'espère que ça aide.

La partie inefficace ne traverse pas l'arbre, mais construit les listes de nœuds. Il semblerait judicieux de créer la liste comme ceci:

descendants[node] = []
for child in node.childs:
    descendants[node].push(child)
    for d in descendants[child]:
        descendants[node].push(d)

Étant donné que chaque nœud descendant est copié dans la liste de chaque parent, nous nous retrouvons avec une complexité O (n log n) en moyenne pour les arbres équilibrés, et O (n²) dans le pire des cas pour les arbres dégénérés qui sont vraiment des listes liées.

Nous pouvons passer à O (n) ou O (1) selon que vous devez effectuer une configuration si nous utilisons l'astuce de calcul des listes paresseusement. Supposons que nous ayons un child_iterator(node)qui nous donne les enfants de ce nœud. Nous pouvons alors définir trivialement un descendant_iterator(node)comme ceci:

def descendant_iterator(node):
  for child in child_iterator(node):
    yield from descendant_iterator(child)
  yield node

Une solution non récursive est beaucoup plus impliquée, car le flux de contrôle des itérateurs est délicat (coroutines!). Je mettrai à jour cette réponse plus tard dans la journée.

Puisque la traversée d'un arbre est O (n) et que l'itération sur une liste est également linéaire, cette astuce reporte complètement le coût jusqu'à ce qu'il soit payé de toute façon. Par exemple, l'impression de la liste des descendants pour chaque nœud a la complexité du pire des cas O (n²): l'itération sur tous les nœuds est O (n) et l'itération sur les descendants de chaque nœud, qu'ils soient stockés dans une liste ou calculés ad hoc .

Bien sûr, cela ne fonctionnera pas si vous avez besoin d'une collection réelle pour travailler.

Ce court algorithme devrait le faire, jetez un œil au code public void TestTreeNodeChildrenListing()

L'algorithme parcourt en fait les nœuds de l'arbre en séquence et conserve la liste des parents du nœud actuel. Selon vos besoins, le nœud actuel est un enfant de chaque nœud parent, il est ajouté à chacun d'eux en tant qu'enfant.

Le résultat final est stocké dans le dictionnaire.

    [TestFixture]
    public class TreeNodeChildrenListing
    {
        private TreeNode _root;

        [SetUp]
        public void SetUp()
        {
            _root = new TreeNode("root");
            int rootCount = 0;
            for (int i = 0; i < 2; i++)
            {
                int iCount = 0;
                var iNode = new TreeNode("i:" + i);
                _root.Children.Add(iNode);
                rootCount++;
                for (int j = 0; j < 2; j++)
                {
                    int jCount = 0;
                    var jNode = new TreeNode(iNode.Value + "_j:" + j);
                    iCount++;
                    rootCount++;
                    iNode.Children.Add(jNode);
                    for (int k = 0; k < 2; k++)
                    {
                        var kNode = new TreeNode(jNode.Value + "_k:" + k);
                        jNode.Children.Add(kNode);
                        iCount++;
                        rootCount++;
                        jCount++;

                    }
                    jNode.Value += " ChildCount:" + jCount;
                }
                iNode.Value += " ChildCount:" + iCount;
            }
            _root.Value += " ChildCount:" + rootCount;
        }

        [Test]
        public void TestTreeNodeChildrenListing()
        {
            var iteration = new Stack<TreeNode>();
            var parents = new List<TreeNode>();
            var dic = new Dictionary<TreeNode, IList<TreeNode>>();

            TreeNode node = _root;
            while (node != null)
            {
                if (node.Children.Count > 0)
                {
                    if (!dic.ContainsKey(node))
                        dic.Add(node,new List<TreeNode>());

                    parents.Add(node);
                    foreach (var child in node.Children)
                    {
                        foreach (var parent in parents)
                        {
                            dic[parent].Add(child);
                        }
                        iteration.Push(child);
                    }
                }

                if (iteration.Count > 0)
                    node = iteration.Pop();
                else
                    node = null;

                bool removeParents = true;
                while (removeParents)
                {
                    var lastParent = parents[parents.Count - 1];
                    if (!lastParent.Children.Contains(node)
                        && node != _root && lastParent != _root)
                    {
                        parents.Remove(lastParent);
                    }
                    else
                    {
                        removeParents = false;
                    }
                }
            }
        }
    }

    internal class TreeNode
    {
        private IList<TreeNode> _children;
        public string Value { get; set; }

        public TreeNode(string value)
        {
            _children = new List<TreeNode>();
            Value = value;
        }

        public IList<TreeNode> Children
        {
            get { return _children; }
        }
    }
}

Normalement, vous utiliseriez simplement une approche récursive, car elle vous permet de changer votre ordre d'exécution afin que vous puissiez calculer le nombre de feuilles à partir des feuilles vers le haut. Étant donné que vous devez utiliser le résultat de votre appel récursif pour mettre à jour le nœud actuel, il faudrait un effort spécial pour obtenir une version récursive de queue. Si vous ne prenez pas cet effort, alors bien sûr, cette approche exploserait simplement votre pile pour un grand arbre.

Étant donné que nous avons réalisé que l'idée principale est d'obtenir un ordre de bouclage commençant aux feuilles et remontant vers la racine, l'idée naturelle qui vient à l'esprit est d'effectuer un tri topologique sur l'arbre. La séquence de nœuds résultante peut être parcourue linéairement afin de additionner le nombre de feuilles (en supposant que vous pouvez vérifier qu'un nœud est une feuille O(1)). La complexité temporelle globale du tri topologique est O(|V|+|E|).

Je suppose que votre Nest le nombre de nœuds, qui serait |V|généralement (à partir de la nomenclature DAG). La taille de E, d'autre part, dépend fortement de l'arité de votre arbre. Par exemple, un arbre binaire a au plus 2 bords par nœud, donc O(|E|) = O(2*|V|) = O(|V|)dans ce cas, ce qui entraînerait un O(|V|)algorithme global . Notez qu'en raison de la structure globale d'un arbre, vous ne pouvez pas avoir quelque chose comme O(|E|) = O(|V|^2). En fait, puisque chaque nœud a un parent unique, vous pouvez avoir au plus une arête à compter par nœud lorsque vous ne considérez que les relations parentales, donc pour les arbres, nous avons une garantie O(|E|) = O(|V|). Par conséquent, l'algorithme ci-dessus est toujours linéaire dans la taille de l'arbre.