Najbardziej efektywny sposób generowania wszystkich potomków wszystkich węzłów w drzewie

Szukam najbardziej wydajnego algorytmu do pobrania drzewa (przechowywanego jako lista krawędzi; LUB jako lista odwzorowań z węzła nadrzędnego na listę węzłów podrzędnych); i stworzyć dla KAŻDEGO węzła listę wszystkich węzłów z niego pochodzących (poziom liścia i poziom nie-liści).

Wdrożenie musi odbywać się za pomocą pętli zamiast recusion, ze względu na skalę; i idealnie powinien być O (N).

To pytanie SO obejmuje standardowe, dość oczywiste rozwiązanie, aby znaleźć odpowiedź na JEDEN węzeł w drzewie. Ale oczywiście powtarzanie tego algorytmu na każdym węźle drzewa jest wysoce nieefektywne (z góry mojej głowy, od O (NlogN) do O (N ^ 2)).

Korzeń drzewa jest znany. Drzewo ma absolutnie dowolny kształt (np. Nie jest N-nary, nie jest w żaden sposób zbalansowany, ma kształt lub formę, nie ma jednolitej głębokości) - niektóre węzły mają 1-2 dzieci, niektóre mają 30K dzieci.

Na poziomie praktycznym (choć nie powinno to wpływać na algorytm) drzewo ma ~ 100–200 000 węzłów.

Jeśli faktycznie chcesz PRODUKOWAĆ każdą listę jako różne kopie, nie możesz mieć nadziei, że w najgorszym przypadku uzyskasz miejsce większe niż n ^ 2. Jeśli potrzebujesz tylko DOSTĘPU do każdej listy:

Wykonałbym przemierzanie drzewa w kolejności zaczynając od korzenia:

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

Następnie dla każdego węzła w drzewie przechowuj minimalną liczbę zamówień i maksymalną liczbę zamówień w poddrzewie (można to łatwo utrzymać przez rekurencję - możesz to symulować za pomocą stosu, jeśli chcesz).

Teraz umieść wszystkie węzły w tablicy A o długości n, w której węzeł o numerze porządkowym i znajduje się w pozycji i. Następnie, gdy musisz znaleźć listę dla węzła X, spójrz na A [X.min, X.max] - zauważ, że ten przedział będzie obejmować węzeł X, który również można łatwo naprawić.

Wszystko to odbywa się w czasie O (n) i zajmuje przestrzeń O (n).

Mam nadzieję, że to pomoże.

Nieefektywną częścią nie jest przemierzanie drzewa, ale budowanie list węzłów. Wydaje się rozsądne stworzenie takiej listy:

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

Ponieważ każdy węzeł potomny jest kopiowany na listę każdego rodzica, w przypadku drzew zrównoważonych uzyskujemy średnio złożoność O (n log n) i najgorszy przypadek O (n²) w przypadku drzew zdegenerowanych, które są naprawdę połączonymi listami.

Możemy upaść na O (n) lub O (1) w zależności od tego, czy musisz przeprowadzić konfigurację, jeśli wykorzystamy sztuczkę leniwego obliczania list. Załóżmy, że mamy plik, child_iterator(node)który daje nam dzieci tego węzła. Następnie możemy w prosty sposób zdefiniować coś descendant_iterator(node)takiego:

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

Rozwiązanie nierekurencyjne jest o wiele bardziej zaangażowane, ponieważ przepływ sterowania iteratorem jest trudny (coroutines!). Zaktualizuję tę odpowiedź później dzisiaj.

Ponieważ przejście do drzewa wynosi O (n), a iteracja po liście jest również liniowa, sztuczka całkowicie odracza koszt, dopóki i tak nie zostanie zapłacony. Na przykład wydruk listy potomków dla każdego węzła ma złożoność najgorszego przypadku O (n²): iteracja po wszystkich węzłach to O (n), podobnie jak iteracja po potomkach każdego węzła, niezależnie od tego, czy są one przechowywane na liście, czy obliczone ad hoc .

Oczywiście to nie zadziała, jeśli potrzebujesz rzeczywistej kolekcji do pracy.

Ten krótki algorytm powinien to zrobić, spójrz na kod public void TestTreeNodeChildrenListing()

Algorytm faktycznie przechodzi kolejno przez węzły drzewa i prowadzi listę rodziców bieżącego węzła. Zgodnie z wymaganiami bieżący węzeł jest dzieckiem każdego węzła nadrzędnego, który jest dodawany do każdego z nich jako dziecko.

Ostateczny wynik jest przechowywany w słowniku.

    [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; }
        }
    }
}

Zwykle wystarczy zastosować podejście rekurencyjne, ponieważ pozwala ono na zmianę kolejności wykonywania, dzięki czemu można obliczyć liczbę liści zaczynając od liści w górę. Ponieważ musisz użyć wyniku wywołania rekurencyjnego, aby zaktualizować bieżący węzeł, przygotowanie wersji rekurencyjnej wymagałoby specjalnego wysiłku. Jeśli nie podejmiesz tego wysiłku, to oczywiście takie podejście po prostu rozbije Twój stos dla dużego drzewa.

Biorąc pod uwagę, że zdaliśmy sobie sprawę, że główną ideą jest uzyskanie kolejności zapętlania, zaczynając od liści i wracając do korzenia, naturalną ideą, która przychodzi na myśl, jest wykonanie sortowania topologicznego na drzewie. Wynikową sekwencję węzłów można przesuwać liniowo, aby zsumować liczbę liści (zakładając, że można zweryfikować, że węzeł jest liściem w O(1)). Ogólna złożoność czasowa rodzaju topologicznego wynosi O(|V|+|E|).

Zakładam, że twoja Njest liczbą węzłów, która |V|zwykle byłaby (z nomenklatury DAG). Z Edrugiej strony wielkość zależy w dużej mierze od aromatu twojego drzewa. Na przykład drzewo binarne ma co najwyżej 2 krawędzie na węzeł, dlatego O(|E|) = O(2*|V|) = O(|V|)w takim przypadku powstałby ogólny O(|V|)algorytm. Pamiętaj, że ze względu na ogólną strukturę drzewa nie możesz mieć czegoś takiego O(|E|) = O(|V|^2). W rzeczywistości, ponieważ każdy węzeł ma unikalny element nadrzędny, możesz mieć co najwyżej jedną krawędź do zliczenia na węzeł, jeśli weźmiesz pod uwagę tylko relacje nadrzędne, więc dla drzew mamy taką gwarancję O(|E|) = O(|V|). Dlatego powyższy algorytm ma zawsze liniowy rozmiar drzewa.