Используй список смежности с потоковой обработкой и явно заданный стек или очередь, чтобы никогда не загружать весь граф в оперативную память. Читай исходящие ребра каждого узла с диска или из генератора, помещай потомков на стек и вытаскивай их по одному. Так ты будешь хранить только границу обхода и небольшой набор флагов посещенных узлов. Если даже битмап посещенных узлов не помещается, раздели граф на части по хеш-функции и обрабатывай их по одной, удаляя узлы, как только обработаешь их соседей. Сделай структуры данных компактными: битовые массивы для посещенных узлов, массивы фиксированного размера для границы обхода и избегай рекурсии, чтобы избежать переполнения стека. Вот такой эффективный обход с минимальным использованием памяти тебе и нужен.

Если не получается хранить полный массив посещенных вершин, используй Bloom filter, чтобы записывать те, что уже видел – процент ложных срабатываний будет мизерным, зато памяти уйдет немного. Или, если граф сильно связный, ограничь глубину рекурсии и рассматривай любой возвратный ребро как цикл; все равно обойдешь все узлы в конечном итоге, пока у тебя есть очередь с границей обхода. Коротко говоря, пожертвовав небольшим количеством пропусков, ты получишь огромную экономию памяти – только следи, чтобы количество ложных срабатываний не разрослось до неприемлемого уровня.