У меня есть неориентированный невзвешенный граф без циклов, где у каждого узла есть метка. Я хотел бы найти все подграфы в этом графе, которые включают по крайней мере один узел с меткой c. Таким образом, каждый из подграфов должен быть как можно меньше, а это означает, что он должен содержать только узлы, необходимые для соединения узлов, которые имеют указанную c метку.
Например, учитывая такой граф (числа - это метки соответствующих узлов): 2-1-2-1-1-2-1
Если 2 в качестве метки c, результат должен быть: 2, 2, 2, 2-1 -2, 2-1-2-1-1-2, 2-1-1-2
Существует ли алгоритм, который эффективно генерирует такие подграфы?