Как найти цикл в ориентированном графе с помощью топологической сортировки?

Я реализовал этот псевдокод в своей программе, чтобы проверить, является ли ориентированный граф ацикличным:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

Это отлично работает, но мне также нужно вывести фактический цикл, если график не ациклический. Можно ли сделать это «внутри» этого кода или мне нужно полностью изменить алгоритм? Я попытался найти решение и нашел этот ответ (Печать (не обнаруживает) цикл с топологической сортировкой), но я не могу понять, как это сделать. У кого-нибудь есть псевдокод, который мог бы мне помочь?


directed-acyclic-graphs cycle topological-sort
person user16655    schedule 27.10.2014    source источник
comment
Вы читали о цветовых картах в алгоритмах графов? Обнаружение цикла тривиально, если у вас есть правильный алгоритм DFS с использованием цветовой карты. Если вы когда-нибудь проследили за ребром и встретили серую вершину, вы нашли цикл. Поскольку вы хотите распечатать вершины, входящие в цикл, вы можете развернуть текущий стек исследуемых вершин до тех пор, пока не найдете ту же самую неприятную серую вершину снова в своем стеке.   -  person seh    schedule 27.10.2014
comment
Я не читал об этом, но похоже, что это лучший план. Тем не менее, я хотел бы использовать решение, которое я уже реализовал, поскольку вся моя программа (довольно большая) зависит от топологической сортировки. Если у меня не получится, я обязательно рассмотрю ваше предложение :)   -  person user16655    schedule 27.10.2014
comment
Я не был достаточно ясен: для топологической сортировки вы запускаете обход в глубину (DFW, а не DFS, так как поиск не задействован) и выделяете только черные вершины по порядку, если вы не найти цикл. Следовательно, DFW одновременно обеспечивает ацикличность вашего графа и топологическую сортировку. DFW и топологическая сортировка не исключают друг друга; вы реализуете топологическую сортировку в терминах DFW.   -  person seh    schedule 27.10.2014

Ответы (1)


arrow_upward
1
arrow_downward

Во-первых, то, что вы пытаетесь сделать, немного проблематично, поскольку может быть более одного цикла. Теоретически каждый узел в графе может иметь саморезку, тогда будет n циклов.

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

person Gil Moshayof    schedule 27.10.2014