алгоритм направленного графа задача

Question

Пожалуйста, помогите мне с алгоритмом для следующей задачи -

Учитывая совокупность фактов, мы хотели бы избавиться от такого же избыточности, насколько это возможно. Факты, связанные с этой проблемой, являются членами транзитивной связи между прописными буквами. Таким образом, каждый факт представляет собой пару прописных букв, таких как AB, что означает, что A связано с B. Буква может или не может быть связана с самим собой, но транзитивность имеет место: если A связано с B и B, связано с C, тогда мы можем заключите, что A связано с C. Создайте класс FactCount, содержащий метод minFacts, которому дана известная строка [], и которая возвращает размер самого маленького набора фактов, который позволит нам вывести все (и только те вещи) что может быть выведено из фактов, содержащихся в известных.

Каждый элемент известного будет содержать 1 или более фактов, разделенных одним пробелом. Наименьший набор фактов может содержать факты, которые могут быть выведены из известных, но не содержащихся в нем.

Например:

{ "AB AC CA AA BC", "AD"}

Возвращает: 4

AB, CA, BC и AD позволяют нам сделать вывод, как АА (AB, BC, CA дает AA транзитивностью), а AC (AB, BC дает AC транзитивностью), и нет меньшего подмножества, которое позволяет вывести все известные факты.

P.S - НЕ РАБОТАЕТ. Просто проблема, которую я нашел онлайн и не мог решить часами ...

Answer 1

Надеюсь, что вы ищете spanning tree вашего графа.

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

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

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

В более математических терминах узлы, принадлежащие вашему связующему дереву и узлам, не принадлежащим ему, являются непересекающимися наборами, и ни один из них не является пустым множеством.

Вы можете, конечно, повторить поиск MST на оставшемся подмножестве, чтобы создать остовный лес, пока не исчерпаете свой набор узлов.