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