Алгоритмы. Обход в глубину (DFS)

После небольшой паузы мы продолжаем разбирать различные алгоритмы.

Обход в глубину (DFS) — это один из фундаментальных алгоритмов на графах, и его легче всего понять через аналогию с исследованием пещеры. Представь, что ты стоишь в системе туннелей с множеством разветвлений. Твоя стратегия заключается в том, чтобы выбрать первый попавшийся проход и идти по нему до тех пор, пока не упрешься в тупик. Только тогда ты возвращаешься назад к последнему перекрестку, где еще есть неисследованные пути, и пробуешь следующий туннель. Эта логика, где глубина проникновения важнее ширины охвата, и лежит в основе алгоритма DFS.

Рассмотрим небольшой граф. Предположим, у нас есть узлы, соединенные между собой: A связан с B и C; B связан с A, D и E; C связан с A и F; D связан только с B; E связан с B и F, а F, в свою очередь, связан с C и E. Если начать обход с узла A, DFS будет двигаться следующим образом: сначала мы попадаем в A, затем углубляемся в B, оттуда — в D. Достигнув D, мы понимаем, что это тупик (сосед B уже посещен), поэтому возвращаемся обратно в B и идем по следующему пути в E. Из E переходим в F, который тоже оказывается тупиком (все соседи посещены или ведут назад). После возврата в E и затем в B, мы наконец возвращаемся в A и идем в C, но обнаруживаем, что C уже был посещен через F. Итоговый порядок посещения узлов будет таким: A, B, D, E, F, C.

Граф:
        A
       / \
      B   C
     / \   \
    D   E   F
         \ /
          (F связан с E и C)

DFS от A пойдёт так:
A → B → D (тупик, назад) → E → F (тупик, назад) → назад → C (уже посещён через F)

Порядок посещения: A, B, D, E, F, C

В этом заключается ключевое отличие DFS от другого известного алгоритма — поиска в ширину (BFS). BFS работает подобно кругам на воде: сначала исследуются все соседние узлы, затем их соседи, распространяясь равномерно во все стороны. DFS же напоминает нить Ариадны в лабиринте: он всегда идет до конца по выбранному пути и лишь затем возвращается.

Граф:           BFS (в ширину):        DFS (в глубину):
    A           Уровень за уровнем     Ветка за веткой
   / \          A                      A
  B   C         B, C                   B, D, E, F, C
 / \   \        D, E, F
D   E   F

Для реализации DFS можно использовать два основных подхода, которые делают одно и то же, но разными средствами: рекурсию и явный стек. Рекурсивный метод полагается на стек вызовов самой программы. Когда мы пишем функцию, которая вызывает саму себя для обработки соседей, язык программирования автоматически запоминает точку возврата. Однако здесь есть важная особенность Python: не стоит задавать значение аргумента visited по умолчанию как пустое множество (set()), так как изменяемые объекты создаются один раз и будут переиспользованы во всех вызовах функции. Вместо этого нужно создавать его внутри функции, если оно не передано.

Пример 1

Чтобы лучше понять, как работает рекурсия, можно проследить её выполнение по шагам. Входя в узел A, мы помечаем его как посещенный и записываем в результат. Затем смотрим на соседа B, который еще не посещен, и вызываем функцию для B. Внутри вызова для B повторяется та же логика: добавляем B в путь и идем к его первому непосещенному соседу D. В D тупик, и функция возвращает результат обратно. Далее в B очередь доходит до следующего соседа — E. Из E попадаем в F, а из F — в C. Когда все пути исчерпаны, результаты склеиваются и возвращаются наверх.

Пример 2

Второй способ реализации — итеративный с использованием явного стека. Стек работает по принципу «последним пришел — первым вышел» (LIFO). Это как стопка тарелок: новую тарелку кладут сверху, и первую берут тоже сверху. В коде мы сами управляем этим стеком, помещая туда узлы для последующей обработки. Важный нюанс: чтобы порядок обхода совпадал с рекурсивной версией, соседей часто добавляют в обратном порядке. Если просто положить соседей в стек по порядку, то из-за механизма LIFO первым будет извлечен последний сосед, и обход пойдет в другую сторону.

Пример 3

📟 Прилетело из @solidityset

Процесс итеративного обхода можно наглядно представить в виде таблицы, где видно, как меняется содержимое стека на каждом шаге. Начинаем со стеком, содержащим A. Извлекаем A, помечаем его и добавляем в результат, а затем кладем в стек его соседей C и B в обратном порядке (чтобы B оказался сверху). Затем извлекаем B, затем D, и так далее, пока стек не опустеет.

Шаг | Стек (вершина →)   | Берём | visited         | result
----|--------------------|-------|-----------------|------------------
 0  | [A]                |  A    | {A}             | [A]
 1  | [C, B]             |  B    | {A,B}           | [A,B]
 2  | [C, E, D]          |  D    | {A,B,D}         | [A,B,D]
 3  | [C, E]             |  E    | {A,B,D,E}       | [A,B,D,E]
 4  | [C, F]             |  F    | {A,B,D,E,F}     | [A,B,D,E,F]
 5  | [C, E*, C]         |  C    | {A,B,D,E,F,C}   | [A,B,D,E,F,C]
    (* E уже в visited — пропустим при извлечении)

Финальный результат: [A, B, D, E, F, C] ✓

Этот код, по сути, является готовой реализацией итеративного DFS, где стек берет на себя работу, которую в рекурсивной версии выполняет стек вызовов. Каждая часть здесь важна: множество visited отслеживает уже обработанные узлы, список stack хранит узлы, которые предстоит обработать, а цикл while работает, пока есть что извлекать.

Одна из классических задач, решаемых с помощью DFS, — поиск циклов в графе. Цикл — это ситуация, когда, двигаясь по графу, мы возвращаемся в узел, который уже встречали на текущем пути. Важно отличать просто посещенный узел от узла, находящегося в текущем стеке рекурсии. Ведь если мы видим уже посещенный узел, который не является частью текущего пути, это может быть просто пересечение, а не цикл. Поэтому в алгоритме используются два множества: visited для всех узлов, которые когда-либо посещались, и rec_stack для узлов, в которых мы находимся прямо сейчас в процессе рекурсивного спуска.

Граф БЕЗ цикла:     Граф С циклом:
    A                   A
   / \                 / \
  B   C               B   C
  |                   |\ /
  D                   | X
                      |/ \
                      D   E

Алгоритм запускает проверку из каждой вершины, чтобы учесть возможную несвязность графа. Если в процессе обхода мы наталкиваемся на соседа, который уже есть в rec_stack, это означает обнаружение цикла.

Пример 4

Как именно это работает, можно увидеть на примере графа с циклом. Начиная с A, мы идем в B, затем в D. В узле D видим соседа B, который уже есть в rec_stack. Это и есть сигнал о наличии цикла.

Пример 5

Еще одно важное практическое применение DFS — поиск пути в лабиринте. Здесь выбор между DFS и BFS зависит от конкретной задачи. Если нам нужно просто найти любой путь к выходу, DFS часто оказывается предпочтительнее. Он идет по одному пути до упора и, если лабиринт не слишком разветвлен, может найти выход довольно быстро. При этом DFS использует меньше памяти, так как хранит лишь текущий путь.

Пример 6

Однако если стоит задача найти кратчайший путь, DFS не подходит. Он может углубиться в длинную ветку и найти путь, который окажется далеко не самым коротким, в то время как существует более прямой маршрут. В такой ситуации BFS гарантированно найдет кратчайший путь, хотя и потребует больше памяти для хранения всех узлов текущего уровня.

Лабиринт:        DFS может пойти так:      BFS пойдёт так:
  S               S→A→C→E→EXIT             S→A (длина 1)
 / \              (длина 4)                S→B (длина 1)
A   B             Хотя существует          S→A→C, S→B→EXIT
|   |             S→B→EXIT                 Найдёт S→B→EXIT
C  EXIT           (длина 2)!              (длина 2) первым
 \ /
  E
  |
 EXIT

DFS нашёл путь длиной 4, хотя есть путь длиной 2.
BFS всегда находит кратчайший путь.

📟 Прилетело из @solidityset

Сравнивая эти два подхода для лабиринта, можно выделить несколько критериев. Для задачи нахождения любого выхода оба алгоритма работают, но DFS требует меньше памяти. Для поиска кратчайшего пути BFS гарантирует результат, а DFS — нет. В глубоких лабиринтах рекурсивный DFS рискует переполнить стек, тогда как итеративный и BFS безопасны. В широких лабиринтах BFS может потребить много памяти, а DFS остается эффективным.

Что касается вычислительной сложности, то и для DFS, и для BFS она одинакова. Временная сложность составляет O(V + E), где V — количество вершин (узлов), а E — количество ребер. Это объясняется тем, что алгоритм посещает каждую вершину ровно один раз и просматривает каждое ребро также один раз. Пространственная сложность в худшем случае составляет O(V) — память нужна для хранения множества посещенных узлов и, в случае итеративной реализации, стека.

Подводя итог, можно сказать, что DFS — это алгоритм, который идет вглубь до упора, а затем возвращается. Его можно реализовать элегантно через рекурсию или более контролируемо через явный стек. Он применяется для поиска любого пути, обнаружения циклов, топологической сортировки и обхода деревьев, но не гарантирует нахождения кратчайшего маршрута.

#algorithm

📟 Прилетело из @solidityset

О КАНАЛЕ. СОТРУДНИЧЕСТВО. ЛУЧШЕЕ

я тут решил навайбкодить себе сайт визитку в виде миниаппа
+ собрал "бесплатный курс по агентам" из своих материалов

Го чекать:

📟 Прилетело из @danokhlopkov

О КАНАЛЕ. СОТРУДНИЧЕСТВО. ЛУЧШЕЕ

я тут решил навайбкодить себе сайт визитку в виде миниаппа
+ собрал "бесплатный курс по агентам" из своих материалов

Го чекать:

📟 Прилетело из @danokhlopkov

gm! Писать про крипту нынче не легко. Фарм поинтов обхожу стороной, про арбитраж на prediction маркетах рассказывать особо нечего, а скам-лончи обхожу стороной. Мемкоин szn для меня закончился в начале 2025 на TRUMP — больше туда не залезал и не хочу. Портфель консервативный, свободных денег на лудоманию без зарплаты стало сильно меньше, поэтому просто держу btc/stables в 40/40/20 пропорции, как учил главный лудоволк. И просто иногда ребалансирую. Но хотел сегодня написать что-то интересное про крипту — и повод нашёлся сам собой.

USDT — один из крупнейших стейблкоинов (хотя USDC уже обходит по объёму транзакций — дешборд на Dune с кучей интересной инфы по всем стейблам)

Aave — крупнейший лендинг. стабильные контракты, проверенные годами.

Что может пойти не так? А вот что: пару месяцев я жил на паранойе, что мой кошелёк заблокировали AML-щики. не мог пользоваться Aave — транзакции ревертились. пришлось дебажить через Tenderly, раскручивать calldata — и оказалось, что всему виной кривая система approvals у USDT:

require(!((_value != 0) && (allowed[msg.sender][_spender] != 0)));

Нельзя изменить ненулевой allowance на другое ненулевое значение. костыль против race condition из 2017 года.

Был сильно удивлён, что крупнейший лендинг + крупнейший стейблкоин не смогли за 8 лет нормально обработать этот кейс у себя. Но с помощью ручного revoke и повторного approve проблема решилась.

📟 Прилетело из @insuline_eth

Про расследование ZachXBT сейчас не напишет только ленивый. Думаю, что следующие расследования в твиттере – это попытка найти кошельки Зака, ведь на Polymarket заработано сильно больше, чем у "героев" выпуска. Но я не об этом.

Trade memecoins, perpetuals, and earn yield. Winter 2025. Y Combinator.

То, что начиналось как локальный мем про деградацию YC — кажется стало реальностью. Бейдж когда-то работал как институт репутации. Нынче даже в нашей снг крипто-телеграм тусовке есть рагпуллеры с бейджиком YC. Без шуток.

Посмотрите батчи за 25-26 год и найдите хотя бы пару продуктов, за которые вы платили как пользователь. Не как инвестор или лудоман. Как пользователь. У меня нет ни одного.

Недавно ETH Zurich (университет, а не конфа лол) и Anthropic выкатили ресёрч — деанон анонимных комментаторов Reddit через LLM. Точность под 70%, стоимость проверки одного человека меньше доллара. Прикрутить такое к due diligence участников YC — задача на выходные. А пока остаётся ждать, чтобы на каждого участника батча расследование писал Zach. Бесплатно. Или не бесплатно — думаю, скоро узнаем.

📟 Прилетело из @insuline_eth

Хорошего человека Gowno не назовут

📟 Прилетело из @insuline_eth

edgex: очередной perp dex или нечто интересное? Анализ команды, концепта, коина, кода + практики

Edgex сначала показался обычным perp dex, поэтому не использовал его. Но одна особенность, о которой узнал позже, заставила посмотреть глубже на проект.

Читать в Teletype, читать в Paragraph.
Открыть web приложение.

Общий итог
• Команда: 4 из 5: команда есть, но участников публичных мало (ко-фаундер и 4 контребьютера, да и те вроде не в технической сфере). Опыт основателя до Edgex тоже не смог оценить.
Но соцсети активные, на вопросы отвечают корректно и чрезвычайно быстро! Я прямо удивился, когда получил ответ через 10-20 минут после сообщения, если не быстрее.

• Концепт: 3 из 5: нет анализа спроса и конкурентов. По концепту это обычный Perp DEX, почти без новых идей. Из сильного - параллельная обработка рынков (BTC и ETH не блокируют друг друга) - это мне понравилось.

• Коин: 3 из 5: токеномика есть, но 25% core contributors и не раскрыто, сколько у инвесторов - это снижает прозрачность и создаёт риск давления. Утилиты не описаны. Есть инвестиции от Amber Group и Circle Ventures, но без суммы.

• Код: 2 из 5: есть аудиты (2024-2025 года) и адреса контрактов, но публичного GitHub edgeX нет, код основной системы закрыт. Есть только аудит и открытый код базовой технологии (StarkEx), при этом нет подтверждения, что найденные проблемы полностью исправлены.

• Практика: 3 из 5: интерфейс в целом удобный, и даже на Русском - это плюс!
Но рынки прогнозов недоступны на некоторых IP (или VPN блокируется, или баг) - невозможно использовать.
Плюс, на споте нет стоп-лоссов и тейк-профитов, но я такого ни у кого не видел из perp дексов.
Из плюсов ещё - на бессрочных фьючерсах есть лестничный ордер и торговля в обе стороны.

Ещё одна проблема - при каждом открытии браузера выскакивает просьба подписать 2 сообщения, хотя я отметил "Запомнить меня".

Что касается скорости исполнения: не моментально, но и не медленно. Где-то 2-5 секунд, хотя и не считал = мои хотелки.


Общий балл: 15 из 25.
Проект интересный, но я бы не использовал в качестве основной децентрализованной биржи: сыроват.

Читать в Teletype, читать в Paragraph.
Открыть web приложение.

А вы видели стоп-лосс и тейк-профит на спотовых рынках каких-то dex?

😎 Незрячий web3 программист (подписаться)
Чат | бот

📟 Прилетело из @blind_dev

🔍 Ищем разработчика в Outreach Today!

Ищу к себе инженера, который заберёт всю техническую часть продукта. Не исполнителя на подхвате, а человека, который будет владеть кодом, развивать систему и шипать — пока я занимаюсь продажами.

— Немного контекста
Outreach Today — B2B SaaS для продаж через email. Закрываем несколько джоб в cold outreach и растём в сторону полного цикла.

• Компании 2 года, полностью на бутстрапе
• $2M ARR, план вырасти x5 в этом году
• 2 000+ B2B-клиентов, 80% в США
• Команда меньше 5 человек
• Весь +-код до сих пор писал я сам

— Что предстоит делать

• Развивать систему в одиночку. Несколько сервисов, инфра, продуктовая часть — ты за всё это отвечаешь. Продукт строился быстро — есть техдолг, есть что ломается. Нужен человек, который шарит, как это работает в стартапе: шипать быстро, но не ронять то, что уже работает. Не полгода рефакторить «как правильно», а держать баланс между новым и поддержкой.

• Мы работаем на самом edge: Claude Code, Codex и другие AI-тулы — прямо в продакшене, каждый день. Это не эксперимент, это наш рабочий процесс. Новые инструменты появляются постоянно, и мы их сразу тестим на реальном бизнесе.

— Кого ищу
Опыт работы в стартапах — понимаешь, что такое шипать быстро и жить с техдолгом. Problem solver — стек для тебя инструмент, а не идентичность. У нас Python, Node, часть на Go. Завтра может быть что-то ещё — и это ок. Hands-on — большую часть времени ты пишешь код, а не менеджеришь. Ownership — берёшь задачу, сам разбираешься, сам доводишь до результата. Быстро учишься — новые тулы, новые технологии, новые подходы. Это постоянно, и это должно драйвить, а не пугать.

— Кого точно НЕ ищу
Человека, которому нужен чёткий definition of done на каждый таск. Того, кто привязан к одному стеку. Того, кто хочет менеджерить, а не кодить. Того, кто привык работать «как надо» в большой компании. Если нужен предсказуемый скоуп — тебе у нас не понравится.

— Кому это подойдёт
Ты хочешь строить и решать инженерные задачи, но не хочешь тащить весь бизнес. Может, думал запустить своё, но понял — сделать продукт не значит, что его кто-то купит. Мы этот риск снимаем: продукт есть, клиенты есть, PMF есть, продажи на мне. Тебе — только техническая часть и свобода решать, как её делать.

— Что ты получишь
Работа напрямую с фаундером, без прослоек. Всё, что ты строишь, сразу попадает к реальным клиентам — ты видишь импакт не через полгода в квартальном отчёте, а сразу. Мы живём на свою выручку, не зависим от инвесторов — не будет такого, что не подняли раунд и всех уволили. AI-first разработка с новейшими тулами на реальном бизнесе. Перспектива роста команды — сейчас ты единственный инженер. Компенсацию обсуждаем индивидуально.

— Условия

• Full-time — принципиально, парт-тайм не работает
• Полностью удалённо
• Таймзона ближе к US (я в Сан-Франциско). Европа, СНГ — ок
• Локация: без ограничений
• Оформление через Deel или аналоги

— Как откликнуться

Заполните форму по ссылке: https://forms.gle/8m74fC5VVT1J6Fmu9

После заполнения мы вернёмся с обратной связью или со следующими шагами.

📟 Прилетело из @max_grock