Здравствуйте! Задумался над одной задачей — можно ли вывести все вершины произвольного дерева, использовав O(1) памяти? Почти сразу придумал обход в глубину, но при этом каждая вершина выводится не один раз. Непонятно, как избавиться от этого недоразумения. Может, есть известный алгоритм?
P.S. Спасибо всем, написали много интересных алгоритмов. Но всё-таки конкретизирую задачу: в функцию обхода передается корень дерева, в каждой вершине хранится список потомков, предок неизвестен. Возможна вторая постановка — в каждой вершине хранится массив потомков конкретной(и одинаковой для всех вершин) длины. Автору известно решение первой задачи, при которой в каждую вершину заходится 1+количество потомков вершины раз. Также, автору известно решение второй задачи для бинарного дерева(обход Морриса). Больше автор ничего придумать/нагуглить не смог.
Эм, в смысле не один раз выводятся? Ты на некой итерации обхода в глубину смотришь, был ли ты в вершине или нет, если не был — выводишь, иначе — нет. Или я что-то не так понял?
А так, помню, в школе нам давали нерекурсивный обход дерева, но я что-то уже не помню :\
фишка в том, что я не могу на константной памяти запомнить все вершины, в которых побывал.
А, ясно, я не понял суть поста, прошу прощения.
Возможно, поможет.
Если у вершины в дереве постоянное число потомков (т.е. заранее известное O(1)), для каждой вершины известен предок и список потомков, то можно, скорее всего, развить метод из ссылки выше.
Вообще имеет значение как задано дерево: списком ребер, списком предков, N списками потомков, всем этим и т.д.
Или если, опять же мы знаем список потомков и предков, можно заюзать массив с предками как стек/очередь :D
P.S. решение с рекурсией не с константной памятью по определению :)
Ну, очевидно, что рекурсия не совсем константна) Я предполагал, что дерево задано списком потомков для каждой вершины, предок неизвестен. И изначально доступ есть только к корню.
Хотя, можно и не список, а постоянное число потомков у каждого дерева. Для такой задачи в случае бинарного дерева приходит в голову обход Морриса, а для какого-нибудь другого — ничего не приходит(
Написал извращенское решение за NlogN с известными предками и потомками.
И решение за N, но с опустошением списка смежности.
В принципе, идея та же самая, что у SergeiFedorov (там предок пихается в список потомков, так что память у нас одинаковая).
Занумеруем все вершины от 1. Теперь пусть мы стоим в вершине V. Перебираем потомков, находим очередного потомка U. В списке смежности вершины V, умножаем значение соответствующее вершине U на -1. Пробегаемся по списку смежности вершины U, вершину V там помещаем в конец и тоже умножаем на -1. Теперь переходим в вершину V. Теперь когда у вершины весь список потомков станет отрицательным, значит мы обошли ее полностью )) И предок, это последняя вершина в ее списке, вернемся в нее и продолжим просматривать список обхода с первого не отрицательного числа.
Получается не совсем честный алгоритм, который действует по модулю, того что наш граф сохранен не оптимальным образом (значения в списках, можно умножать). Однако памяти он действительно требует меньше, чем стандартный обход.
Не читал ссылку yeputons но очень легко можно сделать итератор по произвольному дереву. Пусть дерево хранится в формате (parent, child, sibling) и корневое. Пусть мы находимся в некоторой вершине дерева в итераторе. Тогда ++ делается так:
1) Если у вершины есть child — он ответ.
2) Если у вершины есть sibling — он ответ.
3) Поднимаемся вверх, пока у вершины нет sibling-a. Если нашли вершину с sibling-ом, то этот sibling — ответ.
4) Обход закончен.
Upd. Корректность — легко заметить, что итератор проходит сверху вниз по дереву в традиционном представлении дерева пользователю.
В одном из комментариев топикстартер говорил, что ссылок на родителя нет. Но все равно формулировка задачи такова, что можно предложить, например, такое решение:
Пусть вершины дерева хранятся в памяти так, что они идут подряд друг за другом в том же порядке, в котором их нужно вывести. Тогда просто проходимся по памяти и выводим.
Кстати, только в этой ветке описаны алгоритмы, которые реально используют константный объем, как написано в топике, а не константу дополнительно.
Автор не расскажет?:)
Вот. Идея — при каждом заходе в вершину сдвигать все указатели(т.е, если до захода у вернишы было p — потомков, то после него i-ый указатель будет указывать на i+1 -го потомка, а указатель p — на предка).
Наверное, когда говорят "используя O(1) памяти", подразумевается, что структура дерева лежит в read-only памяти. Если это не так, обычно прямо указывают, можно ли дерево менять, и надо ли его в конце восстановить.
Решение, когда дерево можно разрушить, можно сделать примерно так (тут я предполагаю, что указатель на вернишу и указатель на очередь занимают одинаковое количество памяти):
Эта функция вся в хаках, и наверняка можно сделать без них, но она должна работать. Основная идея -- мы обрабатываем списки детей (не важно массив это или вектор -- главное чтобы по нему можно было итерировать). Мы складываем такие списки в стек. При этом мы исползуем первый элемент списка чтобы указать на следующий элемент стека. Основная идея алгоритма: взять список из стека. Сейчас это список содержит детей какой-то вершины (та вершина уже давно выведена, и нам не интересна). Обработаем вершины из списка. Для каждой вершины выведем ее и положим список ее детей на стек. При этом нам придется пожертвовать первым элементом этого списка. Положим этот первый элемент в список, который мы обрабатываем прямо сейчас, вместо элемента, который мы только что вывели. Когда один список вершин обработан, для каждой вершины этого списка ее список детей уже лежит на стеке, с утраченным первым элементом, а все эти первые элементы сейчас сложены в список, который мы только что обработали. Обработаем его снова, и снова, пока в нем ничего не останется. Ничего не осталось -- берем следующего из списка. В такой реализации это квадрат по времени, но можно ужать до линии, если в начале каждой обработки откидывать все nullptr в списке в конец. По пямяти константа, но используется память дерева.