Здравствуйте, Arsen.Shnurkov, Вы писали:

AS>И не только граф, но и алгоритм поиска в направленном графе
AS>подграфа с заданной раскраской (в частном случае не подграфа, а цепочки).
AS>Как нужный мне алгоритм называется и как его искать?

Тебе нужен обход в ширину (breadth-first traversal) в том варианте, который принимает несколько исхоных вершин. Перед началом ты перебираешь все вершины, и те, которые помечены так же, как начало пути-паттерна, складываешь в FIFO-очередь. В процессе складываешь в очередь только те вершины, которые помечены так же, как очередная вершина на пути-паттерне (то есть на том же расстоянии от начала).

AS>граф с вершинами разных типов (видимо это называется "окрашенные вершины").

Скорее, «помеченные» («labeled») вершины. Дополнительно окрашены они будут в процессе обхода, чтобы различать впервые встреченные (белые); те, для которых work in progress (серые) и они в очереди; и полностью рассмотренные (чёрные).

AS>Перебираем все вершины графа, для каждой смотрим — есть ли исходящий из этой вершины путь, полностью совпадающий с цепочкой.

Поиск в ширину займёт O(E + V), быстрее способа не вижу. От упомянутого наивного перебора BFS отличается тем, что не пойдёт по путям с общим постфиксом, потому что в процессе обхода вершины раскрашиваются, и повторный заход можно задетектить — встретим не белую вершину.