Подскажите пожалуйста пример реализации dfs без рекурсии. Вот попробовал реализовать через стэк, но как-то криво работает..
int G[N][N]; // Матрица смежностей
...
void dfs(int p)
{
stack<int> S;
vector<int> v(N);
int t;
S.push(p);
v[p]++;
cout << p + 1 << " ";
while(!S.empty())
{
t = S.top();
S.pop();
for(int i = N - 1; i > 0; i--)
if(G[t][i] && !v[i])
{
S.push(i);
v[i]++;
cout << i + 1 << " ";
}
}
}
Кстати, зачем вообще отдельно использовать стек когда есть вектор? Оо
Для читабельности кода. Вот читает кто-то твой код и видит слово вектор. И сразу думает, что ты тут какой-то линейной алгеброй занимаешься. А напишешь стек и всем ясно, что тут ДФС'ом попахивает.
Было дело, писал какую-то программу. Там нужен был стек и памяти выделено очень мало... Ну так вот, программа со стеком забрала 60000KB, а тоже самое с вектором — около 3000KB. Был очень удивлен. До сих пор не понимаю, чем это вызвано. С того момента больше не использую стек...
Вроде, std::stack по-умолчанию использует как хранилище не std::vector, а std::deque.
А не зависит ли это часом от конкретной реализации?
cout << i + 1 << " ";Это не будет работать, т.к. мы не переключаемся на выводимую вершину сразу. Чтобы это работало, нужно выводить в теле while-цикла при первом заходе в неё.
Спасибо конечно, а как это влияет? Не вижу разницы каким образом первую вершину выводить, с которой начинается обход..
Тут дело не в первой вершине, а таки в каждой. Ну, если ты хочешь получить вершины в порядке их обхода, надо и выводить их в порядке обхода, то есть при входе в вершину или при выходе из неё. А ты выводишь при добавлении в стек. С бфс-ом прокатило бы, но с нерекурсивным дфс не прокатит, так как ты переходишь к вершине не сразу после её добавления в стек, а когда добавишь в него всех потомков предыдущей вершины.
Спасибо большое, ошибку понял:
и что, сейчас работает? Больше похоже на бфс с перебором ребер в обратном порядке.
Это был бы бфс, если бы контейнером являлся queue...
Согласен, но заменить queue на stack не достаточно, чтобы из бфса сделать дфс.
Да ладно?. Вроде как достаточно.
С чего бы? Внизу у фиолетового норм решение, а это неправильное.
Для дерева было бы достаточно.
Если в графе есть циклы, то это уже не совсем dfs. Если в определенную вершину есть ребро как с вершины х, так и из какого-то из ее потомков, то есть вероятность того, что по ребру из потомка она была бы посещена раньше, чем по ребру из предка, которое мы ей "забронировали".
Пример — граф вида
Мы обойдем его как 1 2 3... 100, хотя в настоящем dfs при рассмотрении вершины 2 вершина 100 еще не посещена, и порядок должен быть 1 2 100 3 4 5...
=================================
Спасибо за подробное объяснение. Сам всегда думал, что простой смены очереди на стек достаточно.
А я правильно понимаю, что постоянного хождения туда-сюда можно избежать, если, например, устанавливать метку посещения только при входе в вершину, а перед этим проверять, что она ещё не установлена?
И нахрена же писать дфс без рекурсии?
Ну вдруг памяти на рекурсию жалко. Да и просто ради интереса/общего развития можно написать.
Ради общего интереса можно еще на ассемблере написать))))
Тогда уж на brainfuck...
во-первых, чтобы не было переполнения стека
во-вторых, вызов функций во многих языках очень дорог
Например вот так: http://pastebin.com/t8egDMrs
Вроде бы порядок обхода как в настоящем dfs.