| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нужен алгоритм обхода ненаправленного графа |
| Автор: KQT 30.4.2011, 19:53 |
| Доброго вечера!.. Существует ли алгоритм обхода ненаправленного графа: линейный по количеству вершин и константный по памяти? Критическим является второе требование, т. е. буду рад и более медленному алгоритму, лишь бы он не требовал дополнительной памяти. Существует ли такой алгоритм для деревьев? |
| Автор: esperanto 30.4.2011, 22:31 |
| Константный по памяти не существует. Есть за лог(п) памяти и больше |
| Автор: KQT 30.4.2011, 22:43 |
| Как называется? Доказано, что лучше нельзя? |
| Автор: esperanto 1.5.2011, 19:13 | ||
То что нельзя за константное количество памяти достаточно очевидно. Ведь надо или считать сколько шагов сделал алгоритм или помечать вершины которые алгоритм уже поситил. Первый подход требует переменную счетчик второй линейное количество памяти. |