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

1. Кладём все тупики в очередь (только кладём, не раскрашиваем)
2. Если очередь пуста - выходим. Иначе - п.3.
3. Достаём из очереди очередную вершину. Если она покрашена, то её просто пропускаем и идём в п.2. Иначе - п.4
4. Смотрим на список вершин, в которые мы можем из текущей вершины попасть. Есть три возможных варианта
   
   • Есть вершины, в которые мы можем попасть из текущей и которые мы ещё не покрасили. В этом случае просто эту вершину пропускаем, вернёмся к ней позже.
   • Есть вершины, которые мы покрасили в красный. Тогда текущую красим в зелёный
   • В списке красных вершин нет. Тогда в красный цвет красим текущую (в частности, у тупиков красных вершин не будет, поэтому они покрасятся в красный).
   Если выполнился вариант 2 или 3 (т.е. если мы покрасили вершину), то идём в п.5, иначе в п.2
5. Все вершины, из которых мы можем попасть в текущую, закидываем в очередь, и идём в п. 2

Насчёт подпунктов пункта 4. Может быть такое, что у тебя одновременно выполняются первые два пункта (покрашены не все вершины, и среди покрашенных есть красные), в этом случае можешь любое действие выполнять, на результат это не повлияет.

https://forum.sources.ru/index.php?showtopic=421261&view=findpost&p=3845540