Учитывая некоторый ориентированный граф, есть много алгоритмов для проверки погоды или нет, он содержит циклы. Т.е. алгоритмы с такими сигнатурами:
function isCyclic(g: DirectedGraph): bool
Но у меня есть проблема, которая немного отличается: учитывая, что я знаю, что ориентированный граф является ациклическим, я хочу проверить, будет ли добавление заданного ребра создавать цикл. Т.е. как то так:
function willCreateCycle(g: AcyclicDirectedGraph, newEdge: Edge): bool
Мое решение так далеко:
В графе у нас есть несколько узлов, два из которых F (от) и T (до)
Мы хотим проверить, если добавление нового ребра E = F-> T создаст цикл
=>
Пройдите по графику, начиная с узла T. Если мы в любой точке окажемся в узле F, у нас будет цикл.
Вы думаете, это правильно? :))