Найти шаг от s до t длины, делимой на 3 в ориентированном графе

Question

Из В лекционных заметках Джеффа Эриксона об алгоритмах графа есть упражнение, чтобы проверить, можно ли делить обход между заданными вершинами s и t на 3 в ориентированном графе.

Я думал использовать поиск в ширину на графике, чтобы получить все пути от s до t. Если простые пути не имеют длины, кратной 3, запустите алгоритм еще раз, чтобы проверить, существует ли цикл между s и t, где длина цикла не делится на 3. Однако я считаю, что метод действительно неэффективно.

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

Answer 1

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

В этом случае мы можем создать новый граф с тремя копиями каждого узла, например, если u является узлом в исходном графе, то у нового графа есть три соответствующих узла (u, 0), (u, 1) и (u, 2). Для каждого ребра u → v в исходном графе, у нового графа есть три соответствующих ребра (u, 0) → (v, 1), (u, 1) → (v, 2) и (u, 2) → (v, 0).

Если пройти (n_0, r_0) → ... → (n_k, r_k) с k ребрами, мы знать, что r[i+1] = r[i] + 1 (modulo 3), потому что все ребра в новом графе удовлетворяют этому свойству. Следовательно, если r_0 = 0, то r_k = k (modulo 3).

Из этого следует, что (s, 0) имеет переход к (t, 0) в новом графе, если и только если s имеет переход к t в исходном график с использованием кратных 3 ребер. Таким образом, вы можете просто применить стандартный алгоритм поиска пути, такой как BFS, в новом графике, чтобы увидеть, достижима ли (t, 0) из (s, 0).

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