Какой алгоритм я могу применить к этому DAG?

Question

У меня есть DAG, представляющая список свойств. Эти свойства таковы, что если a> b, то a имеет направленное ребро к b. Он также транзитивен, так что если a> b и b> c, то a имеет направленное ребро к c.

Однако направленный край от a до c является излишним, потому что a имеет направленный край к b, а b имеет направленный край к c. Как я могу обрезать все эти лишние края? Я думал об использовании алгоритма минимального связующего дерева, но я не совсем уверен, какой алгоритм следует применять в этой ситуации

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

После завершения алгоритма на выходе будет линейный список всех узлов в порядке, соответствующем графику. Таким образом, если a имеет три направленных ребра к b, c и d. b и c, также каждый из которых имеет направленный край к d, выход может быть либо abcd, либо acbd.

Answer 1

Это называется проблемой транзитивного сокращения . Формально говоря, вы ищете минимальный (наименьшее количество ребер) ориентированный граф, транзитивное замыкание которого равно транзитивному замыканию входного графа. (Диаграмма в приведенной выше ссылке на Википедию проясняет это.)

По-видимому, существует эффективный алгоритм для решения этой проблемы, который занимает столько же времени, сколько и для создания транзитивного замыкания (то есть более распространенной обратной задачи добавления транзитивных ссылок вместо их удаления), однако ссылка на 1972 год Бумага Ахо, Гэри и Уллмана стоит 25 долларов, и какое-то быстрое прибегание к поиску не дало никаких хороших описаний.

РЕДАКТИРОВАНИЕ: Скотт Коттон graphlib содержит реализацию Java ! Эта библиотека Java выглядит очень хорошо организованной.

Answer 2

На самом деле, осмотревшись немного больше, я думаю, что Топологическая сортировка - это то, что я действительно здесь хочу.

Answer 3

Если это уже n узлов с направленными ребрами:

1. Начиная с любой точки M, обведите все ее дочерние ребра, выберите самый большой дочерний элемент (например, N), удалите другие ребра, сложность должна быть o (n). Если N не существует (нет дочернего ребра, перейдите к шагу 3).
2. начать с N, повторить шаг 1.
3. начать с точки M, выбрать наименьший родительский узел (например, T), удалить края других.
4. начать с T, повторите шаг 3 .....

---

На самом деле это всего лишь алгоритм упорядочения, и общая сложность должна составлять o (0.5n ^ 2).

---

Одна проблема состоит в том, что если мы хотим зациклить родительские узлы одного узла, то нам нужно больше памяти для регистрации края, чтобы мы могли проследить от дочернего к родительскому. Это можно улучшить на шаге 3, где мы выбираем один узел из левых узлов больше, чем M, это означает, что нам нужно сохранить список узлов, чтобы знать, какие узлы остались ..