1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же:
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись
3 запроса, таблички теоретически большие, практически - все это перемалывается без проблем.