Блог пользователя ser398

Нерекурсивный dfs.

Автор ser398, 11 лет назад, По-русски

Недавно возник вопрос про реализацию поиска в глубину без рекурсии. Я умею просто обходить граф и помечать вершины из одной компоненты используя O(V) памяти на стек. При использовании рекурсии легко сделать пометки tin, tout(время входа и время выхода из вершины). А используя стек мне нужно O(V+E) памяти. Вопрос в том, чтобы использовать O(v) памяти на стек и получить пометки tin, tout.

Теги dfs
  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

http://mirror.codeforces.com/blog/entry/8073

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

А зачем О(V+E) памяти? Тебе ведь нужно просто промоделировать рекурсию. Помимо вершины, в стек еще нужно кидать номер ребра, по которому ты перешел во время просмотра всех ребер из текущей вершины. Грубо говоря, ты просто запоминаешь ту самую локальную переменную, которая у тебя в обычном дфс является счетчиком цикла, чтобы при возврате не смотреть с начала все ребра, а именно с места, где ты в последний раз остановился.

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо. Да я забыл, что нам не нужна память на (вершина, страрый счетчик).

    → Ответить