Удаление циклических зависимостей на ориентированном графе с фиксированными ребрами

Question

У меня есть ориентированный циклический граф. Некоторые края ИСПРАВЛЕНЫ и не могут быть удалены. Другие края могут быть удалены, чтобы разорвать цикл.

Как лучше всего удалить циклы на этом графике? Обход должен быть как можно больше DFS и начинаться с данного узла.

Answer 1

Я использовал следующий алгоритм для решения своей проблемы:

Начните с графика всех фиксированных ребер, помеченных как подтвержденные

Из начального узла проходите через все подтвержденные ребра, а также еще не подтвержденные ребра. Но когда вы собираетесь вернуться по еще не подтвержденному ребру, сначала проверьте, имеет ли узел, к которому идет ребро, путь, следуя подтвержденным ребрам, к узлу в текущем дереве поиска (то есть узлу с < em> флаг посещения установлен). Эта проверка должна выполняться рекурсивно, следуя всем подтвержденным ребрам, но это слишком медленно для меня, поэтому я остановлюсь здесь, чтобы просто проверить, посещает ли узел или же посещает какой-либо из узлов, к которым он был подтвержден. Это охватит большинство моих случаев, но время от времени оставит циклы на графике.

После описанного выше шага я использую алгоритм Тарьяна для нахождения сильно связанных компонентов, оставшихся в графе (это можно сделать за время O (V + E)). Количество сильно связанных компонентов в моих случаях будет очень небольшим, поэтому я просто просматриваю каждый сильно связанный компонент и удаляю по одному съемному краю каждый. Затем я делаю этот шаг снова, пока на графике не останется больше циклов.

Это работает нормально и достаточно быстро.

Answer 2

Что вы можете сделать, это использовать алгоритм Дейкстры: начните с графа, содержащего только ФИКСИРОВАННЫЕ ребра. Затем примените адаптацию алгоритма, начиная с графика, который у вас уже есть:

<Ол>

Начните с начального узла и всех ИСПРАВЛЕННЫХ ребер в компоненте начального узла. Предположим, это дерево.

Добавьте ближайший к дереву узел.

Также добавьте все ФИКСИРОВАННЫЕ ребра в компоненте узла, который вы только что добавили.

Если все узлы в дереве, конец. В противном случае перейдите к шагу 4.

Это, конечно, предполагает, что граф, состоящий только из фиксированных ребер, не содержит циклов. Если это так, решения не существует (то есть подграфа без ребер, но содержащего все ИСПРАВЛЕННЫЕ ребра).

Для ориентированных графов это немного сложнее. В этом случае любой компонент графа ФИКСИРОВАННЫХ ребер должен быть деревом. В алгоритме, подобном Dijkstra, только корни этих узлов должны быть кандидатами для добавления в дерево.

Answer 3

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

Если графу не нужно оставаться связанным, просто обойдите все ребра и удалите все нефиксированные. Это удаляет все циклы, которые вы можете удалить, не удаляя ФИКСИРОВАННЫЕ края.

Если вы хотите, чтобы простой жадный алгоритм удалял ребра, которые являются чисто DFS, вы можете использовать что-то вроде этого, ЕСЛИ граф остается подключенным, даже когда вы удаляете некоторые нефиксированные ребра:

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]