Есть так много способов подойти к этому, и, чтобы не путать вещи, вот отдельный ответ, посвященный описанию вашей основной проблемы:

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

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

Кроме того, если вы действительно хотите найти кучу подграфов, рандомизированный алгоритм по-прежнему является хорошим выбором, поскольку вы можете запускать его несколько раз с разными начальными числами.

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

Итак, перейдем к алгоритму: в зависимости от свойств вашего графа (ов) оптимальный алгоритм может варьироваться, но вы всегда можете начать с простого случайного блуждания, начиная с одного синего узла, переходя к другому синему узлу. (при этом убедитесь, что вы не идете по своим старым стопам). Затем выберите случайный узел на этом пути и начните оттуда переходить к следующему синему и так далее.

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