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